Parallel Collections

# 具体并行集合类

Language

### 并行数组(Parallel Range)

``````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,...
``````

### 并行向量(Parallel Vector)

``````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叉树，因此[分离器]通过将子树分配到每个分离器(spliter)来分离。[组合(combiners)]存储元素的向量并通过懒惰(lazily)拷贝来组合元素。因此，转换方法相对于并行数组来说可伸缩性较差。一旦串联操作在将来scala的发布版本中成为可变的，组合器将会使得串联和变量器方法更加有效率。
``````

### 并行范围(Parallel 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)
``````

### 并行哈希表(Parallel Hash Tables)

``````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,...
``````

### 并行散列Tries(Parallel Hash Tries)

``````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
``````

### 并行并发tries(Parallel Concurrent Tries)

concurrent.triemap 是竞争对手的线程安全的地图，而 mutable.partriemap 是他的并行副本。如果这个数据结构在遍历的过程中被修改了，大多数竞争对手的数据结构不能确保一致遍历，尝试确保在下一次迭代中更新是可见的。这意味着，你可以在尝试遍历的时候改变这些一致性，如下例子所示输出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)
...
``````

### 性能特征

head tail apply update prepend append insert
`ParArray` C L C C L L L
`ParVector` eC eC eC eC eC eC -
`ParRange` C C C - - - -

immutable
`ParHashSet`/`ParHashMap` eC eC eC
mutable
`ParHashSet`/`ParHashMap` C C C
`ParTrieMap` eC eC eC

####Key

C 该操作需要的时间常数（快）
eC 该操作需要有效的常数时间，但这可能依赖于一些假设，如一个向量或分配哈希键的最大长度。
aC 该操作需要分期常量时间。一些调用的操作可能需要更长的时间，但是如果很多操作都是在固定的时间就可以使用每个操作的平均了。
Log 该操作需要collection大小的对数时间比例。
L 这个操作是线性的，需要collection大小的时间比例。
- 这个操作是不被支持的。

tail 产生一个由除了第一个元素的所有元素组成的新的序列。
apply 标引，索引
update 对于不可变(immutable sequence)执行函数式更新(functional update)，对于可变数据执行带有副作用(side effect)的更新。
prepend 在序列的前面添加一个元素。 针对不可变的序列，这将产生一个新的序列，针对可变序列这将修改已经存在的序列。
append 在序列结尾添加一个元素。针对不可变的序列，这将产生一个新的序列，针对可变序列这将修改已经存在的序列。
insert 在序列中的任意位置插入一个元素。这是可变序列(mutable sequence)唯一支持的操作。

lookup 测试一个元素是否包含在集合，或选择一个键所关联的值。