Arrays.stream（array_name）.sum（）比迭代方法慢吗？
我编写了一个leetcode问题： https ：//ooj.leetcode.com/problems/gas-station/使用Java 8。
当我使用Arrays.stream(integer_array).sum()来计算求和时，我的解决方案得到了TLE，同时使用迭代来接受相同的解决方案来计算数组中元素的总和。 这个问题的最佳时间复杂度是O（n），当我使用Java 8中的流API时，我很惊讶得到TLE。我只在O（n）中实现了解决方案。
import java.util.Arrays; public class GasStation { public int canCompleteCircuit(int[] gas, int[] cost) { int start = 0, i = 0, runningCost = 0, totalGas = 0, totalCost = 0; totalGas = Arrays.stream(gas).sum(); totalCost = Arrays.stream(cost).sum(); // for (int item : gas) totalGas += item; // for (int item : cost) totalCost += item; if (totalGas i || (start == 0 && i = cost[i]) { runningCost -= cost[i++]; } else { runningCost -= gas[i]; if (--start < 0) start = gas.length - 1; runningCost += (gas[start] - cost[start]); } } return start; } public static void main(String[] args) { GasStation sol = new GasStation(); int[] gas = new int[] { 10, 5, 7, 14, 9 }; int[] cost = new int[] { 8, 5, 14, 3, 1 }; System.out.println(sol.canCompleteCircuit(gas, cost)); gas = new int[] { 10 }; cost = new int[] { 8 }; System.out.println(sol.canCompleteCircuit(gas, cost)); } }
解决方案被接受时，我评论以下两行:(使用流量计算总和）
totalGas = Arrays.stream(gas).sum(); totalCost = Arrays.stream(cost).sum();
并取消注释以下两行（使用迭代计算总和）：
//for (int item : gas) totalGas += item; //for (int item : cost) totalCost += item;
现在解决方案被接受了。 为什么Java 8中的流API对于大型输入而言比基元的迭代慢？
处理这类问题的第一步是将代码置于受控环境中。 这意味着在您控制（并且可以调用）的JVM中运行它并在JMH之类的良好基准测试中运行测试。 分析，不要推测。
这是我使用JMH对此进行分析的基准测试：
@BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.MICROSECONDS) @State(Scope.Benchmark) public class ArraySum { static final long SEED = -897234L; @Param({"1000000"}) int sz; int[] array; @Setup public void setup() { Random random = new Random(SEED); array = new int[sz]; Arrays.setAll(array, i -> random.nextInt()); } @Benchmark public int sumForLoop() { int sum = 0; for (int a : array) sum += a; return sum; } @Benchmark public int sumStream() { return Arrays.stream(array).sum(); } }
基本上，这会创建一个百万个整数的数组，并将它们相加两次：一次使用for循环，一次使用流。 运行基准测试会产生一堆输出（为简洁和显着效果而省略），但摘要结果如下：
Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 3 514.473 398.512 us/op ArraySum.sumStream 1000000 avgt 3 7355.971 3170.697 us/op
哇！ 那个Java 8流的东西就是SUXX0R！ 它比for-loop慢14倍，不要使用!!! 1！
好吧，不。 首先让我们回顾一下这些结果，然后仔细观察，看看我们是否可以弄清楚发生了什么。
摘要显示了两个基准测试方法，其中“sz”参数为百万。 可以改变这个参数，但在这种情况下不会产生影响。 我也只运行了3次基准测试方法，正如您可以从“样本”列中看到的那样。 （也只有3次预热迭代，这里不可见。）每次操作得分为微秒，显然流代码比for循环代码要慢得多。 但请注意分数误差：这是不同运行中的变化量。 JMH帮助打印出结果的标准偏差（此处未显示），但您可以很容易地看到分数误差是报告分数的重要部分。 这降低了我们对得分的信心。
运行更多迭代应该有所帮助。 更多的热身迭代将让JIT在运行基准测试之前做更多工作并稳定下来，并且运行更多基准测试迭代将消除系统中其他位置的瞬态活动的任何错误。 那么让我们尝试10次预热迭代和10次基准迭代：
Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 10 504.803 34.010 us/op ArraySum.sumStream 1000000 avgt 10 7128.942 178.688 us/op
性能总体上要快一些，测量误差也要小得多，因此运行更多迭代会产生预期的效果。 但是流代码仍然比for循环代码慢得多。 这是怎么回事？
通过查看流方法的各个时序可以获得大线索：
# Warmup Iteration 1: 570.490 us/op # Warmup Iteration 2: 491.765 us/op # Warmup Iteration 3: 756.951 us/op # Warmup Iteration 4: 7033.500 us/op # Warmup Iteration 5: 7350.080 us/op # Warmup Iteration 6: 7425.829 us/op # Warmup Iteration 7: 7029.441 us/op # Warmup Iteration 8: 7208.584 us/op # Warmup Iteration 9: 7104.160 us/op # Warmup Iteration 10: 7372.298 us/op
发生了什么？ 前几次迭代相当快，但随后第四次和随后的迭代（以及随后的所有基准迭代）突然变得非常慢。
我以前见过这个。 正是在这个问题和其他地方的答案上。 我建议阅读那个答案; 它解释了JVM在这种情况下的内联决策如何导致较差的性能。
这里有一点背景：for循环编译成一个非常简单的增量和测试循环，并且可以通过循环剥离和展开等常用优化技术轻松处理。 在这种情况下，流代码虽然不是很复杂，但实际上与for循环代码相比非常复杂; 有一些设置，每个循环至少需要一个方法调用。 因此，JIT优化，特别是其内联决策，对于使流代码快速运行至关重要。 它可能会出错。
另一个背景点是整数求和是关于在循环或流中可以想到的最简单的操作。 这将使得流设置的固定开销看起来相对更昂贵。 它也很简单，它可以触发内联策略中的病态。
另一个答案的建议是添加JVM选项-XX:MaxInlineLevel=12以增加可以内联的代码量。 使用该选项重新运行基准测试可以：
Benchmark (sz) Mode Samples Score Score error Units ArraySum.sumForLoop 1000000 avgt 10 502.379 27.859 us/op ArraySum.sumStream 1000000 avgt 10 498.572 24.195 us/op
啊，好多了。 使用-XX:-TieredCompilation禁用分层编译-XX:-TieredCompilation也具有避免病态行为的效果。 我还发现使循环计算更加昂贵，例如求整数的平方 – 即添加单个乘法 – 也避免了病态行为。
现在，您的问题是在leetcode环境的上下文中运行，该环境似乎在您无法控制的JVM中运行代码，因此您无法更改内联或编译选项。 并且您可能不希望使计算更复杂以避免病理学。 所以对于这种情况，你可能只是坚持好的旧循环。 但是不要害怕使用流，即使是处理原始数组。 除了一些狭窄的边缘情况，它可以表现得相当好。
正常的迭代方法几乎和任何东西一样快，但是流有各种各样的开销：即使它直接来自流，也可能会涉及原始的Spliterator并且会生成许多其他对象。
通常，您应该期望“正常方法” 通常比流更快，除非您使用并行化并且数据非常大。
我的基准测试（参见下面的代码）表明，流式方法比迭代慢约10-15％。 有趣的是，并行流的结果在我的4核（i7）macbook pro上变化很大，但是，虽然我看到它们几次比迭代快约30％，但最常见的结果几乎比顺序慢三倍。
这是基准代码：
import java.util.*; import java.util.function.*; public class StreamingBenchmark { private static void benchmark(String name, LongSupplier f) { long start = System.currentTimeMillis(), sum = 0; for(int count = 0; count < 1000; count ++) sum += f.getAsLong(); System.out.println(String.format( "%10s in %d millis. Sum = %d", name, System.currentTimeMillis() - start, sum )); } public static void main(String argv[]) { int data[] = new int[1000000]; Random randy = new Random(); for(int i = 0; i < data.length; i++) data[i] = randy.nextInt(); benchmark("iterative", () -> { int s = 0; for(int n: data) s+=n; return s; }); benchmark("stream", () -> Arrays.stream(data).sum()); benchmark("parallel", () -> Arrays.stream(data).parallel().sum()); } }
以下是几次运行的输出：
iterative in 350 millis. Sum = 564821058000 stream in 394 millis. Sum = 564821058000 parallel in 883 millis. Sum = 564821058000 iterative in 340 millis. Sum = -295411382000 stream in 376 millis. Sum = -295411382000 parallel in 1031 millis. Sum = -295411382000 iterative in 365 millis. Sum = 1205763898000 stream in 379 millis. Sum = 1205763898000 parallel in 1053 millis. Sum = 1205763898000
等等
这让我很好奇，我也尝试在scala中运行等效的逻辑：
object Scarr { def main(argv: Array[String]) = { val randy = new java.util.Random val data = (1 to 1000000).map { _ => randy.nextInt }.toArray val start = System.currentTimeMillis var sum = 0l; for ( _ <- 1 to 1000 ) sum += data.sum println(sum + " in " + (System.currentTimeMillis - start) + " millis.") } }
这花了14秒 ！ 比java中的流式传输长约40倍（！）。 哎哟!
sum（）方法在语法上等效于return reduce(0, Integer::sum); 在一个大型列表中，进行所有方法调用的开销将超过基本的手动for循环迭代。 for(int i : numbers)迭代的字节代码只比手工for循环生成的字节代码稍微复杂一些。 在并行友好的环境中，流操作可能更快（尽管可能不适用于原始方法），但除非我们知道环境是并行友好的（并且它可能不是因为leetcode本身可能设计为支持低级而不是抽象因为它是衡量效率而不是易读性。
以三种方式中的任何一种（ Arrays.stream(int[]).sum ， for (int i : ints){total+=i;}和for(int i = 0; i < ints.length; i++){total+=i;}应该在效率上相对相似。我使用了下面的测试类（它在0到4096之间for(int i = 0; i < ints.length; i++){total+=i;}了1亿个整数，每次记录100次，并记录平均时间）。所有这些都返回非常相似它甚至试图通过占用while（true）循环中除了一个可用内核之外的所有内核来限制并行处理，但我仍然没有发现特别的区别：
public class SumTester { private static final int ARRAY_SIZE = 100_000_000; private static final int ITERATION_LIMIT = 100; private static final int INT_VALUE_LIMIT = 4096; public static void main(String[] args) { Random random = new Random(); int[] numbers = new int[ARRAY_SIZE]; IntStream.range(0, ARRAY_SIZE).forEach(i->numbers[i] = random.nextInt(INT_VALUE_LIMIT)); Map> inputs = new HashMap>(); NanoTimer initializer = NanoTimer.start(); System.out.println("initialized NanoTimer in " + initializer.microEnd() + " microseconds"); inputs.put("sumByStream", SumTester::sumByStream); inputs.put("sumByIteration", SumTester::sumByIteration); inputs.put("sumByForLoop", SumTester::sumByForLoop); System.out.println("Parallelables: "); averageTimeFor(ITERATION_LIMIT, inputs, Arrays.copyOf(numbers, numbers.length)); int cores = Runtime.getRuntime().availableProcessors(); List threadEaters = new ArrayList (); if (cores > 1){ threadEaters = occupyThreads(cores - 1); } // Only one core should be left to our class System.out.println("\nSingleCore (" + threadEaters.size() + " of " + cores + " cores occupied)"); averageTimeFor(ITERATION_LIMIT, inputs, Arrays.copyOf(numbers, numbers.length)); for (CancelableThreadEater cte : threadEaters){ cte.end(); } System.out.println("Complete!"); } public static long sumByStream(int[] numbers){ return Arrays.stream(numbers).sum(); } public static long sumByIteration(int[] numbers){ int total = 0; for (int i : numbers){ total += i; } return total; } public static long sumByForLoop(int[] numbers){ int total = 0; for (int i = 0; i < numbers.length; i++){ total += numbers[i]; } return total; } public static void averageTimeFor(int iterations, Map> testMap, int[] numbers){ Map durationMap = new HashMap(); Map sumMap = new HashMap(); for (String methodName : testMap.keySet()){ durationMap.put(methodName, 0L); sumMap.put(methodName, 0L); } for (int i = 0; i < iterations; i++){ for (String methodName : testMap.keySet()){ int[] newNumbers = Arrays.copyOf(numbers, ARRAY_SIZE); ToLongFunction function = testMap.get(methodName); NanoTimer nt = NanoTimer.start(); long sum = function.applyAsLong(newNumbers); long duration = nt.microEnd(); sumMap.put(methodName, sum); durationMap.put(methodName, durationMap.get(methodName) + duration); } } for (String methodName : testMap.keySet()){ long duration = durationMap.get(methodName) / iterations; long sum = sumMap.get(methodName); System.out.println(methodName + ": result '" + sum + "', elapsed time: " + duration + " milliseconds on average over " + iterations + " iterations"); } } private static List occupyThreads(int numThreads){ List result = new ArrayList (); for (int i = 0; i < numThreads; i++){ CancelableThreadEater cte = new CancelableThreadEater(); result.add(cte); new Thread(cte).start(); } return result; } private static class CancelableThreadEater implements Runnable { private Boolean stop = false; public void run(){ boolean canContinue = true; while (canContinue){ synchronized(stop){ if (stop){ canContinue = false; } } } } public void end(){ synchronized(stop){ stop = true; } } } }
哪个回来了
initialized NanoTimer in 22 microseconds Parallelables: sumByIteration: result '-1413860413', elapsed time: 35844 milliseconds on average over 100 iterations sumByStream: result '-1413860413', elapsed time: 35414 milliseconds on average over 100 iterations sumByForLoop: result '-1413860413', elapsed time: 35218 milliseconds on average over 100 iterations SingleCore (3 of 4 cores occupied) sumByIteration: result '-1413860413', elapsed time: 37010 milliseconds on average over 100 iterations sumByStream: result '-1413860413', elapsed time: 38375 milliseconds on average over 100 iterations sumByForLoop: result '-1413860413', elapsed time: 37990 milliseconds on average over 100 iterations Complete!
也就是说，在这种情况下没有真正的理由进行sum（）操作。 您正在迭代每个数组，总共三次迭代，最后一次可能是一次比正常更长的迭代。 通过一个完整的同时迭代的数组和一个短路迭代，可以正确计算。 有可能更有效地做到这一点，但我无法找到比我做得更好的方法。 我的解决方案最终成为图表上最快的java解决方案之一 - 它运行在223ms，这是python解决方案的中间包。
如果你愿意，我会在问题上添加我的解决方案，但我希望这里能回答实际的问题。