斯卡拉 - 线性时间的地图和过滤操作？

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

斯卡拉 - 线性时间的地图和过滤操作？

回答

相关问题