Scala - 是线性时间内的映射和过滤操作吗？

Question

Scala是否在线性时间内映射和过滤操作,或者数据库之类的数据结构是否存在一些并行性？

Answer 1

独立并行的,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是处理器的数量你的机器有.要使用它们调用par之前调用上收集filter或map.

了解更多关于此并行的集合.

Answer 2

不,没有任何并行性,除非你正在进行有点明确的并行集合.即使具有并行性,映射和过滤器也是线性时间操作(但在许多工作者之间传播)