Scala Parallelisierung Teilmengen Anruf

Question

Ich habe eine Liste, aus der ich Teilmengen extrahieren möchte. So mache ich '

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

`Dies funktioniert auf kleinen Listengrößen, aber auf großen Listen fehlschlägt. Wie kann man die Teilmengen parallel aufrufen?

Ich habe versucht, die Liste 'l' selbst parallel zu machen, aber der ToSet-Aufruf auf dieser Liste gibt ein parSeq zurück, das keinen Subset-Aufruf hat. Muss ich meinen eigenen Teilmengenalgorithmus schreiben?

Schätzen Sie alle Hilfe.

Answer 1

Es könnte zwei Gründe, warum es fehlschlägt:

• zu viel Zeit in Anspruch nimmt auszuführen
• läuft aus dem Speicher

Sowohl für das gleiche Problem in Zusammenhang stehen: Sie versuchen, materialisieren einen Iterator, der in der Größe exponentiell wächst.

Es gibt einen guten Grund, dass def subsets(): Iterator[Set[A]] einen Iterator und keine Liste zurückgibt - die Ergebnismenge könnte sehr groß sein. In der Tat ist die Zahl der alle möglichen Teilmengen 2^n:

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

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

Wenn Sie Generation von Untergruppen parallelisieren werden Sie noch schnell der Speicher ausgeht oder endlos warten. Mit anderen Worten, es ist ein algorithmisches Problem, kein Nebenläufigkeits-/Hardwareproblem.

Der Weg, dies zu erreichen, ist, den Lazy Generator (Iterator/Stream) zu konsumieren, anstatt zu versuchen, alle Daten auf einmal zu erhalten. Wenn Sie Stream Schnittstelle bevorzugen, können Sie den zurückgegebenen Iterator Strom umwandeln:

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

Streams sind nur faul Listen, so gibt es in Bezug auf die Datenstruktur selbst ist nicht viel Unterschied, und es sollte Ihre Anforderungen passen.