斯卡拉 - 線性時間的地圖和過濾操作？

Scala是否在線性時間映射和過濾操作，還是像數組這樣的數據結構下有一些並行性？斯卡拉 - 線性時間的地圖和過濾操作？

2013-11-01 Walrus the Cat

不，完全沒有平行性，除非你在做parallel collections這是一個很明確。即使並行，地圖和過濾器是線性時間的操作（但許多工人中傳播）

2013-11-01 21:50:58

獨立並行的，map和filter操作總是要做的至少O(n)工作，其中n是集合中元素的個數。如果集合是例如Array,List,ArrayBuffer,HashMap或HashSet，然後filter和map做O(n)工作。對於像平衡樹木這樣的特定集合 - 例如mutable.TreeSet，immutable.TreeMap,immutable.HashSet或immutable.Vector,filter和map取O(n logn)時間，因爲更新它們以添加所有元素隨着集合增長需要越來越多的工作。

獨立的多少工作所需遍歷所有元件，許多Scala集合（通常是基於樹，地圖，嘗試和陣列）支持並行filter和map，所以工作的每個處理器所做的總量爲O(n/p) ，其中p是您的機器具有的處理器數量。在致電filter或map之前，要在集合上使用它們請致電par。

查看更多about parallel collections here。

來源

2013-11-01 21:52:37 axel22

我喜歡你的答案中的所有內容，但我會接受另一個，因爲它的簡潔與我使用StackOverflow很好地協同工作。不過，我鼓勵你。 –

我對第二段中的陳述有所質疑：「完成的工作量是O（n/p）'。」這是不正確的。工作總量仍然是「O（n）」。然而，完成的時間是'O（n/p）'。當然，它確實是'Ω（n/p）'，因爲同時執行的計算的概念獨立性實際上是通過使用共享高速緩存和RAM來相互干擾的。 –

我編輯了「全部工作」部分，你說得對。當然，關於干擾，這是一個理論模型，不能反映某些特定硬件的細節。 – axel22

斯卡拉 - 線性時間的地圖和過濾操作？

回答

相關問題