16

以前の質問から、興味深いことを学びました。Python に一連のイテレータが与えられた場合、これらのイテレータはデカルト積が始まる前itertools.productにタプルに変換されます。関連する質問では、 のソース コードを調べて、中間結果がメモリに格納されていない一方で、元の反復子のタプル バージョンが製品の反復が開始される前に作成されると結論付けています。 itertools.product

質問: (タプル変換された) 入力が大きすぎてメモリに保持できない場合に、デカルト積の反復子を作成する方法はありますか? 些細な例:

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

より実用的な使用例(*iterables[, repeat])では、関数の元の実装のような一連のものが使用されます。上記は単なる例です。の現在の実装を使用できるようには見えないitertools.productので、純粋な python での提出を歓迎します (ただし、! の C バックエンドには勝てませんitertools)。

4

4 に答える 4

7

これは、再起動可能であると想定されている callable を呼び出して iterable を反復する実装です。

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)
于 2012-08-23T14:55:22.853 に答える
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
于 2012-08-23T14:42:49.237 に答える
1

一部の反復可能オブジェクトは複数回循環する必要があるため、これは標準のPythonジェネレーターでは実行できません。「反復」が可能なある種のデータ型を使用する必要があります。単純な「reiterable」クラスと非再帰的な製品アルゴリズムを作成しました。productより多くのエラーチェックが必要ですが、これは少なくとも最初のアプローチです。シンプルな反復可能なクラス...

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

そしてproductiteslf..。

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))]
于 2012-08-23T15:16:18.867 に答える