java什么更有效：排序流还是排序列表？

Question

假设我们在一个集合中有一些项目，并且我们希望使用某个比较器对它们进行排序，期望得到一个列表：

Collection<Item> items = ...;
Comparator<Item> itemComparator = ...;

其中一种方法是对列表中的项目进行排序，如：

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

Ano该方法使用排序流：

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

我想知道，哪种方法更有效？排序流（如多核上的faste排序）有什么优点吗

在运行时复杂性/最快速度方面高效

我不相信自己能实现一个完美的benchmark，学习SortedOps并没有真正启发我

Answer 1

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

查看流（特别是内部类java.util.stream.SortedOps）的Java8源代码，sorted()方法向流管道添加一个组件，该组件将所有流元素捕获到数组或ArrayList中

• 当且仅当管道汇编代码可以提前推断流中的元素数时，才使用数组

• 否则，将使用ArrayList来收集要排序的元素

如果使用了ArrayList，则会产生构建/扩展列表的额外开销

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

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

在这个版本中，ArrayList构造函数将元素items复制到一个大小合适的数组中，然后Collections.sort对该数组进行就地排序。（这种情况发生在封面下）

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

在这个版本中，正如我们上面所看到的，与sorted()相关联的代码要么构建并排序一个数组（相当于上面发生的事情），要么以缓慢的方式构建ArrayList。但除此之外，还有将数据从items流到收集器的开销

总的来说（至少在Java8实现的情况下）代码检查告诉我，第一个版本的代码不能比第二个版本慢，并且在大多数情况下（如果不是全部的话）它会更快。但是，随着列表变得越来越大，O(NlogN)排序将倾向于控制复制的O(N)开销。这将意味着两个版本之间的相对差异将变小

如果您真的关心这个问题，那么应该编写一个基准测试，用特定的Java实现和特定的输入数据集来测试实际的差异。（或者改编@Eugene的基准！）

Answer 2

老实说，我在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

Answer 3

以下是我的基准（不确定是否正确）：

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的速度要慢得多。我没有料到