java - 为什么流这么快

Question

这个问题已经有答案了:

How do I write a correct micro-benchmark in Java? (11 个回答)

已关闭 6 年前。

我试图实现 Coursera 的一个程序。程序语句为:

给定一个非负整数序列 a0,…,an−1，找到最大成对乘积，即序列中两个不同元素相乘可获得的最大整数。

我尝试了各种方法来实现该解决方案，并检查哪种方法最有效。

我发现流仍然很快。

为什么会这样？

我的印象是，找到最大的 2 个元素而不对其进行排序和相乘将是最好的。流排序(顺序流比并行流更快)给出的结果比这种方法更好？

我的程序

    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.List;
    import java.util.Random;
    import java.util.stream.Collectors;

    public class MaxProduct {
        public static void main(String[] args) {
            List<Long> testList = createRandomArrayOfSize(30000000);

            warmup(testList);
            System.out.println("Warmup done");

            Measure.meaureTime("No sorting, finding largest 2 elements and multiplying",
                    () -> findMaxProductByFindingLargest2Elements(new ArrayList<>(testList)));
            Measure.meaureTime("Sorting, Multiplying last 2 elements",
                    () -> findMaxProductUsingSorting(new ArrayList<>(testList)));
            Measure.meaureTime("Sorting using streams, Multiplying last 2 elements",
                    () -> findMaxProductUsingStreamSorting(new ArrayList<>(testList)));
            Measure.meaureTime("Parallel sorting using streams, Multiplying last 2 elements by reduction",
                    () -> findMaxProductReducingParallelStream(new ArrayList<>(testList)));
        }

        public static long findMaxProductByFindingLargest2Elements(List<Long> list) {
            long largest = 0;
            long secondlargest = 0;
            for (Long no : list) {
                if (no > largest) {
                    secondlargest = largest;
                    largest = no;
                }
            }
            return largest * secondlargest;
        }

        public static long findMaxProductUsingSorting(List<Long> list) {
            list.sort(Comparator.naturalOrder());
            return list.get(list.size() - 1) * list.get(list.size() - 2);
        }

        public static long findMaxProductUsingStreamSorting(List<Long> list) {
            List<Long> collect = list.stream().sorted(Comparator.naturalOrder()).collect(Collectors.toList());
            return collect.get(list.size() - 1) * collect.get(list.size() - 2);
        }

        public static long findMaxProductReducingParallelStream(List<Long> list) {
            return list.parallelStream().sorted(Comparator.reverseOrder()).limit(2).reduce((x, y) -> x * y).get();
        }

        private static class Measure {
            private static final int NO_OF_ITERATIONS = 3;

            private static void meaureTime(String description, Runnable runnable) {
                long startTime = System.nanoTime();
                for (int i = 0; i < NO_OF_ITERATIONS; i++) {
                    runnable.run();
                }
                long timeTakenInNanos = System.nanoTime() - startTime;
                System.out.println(description + " : " + (timeTakenInNanos / 3));
            }
        }

        private static void warmup(List<Long> testList) {
            findMaxProductByFindingLargest2Elements(new ArrayList<>(testList));
            findMaxProductUsingSorting(new ArrayList<>(testList));
            findMaxProductUsingStreamSorting(new ArrayList<>(testList));
            findMaxProductReducingParallelStream(new ArrayList<>(testList));
        }

        private static List<Long> createRandomArrayOfSize(int size) {
            return new Random().longs(size, 1, 10000000).boxed().collect(Collectors.toList());
        }
    }

更新结果

不排序，找到最大的 2 个元素并相乘:778547847
排序、最后 2 个元素相乘:13423659115
使用流排序，将最后 2 个元素相乘:15518997158
使用流进行并行排序，将最后 2 个元素乘以归约:5405983848

更新了代码

第一种方法存在错误。如果最大的 no 位于第零个索引，则乘积将为零。需要解决这个问题。

流媒体速度不快
我的测试代码中有一个错误。修正了错误。现在按预期工作。

Answer 1

不幸的是，流不一定很快。

findMaxProductUsingStreamSorting 指定一个 Stream，但未使用 collect 或 findFirst 实现它。它不会改变列表。因此，只会完成两个列表获取的乘积。结果也会是错误的。

对于 Stream，迭代是在较晚的时候完成的，因此排序、过滤等可能有助于巧妙的执行。