Декартово произведение словаря в Python: один проход или рекурсия

Как вычислить декартово произведение словаря в Python без лишних проходов: один проход с itertools и рекурсивная сборка. Код с Fraction и замеры скорости.

Вычисление декартова произведения словаря самого на себя — распространённый приём, когда нужны кортежи ключей и числовая агрегация по соответствующим значениям. Здесь задача — перечислить все кортежи ключей длины repeat и для каждого кортежа перемножить связанные значения типа Fraction. Прямолинейный подход строит два независимых произведения — по ключам и по значениям — и затем склеивает их по индексу. Это работает, но требует двух проходов и создаёт промежуточные списки, которых можно избежать.

Базовый вариант: два произведения — по ключам и по значениям

Следующий пример показывает схему с двумя проходами: первый строит все кортежи ключей, второй — все кортежи значений, при этом для перемножения используется math.prod. Решение полностью на стандартной библиотеке.

import itertools as tools
import math as m
from fractions import Fraction as F

weights = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}

repeat_count = 2  # variable; can be any non-negative integer
key_tuples = list(tools.product(weights, repeat=repeat_count))
value_products = list(map(m.prod, tools.product(weights.values(), repeat=repeat_count)))

result = {key_tuples[i]: value_products[i] for i in range(len(value_products))}
print(result)

Это даёт ожидаемое отображение: кортеж ключей → произведение соответствующих Fraction. Минус — дублирование работы и лишняя память на две параллельные коллекции.

Что на самом деле требуется

Ключи должны выходить кортежами, а значения — быть обычным произведением Fraction. Внешних пакетов не используется, repeat — переменная, поэтому решения, «зашитые» под фиксированное число вложенных циклов, не масштабируются. При таких ограничениях нужна либо одна итерация, которая одновременно отдаёт и кортеж ключей, и его произведение, либо способ собрать ту же структуру без построения двух отдельных декартовых произведений.

Решение 1: однопроходное словарное включение с itertools

Короткий способ избежать двойного прохода — итерировать только декартово произведение ключей и «на лету» считать произведение соответствующих значений. Логика остаётся в одном месте, а связка по индексам между двумя списками исчезает.

import itertools as tools
import math as m
from fractions import Fraction as F

pool = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}

def cart_dict_onepass(bucket, times=2):
    return {
        keys: m.prod(bucket[k] for k in keys)
        for keys in tools.product(bucket, repeat=times)
    }

print(cart_dict_onepass(pool, times=2))

Подход опирается на одно включение: оно идёт по кортежам ключей и перемножает их значения через math.prod. Всё в рамках стандартной библиотеки и работает с любым значением repeat.

Решение 2: рекурсивная сборка без itertools

От itertools можно отказаться вовсе и собрать отображение рекурсивно. Отталкиваемся от нейтрального элемента операции — пустого кортежа с единицей — и по одному умножаем измерения. По сути, это «декартово произведение декартова произведения», применённое repeat раз.

from fractions import Fraction as F

pool = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}

def unfold(state, times=2):
    if times == 0:
        return state
    return unfold(
        {
            prefix + (k2,): state[prefix] * pool[k2]
            for prefix in state for k2 in pool
        },
        times - 1,
    )

def build_map(times=2):
    return unfold({(): 1}, times)

# Если гарантируется, что times > 0, можно пропустить один уровень
# и сразу проинициализировать уже развёрнутым одним измерением.

def build_map_nonempty(times=2):
    return unfold({(k,): pool[k] for k in pool}, times - 1)

print(build_map(times=2))

Результат совпадает со способом через itertools, с бонусом — нет зависимости от itertools. Важно помнить, что Python не оптимизирует хвостовую рекурсию: при очень больших repeat вы упрётесь в лимит рекурсии задолго до того, как такая задача станет вычислимо выполнимой для декартова произведения такого объёма.

Заметки о производительности

На примере из статьи прямой вложенный обход, специализированный под repeat = 2, показал около 121 мкс. Рекурсивный вариант без itertools укладывался примерно в 136–167 мкс, а однопроходное включение с itertools — порядка 398 мкс. Базовый вариант с двумя проходами, где по отдельности строятся произведения ключей и значений, занял примерно 346 мкс. Все измерения проводились на одной машине и одном входе и показывают, что на такой нагрузке рекурсивный подход без itertools может быть быстрее, а фиксированная двуцикловая форма остаётся самой быстрой, когда repeat точно равен двум.

Дополнительные замеры изучали влияние repeat на время выполнения. Как и положено декартову произведению, время растёт экспоненциально по repeat, а соотношения между методами остаются примерно одинаковыми для разных значений repeat. Увеличение размера словаря дало похожую картину: при repeat = 2 затраты росли примерно квадратично от числа элементов, и относительный порядок методов не менялся. Иными словами, для этой задачи асимптотика — O(n^repeat), а выбор между реализациями — в основном про константы и зависимости, а не про различия по big-O.

Зачем это знать

Декартовы произведения растут мгновенно, поэтому важно сокращать промежуточные выделения и лишние проходы. Однопроходный вариант избавляет от связки двух списков по индексам и удерживает вычисления рядом с текущими ключами. Рекурсивный вариант заменяет библиотечную итерацию простым шагом расширения состояния и, судя по замерам выше, дал наилучшее время среди общих решений. Понимание компромиссов помогает выбрать подход с нужным балансом читаемости, зависимостей и скорости под ваши ограничения.

Итоги

Если repeat фиксирован и мал, прямое двойное включение вроде {(k1, k2): pool[k1] * pool[k2] for k1 in pool for k2 in pool} почти непревзойдённо. Когда repeat — переменная, выбирайте между однопроходным включением с itertools, которое считает значения на лету, и рекурсивным расширением без itertools с начальным {(): 1}. Оба варианта опираются на стандартную библиотеку, дают одинаковое отображение «кортеж ключей → произведение Fraction» и избегают лишнего прохода и накладных расходов памяти на отдельные продукты по ключам и значениям. И в качестве стилистики: отдавайте предпочтение понятным именам импортов вместо чрезмерных псевдонимов, если только алиас не общеизвестен; ясность окупается, когда к коду приходится возвращаться в стрессовой ситуации.