2

Scala 是在线性时间内映射和过滤操作,还是像数组这样的数据结构在后台有一些并行性?

4

2 回答 2

16

独立于并行性,map操作filter总是必须至少O(n)完成n集合中元素数量的工作。如果集合是例如Array, List, ArrayBuffer, HashMapor HashSet, 那么filterandmap工作O(n)。对于像平衡树这样的特定集合 - 例如mutable.TreeSet、或immutable.TreeMap,and需要时间,因为随着集合的增长,更新它们以添加所有元素需要越来越多的工作。immutable.HashSetimmutable.VectorfiltermapO(n logn)

与遍历所有元素需要多少工作无关,许多 Scala 集合(通常基于树、映射、尝试和数组的集合)支持并行filtermap,因此每个处理器完成的工作总量为O(n / p),其中p是处理器的数量你的机器有。要使用它们,请在调用或par之前调用集合。filtermap

在此处阅读有关并行集合的更多信息。

于 2013-11-01T21:52:37.840 回答
8

不,根本没有并行性,除非你正在做有点明确的并行集合。即使具有并行性,映射和过滤器也是线性时间操作(但分布在许多工作人员中)

于 2013-11-01T21:50:58.110 回答