コレクションのすべての順列を並行して計算する

Question

コレクションのすべての順列を計算する必要がありますが、そのためのコードがありますが、問題は線形で時間がかかります。

public static <E> Set<Set<E>> getAllCombinations(Collection<E> inputSet) { 
    List<E> input = new ArrayList<>(inputSet); 
    Set<Set<E>> ret = new HashSet<>(); 
    int len = inputSet.size(); 
    // run over all numbers between 1 and 2^length (one number per subset). each bit represents an object 
    // include the object in the set if the corresponding bit is 1 
    for (int i = (1 << len) - 1; i > 0; i--) { 
     Set<E> comb = new HashSet<>(); 
     for (int j = 0; j < len; j++) { 
      if ((i & 1 << j) != 0) { 
       comb.add(input.get(j)); 
      } 
     } 
     ret.add(comb); 
    } 
    return ret; 
} 

私は並列に計算を実行しようとしています。

私は、再帰を使ってロジックを書いてから、並列呼び出しを並列実行することはできますが、どうすればいいのか正確には分かりません。

助けていただければ幸いです。

Answer 1

再帰を使用する必要はありませんが、実際には反生産性がある可能性があります。各コンビネーションの作成は、他のコンビネーションとは独立して実行できるため、並列ストリームを使用して実行できます。あなたも手でビット操作を実行する必要はないことに注意してください：

public static <E> Set<Set<E>> getAllCombinations(Collection<E> inputSet) { 
    // use inputSet.stream().distinct().collect(Collectors.toList()); 
    // to get only distinct combinations 
    // (in case source contains duplicates, i.e. is not a Set) 
    List<E> input = new ArrayList<>(inputSet); 
    final int size = input.size(); 
    // sort out input that is too large. In fact, even lower numbers might 
    // be way too large. But using <63 bits allows to use long values 
    if(size>=63) throw new OutOfMemoryError("not enough memory for " 
     +BigInteger.ONE.shiftLeft(input.size()).subtract(BigInteger.ONE)+" permutations"); 

    // the actual operation is quite compact when using the Stream API 
    return LongStream.range(1, 1L<<size) /* .parallel() */ 
     .mapToObj(l -> BitSet.valueOf(new long[] {l}).stream() 
      .mapToObj(input::get).collect(Collectors.toSet())) 
     .collect(Collectors.toSet()); 
} 

インナーストリーム動作、すなわちビットを反復処理、それが合併しなければならない、特にとして、並列処理の恩恵を受けるには小さすぎます結果は単一のSetになります。しかし、生成する組み合わせの数が十分に多い場合、外部ストリームを並列に実行すると、すべてのCPUコアが既に使用されます。

代わりに、パラレルストリームを使用するのではなく、Set<Set<E>>に収集する代わりにStream<Set<E>>を返すことで、呼び出し側が消費操作を直接チェーンできるようにします。

ところで、Set（またはそれらの多く）のハッシングは非常に高価な場合があります。したがって、最終的なマージステップのコストがパフォーマンスを左右する可能性があります。代わりにList<Set<E>>を返すと、パフォーマンスが大幅に向上します。同じことは、組み合わせを一切収集せずにStream<Set<E>>を返す代替方法にも当てはまります。これは、Setをハッシュすることなく動作するためです。