Producto cartesiano de iteradores grandes (itertools)

Question

De un previous question aprendí algo interesante. Si Python's itertools.product se alimenta con una serie de iteradores, estos iteradores se convertirán en tuplas antes de comienza el producto cartesiano. Relatedquestions observe el código fuente de itertools.product para concluir que, aunque no se almacenan en la memoria resultados intermedios, las versiones tuple de los iteradores originales se crean 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 tupla) son demasiado grandes para mantenerlas en la memoria? ejemplo trivial:

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

Un caso más práctico el uso tomaría en una serie de (*iterables[, repeat]) como la implementación original de la función - lo anterior es sólo 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 C de itertools).

Answer 1

He aquí una aplicación que llama a callables e itera iterables, que se supone reiniciable:

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

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.

Así que la respuesta es iterator recreation. Un cliente de la función debería asegurarse de que la creación de los iteradores sea pura (sin efectos secundarios). Al igual que

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 3

Esto no se puede hacer con los generadores estándar de Python, 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 comprobación de errores, pero este es al menos un primer enfoque. El simple clase reiterable ...

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 4

Siento este tema, pero después de pasar horas de depuración de una programa que intenta iterar sobre productos cartesianos generados 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, lo necesario para pasar una copia a la llamada recursiva.