Arrays.stream（array_name）.sum（）比迭代方法慢嗎？

Question

我被編碼本文給出了問題：https://oj.leetcode.com/problems/gas-station/使用Java 8.

我的解決方案得到了TLE當我用Arrays.stream(integer_array).sum()計算總和，而相同的溶液得到了使用迭代計算在陣列元素的總和接受。這個問題的最佳時間複雜度是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 < totalCost) 
      return -1; 

     while (start > i || (start == 0 && i < gas.length)) { 
      runningCost += gas[i]; 
      if (runningCost >= 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中的流媒體API 8對於較大的輸入比基元的迭代要慢？

Answer 1

正常的迭代方法將是非常快，什麼都可以，但流有多種開銷：即使它直接從流過來，還有的可能會是一個原始Spliterator參與和大量的其他物體正在生成。

一般情況下，你應該期待「正常途徑」來除非你使用兩個並行和你的數據量非常大，通常比流得更快。

Answer 2

sum（）方法在語法上等效於return reduce(0, Integer::sum);在大型列表中，進行所有方法調用的開銷比基本的手動循環迭代更多。 for(int i : numbers)迭代的字節碼只比手邊for-loop生成的字節碼複雜得多。在並行友好的環境中，流操作可能會更快（儘管對於原始方法可能不是這樣），但除非我們知道環境是並行友好的（並且可能不是這樣，因爲leetcode本身可能被設計爲傾向於低級抽象因爲它測量的是效率而不是易讀性）。

任何的三種方式（Arrays.stream(int[]).sum，for (int i : ints){total+=i;}和for(int i = 0; i < ints.length; i++){total+=i;}應該是效率比較類似所做的乘加運算。我用下面的測試類（它總結0和4096百倍每間一億整數記錄平均時間），它們都以非常相似的時間段返回，它甚至試圖通過在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<String, ToLongFunction<int[]>> inputs = new HashMap<String, ToLongFunction<int[]>>(); 

     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<CancelableThreadEater> threadEaters = new ArrayList<CancelableThreadEater>(); 
     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<String, ToLongFunction<int[]>> testMap, int[] numbers){ 
     Map<String, Long> durationMap = new HashMap<String, Long>(); 
     Map<String, Long> sumMap = new HashMap<String, Long>(); 
     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<int[]> 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<CancelableThreadEater> occupyThreads(int numThreads){ 
     List<CancelableThreadEater> result = new ArrayList<CancelableThreadEater>(); 
     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解決方案之一 - 它的運行速度爲223毫秒，這是中間包的python解決方案。

如果您關心此問題，我會將我的解決方案添加到該問題中，但希望在此解答實際問題。

Answer 3

我的基準測試（請參閱下面的代碼）顯示，流式方法比迭代式慢大約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倍（！）比流式傳輸更長。哎喲!

Answer 4

處理這類問題的第一步是將代碼放入受控環境中。這意味着在你控制（並可以調用）的JVM中運行它，並在諸如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循環慢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 

發生了什麼事：

大量線索可以通過查看流方法的各個定時獲得？前幾次迭代的速度相當快，但隨後的第四次迭代（以及後面的所有基準迭代）突然變慢。

我以前見過這個。 SO上的其他地方是this question和this answer。我建議閱讀這個答案;它解釋了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禁用分層編譯也具有避免病態行爲的效果。我還發現，使循環計算甚至更昂貴一些，例如求和整數的平方 - 即增加一個乘法 - 也可以避免病態行爲。

現在，您的問題是關於在leetcode環境的環境中運行，它似乎在JVM中運行代碼而您無法控制，因此您無法更改內聯或編譯選項。而且你可能不想讓你的計算更加複雜以避免病態。所以對於這種情況，你可能只需要堅持一個很好的舊for循環。但是不要害怕使用流，即使是處理原始數組。除了一些狹窄的邊緣情況外，它可以表現的很好。