斯卡拉平行子集調用

Question

我有一個列表，我想從中提取子集。所以我願意`

val l = List(1,2,4).toSet.subsets.toList 

`這適用於小列表大小，但在大列表上失敗。如何使子集調用並行？

我試着讓列表'l'本身並行，但列表上的toSet調用返回一個沒有子集調用的parSeq。我是否必須編寫自己的子集算法？

欣賞所有的幫助。

Answer 1

有可能是失敗的原因有2個原因：

• 需要太多的時間來執行
• 內存用完

兩者都與同樣的問題：你想實現一個大小呈指數級增長的迭代器。

有一個很好的理由，def subsets(): Iterator[Set[A]]返回一個迭代器而不是一個列表 - 結果集可能是巨大的。事實上 所有可能的子集數爲2^n：

scala> (1 to 10).toSet.subsets.size 
res0: Int = 1024 

scala> math.pow(2, 10) 
res1: Double = 1024.0 

如果並行代子集，你會很快仍在運行內存或無休止地等待。換句話說，這是一個算法問題，而不是併發/硬件問題。

解決此問題的方法是隨時使用惰性生成器（迭代器/流），而不是一次嘗試獲取所有數據。如果你喜歡Stream界面，您可以返回的迭代器轉換成流：

scala> (1 to 10).toSet.subsets.toStream 
res2: scala.collection.immutable.Stream[scala.collection.immutable.Set[Int]] = Stream(Set(), ?) 

流只是懶惰的名單，所以沒有在數據結構本身而言太大的差別，它應該符合你的要求。