ГЛАВНАЯ

RU

Декартово произведение в параллельных потоках

Многопоточность • Комбинаторика • Прямое произведение
04.10.2021

Рассмотрим алгоритм получения декартова произведения с помощью потоков Java Stream. Это решение похоже на три вложенных цикла for с тем отличием, что здесь внешний цикл заменён на поток для удобства последующего распараллеливания. Будем использовать метод reduce с тремя параметрами: identity, accumulator и combiner.

Алгоритм с тремя вложенными циклами: Декартово произведение множеств.

Входящие данные — это произвольное количество списков и их элементов.

a = [A1,B1,C1,D1]
b = [A2,B2,C2]
c = [A3,B3]
d = [A4]

Количество возможных комбинаций — это произведение количеств элементов всех списков:

4 * 3 * 2 * 1 = 24

Получаем поток списков Stream<List<T>> из входящих данных и вызываем метод reduce:

  • identity — сущность. В нашем случае это список списков List<List<T>>, заполненный одним пустым значением. Будем использовать его как промежуточный результат и как финальный результат.

  • accumulator — накопитель. Для каждого шага редукции описываем метод с двумя параметрами: промежуточный результат и текущий список. Дополняем промежуточный результат значениями из текущего списка.

  • combiner — объединитель. Используется в многопоточном режиме, объединяем результаты работы потоков, получаем декартово произведение результатов.

Пошагово процесс накопления декартова произведения выглядит следующим образом:

result0: [[]]
  list1: [A1,B1,C1,D1]
--------
result1: [[A1],[B1],[C1],[D1]]
  list2: [A2,B2,C2]
--------
result2: [[A1,A2],[A1,B2],[A1,C2],[B1,A2],[B1,B2],...[D1,C2]]
  list3: [A3,B3]
--------
result3: [[A1,A2,A3],[A1,A2,B3],[A1,B2,A3],[A1,B2,B3],[A1,C2,A3],...[D1,C2,B3]]
  list4: [A4]
--------
result4: [[A1,A2,A3,A4],[A1,A2,B3,A4],[A1,B2,A3,A4],[A1,B2,B3,A4],...[D1,C2,B3,A4]]

Комбинации по столбцам #

Количество комбинаций: 24
[A1, A2, A3, A4] [B1, A2, A3, A4] [C1, A2, A3, A4] [D1, A2, A3, A4]
[A1, A2, B3, A4] [B1, A2, B3, A4] [C1, A2, B3, A4] [D1, A2, B3, A4]
[A1, B2, A3, A4] [B1, B2, A3, A4] [C1, B2, A3, A4] [D1, B2, A3, A4]
[A1, B2, B3, A4] [B1, B2, B3, A4] [C1, B2, B3, A4] [D1, B2, B3, A4]
[A1, C2, A3, A4] [B1, C2, A3, A4] [C1, C2, A3, A4] [D1, C2, A3, A4]
[A1, C2, B3, A4] [B1, C2, B3, A4] [C1, C2, B3, A4] [D1, C2, B3, A4]

Комбинации элементов в параллельных потоках #

В параллельном режиме скорость работы алгоритма увеличивается при перемножении большого количества маленьких списков, например 20 списков по 2 элемента или 15 списков по 3 элемента. Время вычислений уменьшается в полтора-два раза. В остальных случаях время работы примерно такое же, как у трёх вложенных циклов for.

/**
 * @param lists произвольное количество списков
 * @param <T>   тип элементов списков
 * @return декартово произведение переданных списков
 */
public static <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
    // входящие данные не равны null
    if (lists == null) return Collections.emptyList();
    // поток списков Stream<List<T>>
    return lists.stream()
        // включаем параллельный режим
        .parallel()
        // отбрасываем нулевые и пустые списки
        .filter(list -> list != null && list.size() > 0)
        // сводим поток списков в один список, получаем декартово произведение
        // reduce(identity, accumulator, combiner)
        .reduce( // промежуточный результат, содержит одно пустое значение
            Collections.singletonList(Collections.emptyList()),
            // обходим переданные списки и дополняем промежуточный результат их
            // элементами, на каждом шаге получаем новый промежуточный результат
            (result, list) -> {
                // следующий промежуточный результат
                List<List<T>> nResult = new ArrayList<>(result.size() * list.size());
                // строки текущего промежуточного результата
                for (List<T> row : result) {
                    // элементы текущего списка
                    for (T el : list) {
                        // новая строка для следующего промежуточного результата
                        List<T> nRow = new ArrayList<>(row.size() + 1);
                        // добавляем текущую строку
                        nRow.addAll(row);
                        // добавляем текущий элемент
                        nRow.add(el);
                        // помещаем в следующий промежуточный результат
                        nResult.add(nRow);
                    }
                }
                // передаём на следующую итерацию
                return nResult;
            },
            // используется в многопоточном режиме, объединяем результаты
            // работы потоков, получаем декартово произведение результатов
            (result1, result2) -> {
                // объединённый результат
                List<List<T>> result = new ArrayList<>(result1.size() * result2.size());
                // обходим результаты
                for (List<T> comb1 : result1) {
                    for (List<T> comb2 : result2) {
                        // складываем комбинации
                        List<T> comb = new ArrayList<>(comb1.size() + comb2.size());
                        comb.addAll(comb1);
                        comb.addAll(comb2);
                        result.add(comb);
                    }
                }
                return result;
            });
}
// запускаем программу и выводим результат
public static void main(String[] args) {
    // произвольное количество списков и их элементов
    List<String> a = Arrays.asList("A1", "B1", "C1", "D1");
    List<String> b = Arrays.asList("A2", "B2", "C2");
    List<String> c = Arrays.asList("A3", "B3");
    List<String> d = Collections.singletonList("A4");
    // декартово произведение
    List<List<String>> cp = cartesianProduct(Arrays.asList(a, b, c, d));
    // вывод
    System.out.println("Количество комбинаций: " + cp.size());
    // комбинации по столбцам
    int rows = 6;
    IntStream.range(0, rows).forEach(i -> System.out.println(
            IntStream.range(0, cp.size())
                    .filter(j -> j % rows == i)
                    .mapToObj(j -> cp.get(j).toString())
                    .collect(Collectors.joining(" "))));
}

Вывод для этого кода см. выше: комбинации по столбцам.

© Головин Г.Г., Код с комментариями, 2021

Наверх