Вычислите все перестановки коллекции параллельно


Мне нужно вычислить все перестановки коллекции, и у меня есть код для этого, но проблема в том, что он линейный и занимает много времени.

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;
}

Я пытаюсь сделать вычисления параллельными.

Я думал о возможности написать логику с помощью рекурсии, а затем параллельно выполнить вызов рекурсии, но я не совсем уверен, как это сделать.

Буду признателен за любую помощь.

1 3
combinations java-stream parallel-processing recursion

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. Но если число комбинации производить достаточно большие, запуск внешнего потока параллельно будет уже задействовать все ядра процессора. Альтернативой является не использование параллельного потока, а возврат самого потока Stream<Set<E>> вместо того, чтобы собирать его в Set<Set<E>>, чтобы позволить вызывающему объекту напрямую связывать потребляющую операцию.

Кстати, хеширование целого Set (или их множества) может быть довольно дорогим, поэтому стоимость заключительного этапа(этапов) слияния, вероятно, будет доминировать в производительности. Возвращение a List<Set<E>> вместо этого можно резко увеличить производительность. То же самое относится и к альтернативе возврата a Stream<Set<E>> без сбора комбинаций вообще, поскольку это также работает без хэширования Sets.

4