平行集合

具體平行集合類別

平行陣列

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 會由與其來源平行陣列相同的基礎陣列作為後盾。

平行向量

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，由於這是並發資料結構，因此只會為整個轉換器方法呼叫建構一個組合器，並由所有處理器共用。

與所有平行可變集合一樣，TrieMap 和平行 ParTrieMap 透過呼叫 seq 或 par 方法取得，由同一儲存體支援，因此其中一個的修改會在另一個中可見。轉換會在恆定時間內發生。

效能特性

序列類型的效能特性

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

集合和映射類型的效能特性

	查詢	新增	移除
不可變
`ParHashSet`/`ParHashMap`	eC	eC	eC
可變
`ParHashSet`/`ParHashMap`	C	C	C
`ParTrieMap`	eC	eC	eC

金鑰

以上兩個表格中的項目說明如下


C	此操作需要（快速的）常數時間。
eC	此操作需要有效的常數時間，但這可能取決於某些假設，例如向量的最大長度或雜湊金鑰的分配。
aC	此操作需要攤銷常數時間。此操作的某些呼叫可能需要較長的時間，但如果對平均值執行許多操作，則每個操作只需要常數時間。
Log	此操作需要與集合大小的對數成正比的時間。
L	此操作是線性的，也就是說它需要與集合大小成正比的時間。
-	不支援此操作。

第一個表格處理序列類型（不可變和可變）以及以下操作


head	選取序列的第一個元素。
tail	產生一個新的序列，其中包含除了第一個元素之外的所有元素。
apply	索引。
update	不可變序列的功能性更新（使用 `updated`），可變序列的副作用更新（使用 `update`）。
prepend	在序列的前面新增一個元素。對於不可變序列，這會產生一個新的序列。對於可變序列，它會修改現有的序列。
append	在序列的結尾新增一個元素。對於不可變序列，這會產生一個新的序列。對於可變序列，它會修改現有的序列。
insert	在序列中的任意位置插入一個元素。這僅直接支援可變序列。

第二個表格處理可變和不可變的集合和映射以及以下操作


查詢	測試元素是否包含在集合中，或選取與金鑰相關聯的值。
新增	將新元素新增到集合或金鑰/值對新增到映射。
移除	從集合中移除元素或從映射中移除金鑰。
最小值	集合中的最小元素，或映射中的最小金鑰。