什么更有效:排序流还是排序列表?

老实说,我不相信自己 太多 要么在 JMH (除非我了解组装,这对我来说需要很多时间),尤其是因为我使用了 @Setup(Level.Invocation) ,但这里有一个小测试(我参加了 StringInput 根据我做的其他测试生成,但这不重要,只是一些需要排序的数据)

@State(Scope.Thread)
public static class StringInput {

    private String[] letters = { "q", "a", "z", "w", "s", "x", "e", "d", "c", "r", "f", "v", "t", "g", "b",
            "y", "h", "n", "u", "j", "m", "i", "k", "o", "l", "p" };

    public String s = "";

    public List<String> list;

    @Param(value = { "1000", "10000", "100000" })
    int next;

    @TearDown(Level.Invocation)
    public void tearDown() {
        s = null;
    }

    @Setup(Level.Invocation)
    public void setUp() {

         list = ThreadLocalRandom.current()
                .ints(next, 0, letters.length)
                .mapToObj(x -> letters[x])
                .map(x -> Character.toString((char) x.intValue()))
                .collect(Collectors.toList());

    }
}


@Fork(1)
@Benchmark
public List<String> testCollection(StringInput si){
    Collections.sort(si.list, Comparator.naturalOrder());
    return si.list;
}

@Fork(1)
@Benchmark
public List<String> testStream(StringInput si){
    return si.list.stream()
            .sorted(Comparator.naturalOrder())
            .collect(Collectors.toList());
}

结果表明: Collections.sort 速度更快,但幅度不大:

Benchmark                                 (next)  Mode  Cnt   Score   Error  Units
streamvsLoop.StreamVsLoop.testCollection    1000  avgt    2   0.038          ms/op
streamvsLoop.StreamVsLoop.testCollection   10000  avgt    2   0.599          ms/op
streamvsLoop.StreamVsLoop.testCollection  100000  avgt    2  12.488          ms/op
streamvsLoop.StreamVsLoop.testStream        1000  avgt    2   0.048          ms/op
streamvsLoop.StreamVsLoop.testStream       10000  avgt    2   0.808          ms/op
streamvsLoop.StreamVsLoop.testStream      100000  avgt    2  15.652          ms/op

可以肯定地说,两种排序形式将具有相同的复杂性。。。即使不看代码。(如果他们不这样做,那么一个表单将被严重破坏!)

查看流的Java 8源代码(特别是内部类 java.util.stream.SortedOps ),则 sorted() 方法将组件添加到流管道中,该流管道将所有流元素捕获到数组或 ArrayList 。

• 当且仅当管道程序集代码可以提前推断流中的元素数时,才使用数组。

• 否则 阵列列表 用于收集要排序的元素。

如果 阵列列表 如果使用,则会产生创建/增加列表的额外开销。

然后我们返回两个版本的代码:

List<Item> sortedItems = new ArrayList<>(items);
Collections.sort(sortedItems, itemComparator);

在此版本中 阵列列表 构造函数复制元素 items 到适当大小的阵列,然后 Collections.sort 执行该数组的就地排序。(这种情况发生在隐蔽处)。

List<Item> sortedItems = items
    .stream()
    .sorted(itemComparator)
    .collect(Collectors.toList());

在这个版本中,如上所述,与 已排序() 要么构建并排序一个数组(相当于上面发生的事情),要么构建 阵列列表 缓慢的方式。但除此之外,还有数据流的开销 项目 和收集器。

总体而言(至少在Java 8实现的情况下)代码检查告诉我,第一个版本的代码不能比第二个版本慢,并且在大多数(如果不是所有)情况下,它会更快。但随着名单越来越大 O(NlogN) 排序将倾向于主导 O(N) 复制的间接费用。这意味着 相对的 这两个版本之间的差异将变小。

如果您真的在意,那么应该编写一个基准测试,以测试与特定Java实现和特定输入数据集的实际差异。(或者改编@Eugene的基准!)

以下是我的基准(不确定是否正确):

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OperationsPerInvocation;
import org.openjdk.jmh.annotations.OutputTimeUnit;

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(MyBenchmark.N)
public class MyBenchmark {

    public static final int N = 50;

    public static final int SIZE = 100000;

    static List<Integer> sourceList = new ArrayList<>();
    static {
        System.out.println("Generating the list");
        for (int i = 0; i < SIZE; i++) {
            sourceList.add(i);
        }
        System.out.println("Shuffling the list.");
        Collections.shuffle(sourceList);
    }

    @Benchmark
    public List<Integer> sortingList() {
        List<Integer> sortedList = new ArrayList<>(sourceList);
        Collections.sort(sortedList);
        return sortedList;
    }

    @Benchmark
    public List<Integer> sortedStream() {
        List<Integer> sortedList = sourceList.stream().sorted().collect(Collectors.toList());
        return sortedList;
    }

    @Benchmark
    public List<Integer> treeSet() {
        Set<Integer> sortedSet = new TreeSet<>(sourceList);
        List<Integer> sortedList = new ArrayList<>(sortedSet);
        return sortedList;
    }
}

结果:

Benchmark                 Mode  Cnt       Score       Error  Units
MyBenchmark.sortedStream  avgt  200  300691.436 ± 15894.717  ns/op
MyBenchmark.sortingList   avgt  200  262704.939 ±  5073.915  ns/op
MyBenchmark.treeSet       avgt  200  856577.553 ± 49296.565  ns/op

在@Eugene的基准测试中,排序列表比排序流快一点(约20%)。让我有点惊讶的是 treeSet 速度明显较慢。我没想到会这样。