Prodotto cartesiano di grandi iteratori (itertools)

Question

Da un previous question ho imparato qualcosa di interessante. Se Python itertools.product viene alimentato con una serie di iteratori, questi iteratori verranno convertiti in tuple prima del. Inizia il prodotto cartesiano. Relatedquestions guardare il codice sorgente di itertools.product per concludere che, mentre nessun risultato intermedio è memorizzato in memoria, le versioni di tuple degli iteratori originali vengono create prima dell'inizio dell'iterazione del prodotto.

Domanda: C'è un modo per creare un iteratore su un prodotto cartesiano quando gli ingressi (convertiti nella tupla) sono troppo grandi per essere conservati in memoria? banale esempio:

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

più pratica caso d'uso prenderebbe in una serie di (*iterables[, repeat]) come l'implementazione originale della funzione - quanto sopra è solo un esempio. Non sembra che tu possa usare l'attuale implementazione di itertools.product, quindi accolgo con favore in sottomissione in puro python (anche se non puoi battere il backend C di itertools!).

Answer 1

Ecco un'implementazione che chiama callable e itera iterables, che si presume riavviabile:

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 

Testing:

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

Senza "ricreazione iteratore", può essere possibile per il primo dei fattori. Ma ciò farebbe risparmiare solo 1/n spazio (dove n è il numero di fattori) e aggiungere confusione.

Quindi la risposta è ricreazione iteratore. Un cliente della funzione dovrebbe assicurarsi che la creazione degli iteratori sia pura (senza effetti collaterali). Come

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

Questo non può essere fatto con i generatori standard di Python, perché alcuni dei iterabili devono essere ripetuti più volte. Devi usare una sorta di tipo di dati in grado di "reiterare". Ho creato una semplice classe "reiterabile" e un algoritmo di prodotto non ricorsivo. product dovrebbe avere più controllo degli errori, ma questo è almeno un primo approccio. Il semplice classe reiterabile ...

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

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

Provato:

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

Mi dispiace di questa discussione, ma dopo passare ore di debug di un programma che tenta di iterare su generatori di prodotti cartesiani generati in modo ricorsivo. Posso dirti che nessuna delle soluzioni di cui sopra funziona se non funziona con numeri costanti come in tutti gli esempi sopra.

Correzione:

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 

Se i generatori contengono generatori, è necessario passare una copia per la chiamata ricorsiva.