Как itertools.product вычисляет декартово произведение, не сохраняя промежуточные результаты в памяти

Question

Согласно документации здесь iterpools.product не хранит промежуточные результаты в памяти (он вычисляет декартово произведение входных списков). Но грубый набросок данного алгоритма заставляет меня верить в это. Обратите внимание, как result постоянно обновляется в каждой итерации, беря элементы в result и добавляя к нему больше.

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Я попытался взломать базовый C код здесь , но не смог. Я хотел бы понять, как работает код C без сохранения промежуточных результатов в памяти. Я столкнулся с рекурсивным подходом (воспроизведенным ниже), который не сохраняет промежуточные результаты в памяти, кроме стека рекурсивных вызовов. Использует ли код C также рекурсивный подход, иначе как он может работать, не сохраняя промежуточные результаты в памяти?

// Recursive approach
def product(input, ans, i): 
    if i == len(input): 
        print(ans) 
        return 
    j = 0 
    while j < len(input[i]): 
        ans.append(input[i][j]) 
        find(input, ans, i+1) 
        ans.pop() 
        j += 1

input = [] 
input.append(["hi", "hey"]) 
input.append(["there", "here"]) 
input.append(["cute", "handsome"])  

ans = [] 
print(product(input, ans, 0))

hi there cute
hi there handsome
....

Answer 1

Хранит входные данные в памяти (как tuple с) вместе с индексом для каждого tuple и многократно циклически повторяет все, кроме первого. Каждый раз, когда запрашивается новое выходное значение, оно:

1. Продвигает указатель в крайнее правое положение tuple
2. Если он проходит после конца, он сбрасывает его в ноль и продвигается к следующему крайнему правому индексу
3. Шаг 2 повторяется до тех пор, пока не будет найден индекс, который можно увеличивать, не превышая конца его конкретного итератора
4. Новый tuple создается путем извлечения значения из текущего индекса для каждого источника данных

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

Для очень простого примера, внутреннее состояние для:

for x, y in product('ab', 'cd'):

будет создавать кортежи ('a', 'b') и ('c', 'd') заранее и массив индексов, [0, 0] изначально. При первом нажатии он дает ('a', 'b')[0], ('c', 'd')[0] или ('a', 'c'). При следующем извлечении он увеличивает массив индексов до [0, 1] и возвращает ('a', 'b')[0], ('c', 'd')[1] или ('a', 'd'). Следующее извлечение увеличивает самый правый индекс до 2, понимает, что он переполнен, возвращает его к 0 и увеличивает следующий индекс, делая его [1, 0], и возвращает ('a', 'b')[1], ('c', 'd')[0] или ('b', 'c'). Это продолжается до тех пор, пока крайний левый индекс не переполнится, после чего итерация будет завершена.

Фактически эквивалентный код Python будет выглядеть примерно так:

def product(*iterables, repeat=1):
    tuples = [tuple(it) for it in iterables] * repeat
    if not all(tuples):
        return # A single empty input means nothing to yield
    indices = [0] * len(tuples)
    yield tuple(t[i] for i, t in zip(indices, tuples))
    while True:
        # Advance from rightmost index moving left until one of them
        # doesn't cycle back to 0
        for i in range(len(indices))[::-1]:
            indices[i] += 1
            if indices[i] < len(tuples[i]):
                break  # Done advancing for this round
            indices[i] = 0  # Cycle back to 0, advance next
        else:
            # The above loop will break at some point unless
            # the leftmost index gets cycled back to 0
            # (because all the leftmost values have been used)
            # so if reach the else case, all products have been computed
            return

        yield tuple(t[i] for i, t in zip(indices, tuples))

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

Как видите, каждый вывод tuple yield редактируется сразу после создания; только входы и текущие индексы для этих входов должны быть сохранены как состояние итератора. Таким образом, до тех пор, пока вызывающая сторона не сохраняет результаты и просто выполняет итерации, требуется очень мало памяти.