java - 并行计算集合的所有排列

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 核心。

另一种选择是不使用并行流，而是返回 Stream<Set<E>>本身而不是收集到 Set<Set<E>> ，以允许调用者直接链接消费操作。

顺便说一下，对整个 Set 进行哈希处理(或其中很多)可能非常昂贵，因此最终合并步骤的成本可能会主导性能。返回List<Set<E>>相反可以显着提高性能。这同样适用于返回 Stream<Set<E>> 的替代方案。根本不需要收集组合，因为这也可以在不散列 Set 的情况下工作。 s。