Декартово произведение больших итераторов (itertools)

Из предыдущего вопроса я узнал что-то интересное. Если Python itertools.product будет снабжен серией итераторов, эти итераторы будут преобразованы в кортежи перед декартовым произведением. Связанные questions посмотрите на исходный код itertools.product, чтобы сделать вывод, что, хотя промежуточные результаты отсутствуют хранящиеся в памяти, корневые версии исходных итераторов создаются до начала итерации продукта.

Вопрос: Есть ли способ создать итератор для декартова продукта, когда входы с корневым преобразованием слишком велики для хранения в памяти? Тривиальный пример:

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

Более практичный случай использования займет в серии (*iterables[, repeat]), как и исходная реализация функции - вышеприведенный пример. Это не похоже на то, что вы можете использовать текущую реализацию itertools.product, поэтому я приветствую ее в представлении в чистом питоне (хотя вы не можете использовать бэкэнд из itertools!).

Ответы

Ответ 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)

Ответ 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

Ответ 3

Это невозможно сделать со стандартными генераторами Python, потому что некоторые из повторяющихся элементов должны циклически повторяться несколько раз. Вы должны использовать какой-то тип данных, способный "повторять". Я создал простой "перезаписываемый" класс и нерекурсивный алгоритм продукта. product должен иметь большую проверку ошибок, но это, по крайней мере, первый подход. Простой повторимый класс...

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

И product iteslf...

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))]

Ответ 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

Если ваши генераторы содержат генераторы, вам необходимо передать копию на рекурсивный вызов.