Блог

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

 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]) 
        product(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
....
  

Он сохраняет входные данные в памяти (как 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] or ('a', 'd') . При следующем извлечении крайний правый индекс увеличивается до 2, осознает, что он переполнен, возвращает его обратно в 0 и увеличивает следующий индекс, делающий его [1, 0] , и выдает ('a', 'b')[1], ('c', 'd')[0] or ('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 редактируется сразу после создания; только входные данные и текущие индексы для этих входных данных должны быть сохранены как состояние итератора. Таким образом, пока вызывающий не сохраняет результаты, а просто выполняет итерации в реальном времени, требуется очень мало памяти.