스칼라 병렬화 하위 집합 호출

Question

하위 집합을 추출 할 목록이 있습니다. 그래서 나는해야한다.

`이것은 작은 목록 크기에서는 작동하지만 큰 목록에서는 실패한다. 하위 집합을 병렬로 호출하는 방법

나는 'l'그 자체를 병렬로 만들려고했지만, 그 목록에있는 toSet 호출은 부분 집합 호출이없는 parSeq를 반환한다. 내 하위 집합 알고리즘을 작성해야합니까?

감사합니다.

Answer 1

실패 이유는 두 가지 이유가있을 수 있습니다 : 당신이하려고하는 :

• 이 모두이 같은 문제에 관련된

메모리가 부족

실행을 실행하기 위해 너무 많은 시간이 소요 기하 급수적으로 커지는 반복자를 구체화합니다.

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(), ?) 

스트림은 게으른 목록입니다.