并行集合

具体并行集合类

并行数组

一个 ParArray 序列包含一个元素的线性连续数组。这意味着可以通过修改底层数组来高效地访问和更新元素。出于这个原因，遍历元素也非常高效。并行数组类似于数组，因为它们的大小是常量。

scala> val pa = scala.collection.parallel.mutable.ParArray.tabulate(1000)(x => 2 * x + 1)
pa: scala.collection.parallel.mutable.ParArray[Int] = ParArray(1, 3, 5, 7, 9, 11, 13,...

scala> pa reduce (_ + _)
res0: Int = 1000000

scala> pa map (x => (x - 1) / 2)
res1: scala.collection.parallel.mutable.ParArray[Int] = ParArray(0, 1, 2, 3, 4, 5, 6, 7,...

在内部，拆分并行数组拆分器等同于创建两个新的拆分器，并更新它们的迭代索引。组合器稍显复杂。由于对于大多数转换器方法（例如 flatMap、filter、takeWhile 等），我们事先不知道元素的数量（因此也不知道数组的大小），因此每个组合器本质上都是数组缓冲区的变体，具有摊销常数时间 += 操作。不同的处理器将元素添加到单独的并行数组组合器中，然后通过链接它们的内部数组来组合这些组合器。底层数组仅在元素总数已知后才分配并并行填充。出于这个原因，转换器方法比访问器方法稍贵。此外，请注意，最终的数组分配在 JVM 上按顺序进行，因此如果映射操作本身非常便宜，这可能会成为顺序瓶颈。

通过调用 seq 方法，并行数组将转换为 ArraySeq 集合，它们是其顺序对应项。此转换很有效，并且 ArraySeq 由与从中获取并行数组相同的底层数组支持。

并行 Vector

ParVector 是一个不可变序列，具有低常数因子对数访问和更新时间。

scala> val pv = scala.collection.parallel.immutable.ParVector.tabulate(1000)(x => x)
pv: scala.collection.parallel.immutable.ParVector[Int] = ParVector(0, 1, 2, 3, 4, 5, 6, 7, 8, 9,...

scala> pv filter (_ % 2 == 0)
res0: scala.collection.parallel.immutable.ParVector[Int] = ParVector(0, 2, 4, 6, 8, 10, 12, 14, 16, 18,...

不可变向量由 32 路树表示，因此拆分器通过将子树分配给每个拆分器来拆分。合并器当前保留一个元素向量，并通过延迟复制元素来合并。因此，转换器方法的可扩展性不如并行数组。一旦向量连接操作在将来的 Scala 版本中可用，合并器将使用连接进行合并，转换器方法将变得更加高效。

并行向量是顺序 Vector 的并行对应项，因此两者之间的转换需要常量时间。

并行范围

ParRange 是一个元素的有序序列，这些元素等距分布。并行范围的创建方式与顺序 Range 类似

scala> (1 to 3).par
res0: scala.collection.parallel.immutable.ParRange = ParRange(1, 2, 3)

scala> (15 to 5 by -2).par
res1: scala.collection.parallel.immutable.ParRange = ParRange(15, 13, 11, 9, 7, 5)

就像顺序范围没有生成器一样，并行范围也没有合并器。映射并行范围的元素会产生并行向量。顺序范围和并行范围可以使用 seq 和 par 方法有效地相互转换。

并行哈希表

并行哈希表将它们的元素存储在底层数组中，并将其放置在由各个元素的哈希码确定的位置。并行可变哈希集 (mutable.ParHashSet) 和并行可变哈希映射 (mutable.ParHashMap) 基于哈希表。

scala> val phs = scala.collection.parallel.mutable.ParHashSet(1 until 2000: _*)
phs: scala.collection.parallel.mutable.ParHashSet[Int] = ParHashSet(18, 327, 736, 1045, 773, 1082,...

scala> phs map (x => x * x)
res0: scala.collection.parallel.mutable.ParHashSet[Int] = ParHashSet(2181529, 2446096, 99225, 2585664,...

并行哈希表合并器根据元素的哈希码前缀将元素分类到各个存储桶中。它们通过简单地将这些存储桶连接在一起来合并。一旦最终哈希表要构建（即调用合并器 result 方法），底层数组将被分配，并且来自不同存储桶的元素将并行复制到哈希表数组的不同连续段中。

可以使用 par 方法将顺序哈希映射和哈希集合转换为其并行变体。并行哈希表在内部需要一个大小映射，用于跟踪哈希表不同块中的元素数量。这意味着，当顺序哈希表第一次转换为并行哈希表时，将遍历该表并创建大小映射 - 因此，对 par 的第一次调用需要与哈希表大小成正比的时间。哈希表的进一步修改将维护大小映射的状态，因此使用 par 和 seq 进行的后续转换具有恒定复杂度。可以使用哈希表中的 useSizeMap 方法来开启和关闭大小映射的维护。重要的是，顺序哈希表中的修改在并行哈希表中可见，反之亦然。

并行哈希树

并行哈希树是不可变哈希树的并行对应项，用于有效表示不可变集合和映射。它们由 immutable.ParHashSet 和 immutable.ParHashMap 类支持。

scala> val phs = scala.collection.parallel.immutable.ParHashSet(1 until 1000: _*)
phs: scala.collection.parallel.immutable.ParHashSet[Int] = ParSet(645, 892, 69, 809, 629, 365, 138, 760, 101, 479,...

scala> phs.map(x => x * x).sum
res0: Int = 332833500

与并行哈希表类似，并行哈希树组合器将元素预先排序到存储桶中，并通过将不同的存储桶分配给不同的处理器来并行构建结果哈希树，这些处理器独立构建子树。

可以通过使用 seq 和 par 方法以恒定时间将并行哈希树转换回顺序哈希树，反之亦然。

并行并发树

concurrent.TrieMap 是一个并发线程安全映射，而 mutable.ParTrieMap 是它的并行对应项。虽然大多数并发数据结构不能保证在遍历期间修改数据结构时进行一致遍历，但 Ctries 保证仅在下次迭代中可见更新。这意味着你可以在遍历并发树时对其进行变异，就像以下输出 1 到 99 的数字平方根的示例中一样

scala> val numbers = scala.collection.parallel.mutable.ParTrieMap((1 until 100) zip (1 until 100): _*) map { case (k, v) => (k.toDouble, v.toDouble) }
numbers: scala.collection.parallel.mutable.ParTrieMap[Double,Double] = ParTrieMap(0.0 -> 0.0, 42.0 -> 42.0, 70.0 -> 70.0, 2.0 -> 2.0,...

scala> while (numbers.nonEmpty) {
     |   numbers foreach { case (num, sqrt) =>
	 |     val nsqrt = 0.5 * (sqrt + num / sqrt)
	 |     numbers(num) = nsqrt
	 |     if (math.abs(nsqrt - sqrt) < 0.01) {
	 |       println(num, nsqrt)
	 |		 numbers.remove(num)
	 |	   }
	 |   }
	 | }
(1.0,1.0)
(2.0,1.4142156862745097)
(7.0,2.64576704419029)
(4.0,2.0000000929222947)
...

组合器在底层实现为 TrieMap - 由于这是一个并发数据结构，因此仅为整个转换器方法调用构建一个组合器，并由所有处理器共享。

与所有并行可变集合一样，通过调用 seq 或 par 方法获得的 TrieMap 和并行 ParTrieMap 由同一存储库支持，因此对一个的修改在另一个中可见。转换以恒定时间发生。

性能特征

序列类型性能特征

	头部	尾部	应用	更新	前置	追加	插入
`ParArray`	C	L	C	C	L	L	L
`ParVector`	eC	eC	eC	eC	eC	eC	-
`ParRange`	C	C	C	-	-	-	-

集合和映射类型性能特征

	查找	添加	移除
不可变
`ParHashSet`/`ParHashMap`	eC	eC	eC
可变
`ParHashSet`/`ParHashMap`	C	C	C
`ParTrieMap`	eC	eC	eC

键

以上两张表中的条目解释如下


C	操作需要（快速）常量时间。
eC	操作需要有效常量时间，但这可能取决于某些假设，例如向量的最大长度或哈希键的分布。
aC	操作需要摊销常量时间。某些操作调用可能需要更长时间，但如果对平均许多操作执行，则每个操作仅需要常量时间。
Log	操作需要与集合大小的对数成正比的时间。
L	操作是线性的，即需要与集合大小成正比的时间。
-	不支持该操作。

第一张表处理序列类型（不可变和可变）以及以下操作


头部	选择序列的第一个元素。
尾部	生成一个新序列，该序列包含除第一个元素之外的所有元素。
应用	索引。
更新	不可变序列的功能更新（使用 `updated`），可变序列的副作用更新（使用 `update`）。
前置	在序列前面添加一个元素。对于不可变序列，这将生成一个新序列。对于可变序列，它将修改现有序列。
追加	在序列末尾添加一个元素。对于不可变序列，这将生成一个新序列。对于可变序列，它将修改现有序列。
插入	在序列中的任意位置插入一个元素。仅可变序列直接支持此操作。

第二个表处理可变和不可变集合和映射，并带有以下操作


查找	测试元素是否包含在集合中，或选择与键关联的值。
添加	向集合中添加新元素或向映射中添加键/值对。
移除	从集合中移除元素或从映射中移除键。
min	集合中最小的元素，或映射中最小的键。