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

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. Но если количество создаваемых комбинаций достаточно велико, параллельная работа внешнего потока уже будет использовать все ядра ЦП.

Альтернативный вариант заключается не в использовании параллельного потока, а в возврате самого Stream<Set<E>> вместо сбора в Set<Set<E>>, позволяющего вызывающему абоненту напрямую связать операцию потребления.

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