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 是您机器的处理器数量。要使用它们，请在调用 filter 或 map 之前调用集合上的 par。

阅读更多关于 parallel collections here 的信息.