itertools.product如何计算笛卡尔积而不将中间结果保存在内存中

Question

根据文档here 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代码here，但不能。我想了解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

它将输入存储在内存中（如tuples），以及每个tuple的索引，并重复循环除第一个之外的所有内容。每次请求新的输出值时，它：

1. 将指数推进到最右边的tuple
2. 如果超过结束，则将其重置为零，并推进下一个最右边的索引
3. 重复步骤2，直到找到一个索引，该索引可以递增而不超过其特定迭代器的末尾
4. 通过拉取每个数据源的当前索引处的值来创建新的tuple

它有一个特殊情况，第一次拉动它只是从每个tuple拉出第0个值，但是否则每次都会跟随该模式。

对于一个非常简单的例子，内部状态为：

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

将是最前面创建元组('a', 'b')和('c', 'd')，以及一系列索引[0, 0]。在第一次拉动时，它产生('a', 'b')[0], ('c', 'd')[0]或('a', 'c')。在下一次拉动时，它将indices数组推进到[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在创建后立即被yielded;只有那些输入的输入和当前索引必须保留为迭代器状态。因此，只要调用者不存储结果，并且只是实时迭代，就需要非常少的内存。