Whys流如此之快

我試圖從Coursera實現一個程序。程序語句如下：Whys流如此之快

給定一個非負整數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
使用str的並行排序EAMS，通過還原乘以最後2個元件：5405983848

更新了代碼

有在第一種方法中的錯誤。如果最大的「否」處於第零指數，則產品將爲零。需要解決這個問題。

流不快
在我的測試代碼中是一個錯誤。修正了錯誤。現在按預期工作。

來源

2016-08-11 Paul Nibin

哪個課程??? –

https://www.coursera.org/learn/algorithmic-toolbox –

我仍然看到一些問題。 1）調用'warmup'後，您的列表會被排序。 2）您比較的功能不會給出相同的結果。 3）請參閱http://stackoverflow.com/q/504103/2568885瞭解如何編寫微型基準。 – binoternary

您的測試存在缺陷。你運行流測試的時間已經排序，這就是爲什麼它很快。

來源

2016-08-11 14:40:55 macsniper

謝謝。將修復它，然後再試一次。 –

@PaulNibin它不是固定的。您的'measureTime'做了多次迭代，並且它們之間的列表沒有重置。 – davmac

最初的問題是「爲什麼會這樣？」。我的回答（在他改變他的問題之前）提供了他的問題的答案。 – macsniper

不幸的是流並不一定是快速的。

findMaxProductUsingStreamSorting指定了一個Stream，但沒有用collect或findFirst來實現。它不會改變列表。因此只有兩個列表的產物纔會完成。結果也是錯誤的。

隨着流的迭代是遲到，所以排序，過濾等，可能會使聰明的執行。

來源

2016-08-11 15:40:01

謝謝。修正了這個錯誤。現在流不再快了。需要處理我的代碼審查技能。 –

Whys流如此之快

回答

相關問題