斯卡拉性能問題

Question

在article written by Daniel Korzekwa，他說，下面的代碼性能：

list.map(e => e*2).filter(e => e>10) 

比使用Java編寫的迭代求解更糟。

任何人都可以解釋爲什麼嗎？在Scala中這樣的代碼的最佳解決方案是什麼（我希望它不是一個Java迭代版本，它是Scala-fied）？

Answer 1

原因該特定的代碼是緩慢的，因爲它的工作對原語，但它使用通用的操作，因此，元都被裝箱。 （如果List及其祖先專門化，這可以得到改進。）這可能會使事情減慢5倍左右。

此外，算法，這些操作是比較昂貴的，因爲你犯了一個完整列表，然後做出一個全新的列表投擲中間列表的幾個組件之遙。如果你一舉成功，那麼你會過得更好。你可以這樣做：

list collect (case e if (e*2>10) => e*2) 

但如果計算e*2是真的很貴？那麼你可以

(List[Int]() /: list)((ls,e) => { val x = e*2; if (x>10) x :: ls else ls } 

除了這會出現倒退。 （如果需要的話，你可以反轉它，但是這需要創建一個新的列表，這在算法上又不是理想的。）

當然，如果你單獨使用Java，你有相同的算法問題鏈表 - 你的新列表將最終倒退，或者你必須創建兩次，第一次反向，然後轉發，或者你必須建立它（非尾）遞歸（這在Scala中很容易，但不適用於因爲你會用盡任何一種語言），或者你必須創建一個可變列表，然後假裝它不可變。 （順便說一句，你也可以在Scala中做 - 也可以參考mutable.LinkedList。）

Answer 2

基本上它的遍歷兩次的列表。一次用於將每個元素與兩個元素相乘。然後再過一次來過濾結果。

把它看成是一個while循環產生與中間結果的鏈表。然後另一個循環應用過濾器來產生最終結果。

這應該是更快：

list.view.map(e => e * 2).filter(e => e > 10).force 

Answer 3

Rex Kerr正確地說明了主要問題：在不可變列表上操作，指定的一段代碼在內存中創建中間列表。請注意，這不一定比等效的Java代碼慢;你永遠不會在Java中使用不可變的數據結構。

維爾弗裏德施普林格有一個很好的，斯卡拉idomatic解決方案。使用view，不會創建整個列表的（操縱）副本。

注意，使用視圖可能並不總是很理想。例如，如果您的第一個電話是filter，預計會拋棄大部分列表，則可能需要明確創建較短的版本，並且僅在此之後才使用view，以便提高以後迭代的內存局部性。

Answer 4

Scala的方法是更加抽象和通用。因此很難優化每一個案例。

我可以想象，如果HotSpot JIT編譯器看到未使用直接結果，它可能會在未來將代碼應用於流和循環融合。

此外，Java代碼只是做了更多。

如果你真的只想改變數據結構，請考慮transform。 它看起來有點像map但不會創建一個新的集合，摹：

val array = Array(1,2,3,4,5,6,7,8,9,10).transform(_ * 2) 
// array is now WrappedArray(2, 4, 6, 8, 10, 12, 14, 16, 18, 20) 

我真的希望一些額外的就地操作將離子將來添加...

Answer 5

爲了避免遍歷列表兩次，我覺得for語法是一個不錯的選擇在這裏：

val list2 = for(v <- list1; e = v * 2; if e > 10) yield e 

Answer 6

解決方案主要是使用JVM。雖然Scala在@specialization這個數字中有一個解決方法，但是這會大大增加任何專門的類的大小，並且只能解決一半的問題 - 另一半是創建臨時對象。 JVM實際上做了很多優化，或者性能會更糟糕，但是Java並不需要Scala所做的優化，因此JVM不提供它們。我期望通過在Java中引入SAM非實際關閉來改變某種程度。

但最終，它歸結爲平衡需求。循環Java和Scala比Scala的功能等效的速度快得多，但在C語言中可以更快地完成。然而，儘管微型基準告訴我們，人們使用Java。

Answer 7

list.filter（E => E * 2> 10）.MAP（E => E * 2）

這種嘗試首先降低了列表。所以第二次遍歷的元素少。