libreria - python 3 itertools chain

Producto cartesiano de grandes iteradores(itertools)

Question

De una pregunta anterior aprendí algo interesante. Si Python''s itertools.product se alimenta con una serie de iteradores, estos iteradores se convertirán en tuplas antes de que comience el producto cartesiano. Las preguntas relacionadas itertools.product el código fuente de itertools.product para concluir que, si bien no se almacenan en la memoria resultados intermedios, se crean versiones en tupla de los iteradores originales antes de que comience la iteración del producto.

Pregunta : ¿Hay alguna manera de crear un iterador en un producto cartesiano cuando las entradas (convertidas en tuplas) son demasiado grandes para mantenerlas en la memoria? Ejemplo trivial:

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

Un caso de uso más práctico tomaría una serie de (*iterables[, repeat]) como la implementación original de la función; lo anterior es solo un ejemplo. No parece que puedas usar la implementación actual de itertools.product , así que doy la bienvenida en la presentación en python puro (¡aunque no puedes superar el backend de C de itertools !).

Answer 1

Aquí hay una implementación que llama a callables e itera iterables, que se supone son reiniciables:

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

Pruebas:

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

Answer 2

Esto no se puede hacer con generadores de Python estándar, porque algunos de los iterables se deben reciclar varias veces. Tienes que usar algún tipo de tipo de datos capaz de "reiterar". Creé una clase simple "reiterable" y un algoritmo de producto no recursivo. product debería tener más control de errores, pero este es al menos un primer enfoque. La clase simple y reiterativa ...

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

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

Probado:

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

Answer 3

Sin "recreación de iterador", puede ser posible para el primero de los factores. Pero eso ahorraría solo 1 / n de espacio (donde n es la cantidad de factores) y agregaría confusión.

Entonces la respuesta es recreación de iterador. Un cliente de la función debería asegurarse de que la creación de los iteradores sea pura (sin efectos secundarios). Me gusta

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

Answer 4

Lamento subir este tema pero después de pasar horas depurando un programa que intenta iterar sobre el producto cartesiano generado recursivamente de generadores. Puedo decirle que ninguna de las soluciones anteriores funciona si no funciona con números constantes como en todos los ejemplos anteriores.

Corrección:

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

Si sus generadores contienen generadores, debe pasar una copia a la llamada recursiva.