大型迭代器的笛卡尔积（itertools）

Question

从之前的问题中，我学到了一些有趣的东西。如果Python的itertools.product被提供了一系列迭代器，这些迭代器将在笛卡尔积开始之前转换为元组。相关的问题查看itertools.product的源代码得出，虽然没有中间结果存储在内存中，但在积的迭代开始之前，原始迭代器的元组版本被创建。

问题：当（转换为元组的）输入太大而无法存入内存时，是否有一种方法创建笛卡尔积的迭代器？下面是一个简单的示例：

import itertools
A = itertools.permutations(xrange(100))
itertools.product(A)

更实际的用例将接受一系列 (*iterables[, repeat])，就像函数的原始实现一样 - 上面只是一个示例。看起来你不能使用当前的 itertools.product 实现，所以我欢迎纯Python的解决方案（尽管你无法击败itertools的C后端！）。

- Hooked

---

你认为这些产品应该如何生产呢？你需要使用.tee()函数，它还会缓存迭代器以完成它们的工作。 - Martijn Pieters

或者，你需要可重新启动的迭代器，例如，只有当你可以以某种方式全新创建每个迭代器时，才能产生与先前完整运行期间完全相同的结果，才能实现你的目标。 - Martijn Pieters

@MartijnPieters 我不确定（这也是为什么要问的原因！）。问题的核心是，提供一个没有任何中间存储的外积实现。在 itertools 中可能可以实现，但我不确定——在纯 Python 中，我认为这是可能的，因为我们可以通过每次需要时重新创建迭代器来“重启”它。 - Hooked

没错，但这只有在您能够保证每次重新创建迭代器时都能产生相同的结果时才有效。 - Martijn Pieters

Answer 1

以下是一个实现，它调用可调用对象并迭代可迭代对象，假定它们可以重新启动：

def product(*iterables, **kwargs):
    if len(iterables) == 0:
        yield ()
    else:
        iterables = iterables * kwargs.get('repeat', 1)
        it = iterables[0]
        for item in it() if callable(it) else iter(it):
            for items in product(*iterables[1:]):
                yield (item, ) + items

测试：

import itertools
g = product(lambda: itertools.permutations(xrange(100)),
            lambda: itertools.permutations(xrange(100)))
print next(g)
print sum(1 for _ in g)

- ecatmur

---

我不完全理解为什么product的输入必须是一个lambda函数，即使你使用我的示例中的A，它似乎仍然可以工作。 - Hooked

@Hooked，这个方法可以先尝试一下，但是当它在内部循环中到达末尾时，它不会知道如何重新开始排列。建议尝试一下A的小范围。 - ecatmur

@Hooked：如果我们想要可重现的迭代器，您必须将迭代器创建者传递给产品函数。这些迭代器只能在函数本身中创建。 - Jo So

我现在明白了，没有意识到像 for x in product(lambda: A,repeat=2): 这样做可能是危险的，因为 A 会被使用完而得出完全错误的答案。非常好的回答，谢谢！ - Hooked

Answer 2

没有“迭代器重建”，第一个因素可能是可能的。但这只能节省1/n的空间（其中n是因素的数量），并增加混乱。

所以答案是迭代器重建。函数的客户端必须确保迭代器的创建是纯净的（没有副作用）。例如：

def iterProduct(ic):
    if not ic:
        yield []
        return

    for i in ic[0]():
        for js in iterProduct(ic[1:]):
            yield [i] + js


# Test
x3 = lambda: xrange(3)
for i in iterProduct([x3,x3,x3]):
    print i

- Jo So

---

调用 len(ic) 失败，因为我的输入 A 是一个类型为 'itertools.permutations' 的对象，它没有 len() 方法。如果我没记错的话，你也不能通过索引访问迭代器 ic[0]，因为一般情况下没有实现 __getitem__ 方法。 - Hooked

@Hooked：现在不需要调用len()了。ic不应该是一个迭代器，它只是作为一个列表提供的固定数量的因子（也许有一种使用可变参数或更加函数式的解决方案，但我的Python版本比较老）。 - Jo So

@DSM：第二个代码块中的if ic:是隐式的。试一下吧。 - Jo So

@JoSo：啊，你说得对。我正在使用自己修改过的原始代码，所以错误只出现在我的一边。: ^) - DSM

Answer 3

这不能使用标准的Python生成器完成，因为其中一些可迭代对象必须被多次循环。您必须使用某种能够“重新迭代”的数据类型。我创建了一个简单的“可重复迭代”类和一个非递归乘积算法。product应该有更多的错误检查，但这至少是一个初步的方法。这个简单的可重复迭代类...

class PermutationsReiterable(object):
    def __init__(self, value):
        self.value = value
    def __iter__(self):
        return itertools.permutations(xrange(self.value))

以及产品本身...

def product(*reiterables, **kwargs):
    if not reiterables:
        yield ()
        return
    reiterables *= kwargs.get('repeat', 1)

    iterables = [iter(ri) for ri in reiterables]
    try:
        states = [next(it) for it in iterables]
    except StopIteration:
        # outer product of zero-length iterable is empty
        return
    yield tuple(states)

    current_index = max_index = len(iterables) - 1
    while True:
        try:
            next_item = next(iterables[current_index])
        except StopIteration:
            if current_index > 0:
                new_iter = iter(reiterables[current_index])
                next_item = next(new_iter)
                states[current_index] = next_item
                iterables[current_index] = new_iter
                current_index -= 1
            else:
                # last iterable has run out; terminate generator
                return
        else:
            states[current_index] = next_item
            current_index = max_index
            yield tuple(states)

测试完成：

>>> pi2 = PermutationsReiterable(2)
>>> list(pi2); list(pi2)
[(0, 1), (1, 0)]
[(0, 1), (1, 0)]
>>> list(product(pi2, repeat=2))
[((0, 1), (0, 1)), ((0, 1), (1, 0)), ((1, 0), (0, 1)), ((1, 0), (1, 0))]
>>> giant_product = product(PermutationsReiterable(100), repeat=5)
>>> len(list(itertools.islice(giant_product, 0, 5)))
5
>>> big_product = product(PermutationsReiterable(10), repeat=2)
>>> list(itertools.islice(big_product, 0, 5))
[((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)), 
 ((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 7, 9, 8)), 
 ((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 8, 7, 9)), 
 ((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 8, 9, 7)), 
 ((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 9, 7, 8))]

- senderle

---

@senderle：我认为这已经是过度工程了。 - Jo So

@JoSo，那么您必须考虑 itertools.product 是过度设计的。如果您传递一个无效的关键字参数，它会抛出错误。 - senderle

错误：product() 应该返回一个空元组。 - ecatmur

另外，在该函数中你没有使用 repeat。 - ecatmur

你修正了错误的位置！yield() 应该放在开头。 - ecatmur

Answer 4

很抱歉提高这个话题，但是在花费几个小时调试程序并尝试迭代递归生成的笛卡尔积生成器后，我可以告诉你，如果不使用固定数字(与上面所有示例相同)，那么上面的解决方案都不起作用。

更正：

from itertools import tee

def product(*iterables, **kwargs):
    if len(iterables) == 0:
        yield ()
    else:
        iterables = iterables * kwargs.get('repeat', 1)
        it = iterables[0]
        for item in it() if callable(it) else iter(it):
            iterables_tee = list(map(tee, iterables[1:]))
            iterables[1:] = [it1 for it1, it2 in iterables_tee]
            iterable_copy = [it2 for it1, it2 in iterables_tee]
            for items in product(*iterable_copy):
                yield (item, ) + items

如果您的生成器包含生成器，则需要将其副本传递给递归调用。

- Philippe Ferreira de sousa