Scala 是在线性时间内映射和过滤操作,还是像数组这样的数据结构在后台有一些并行性?
问问题
1255 次
2 回答
16
独立于并行性,map
操作filter
总是必须至少O(n)
完成n
集合中元素数量的工作。如果集合是例如Array
, List
, ArrayBuffer
, HashMap
or HashSet
, 那么filter
andmap
工作O(n)
。对于像平衡树这样的特定集合 - 例如mutable.TreeSet
、或immutable.TreeMap
,and需要时间,因为随着集合的增长,更新它们以添加所有元素需要越来越多的工作。immutable.HashSet
immutable.Vector
filter
map
O(n logn)
与遍历所有元素需要多少工作无关,许多 Scala 集合(通常基于树、映射、尝试和数组的集合)支持并行filter
和map
,因此每个处理器完成的工作总量为O(n / p)
,其中p
是处理器的数量你的机器有。要使用它们,请在调用或par
之前调用集合。filter
map
在此处阅读有关并行集合的更多信息。
于 2013-11-01T21:52:37.840 回答
8
不,根本没有并行性,除非你正在做有点明确的并行集合。即使具有并行性,映射和过滤器也是线性时间操作(但分布在许多工作人员中)
于 2013-11-01T21:50:58.110 回答