Kartesisches Produkt großer Iteratoren (itertools)

Question

Von einer previous question habe ich etwas Interessantes gelernt. Wenn Pythons itertools.product eine Reihe von Iteratoren erhält, werden diese Iteratoren in Tupel konvertiert, bevor das kartesische Produkt beginnt. Relatedquestions Betrachten Sie den Quellcode von itertools.product um zu schließen, dass, während keine Zwischenergebnisse im Speicher gespeichert sind, Tupel-Versionen der ursprünglichen Iteratoren erstellt werden, bevor die Produkt-Iteration beginnt.

Frage: Gibt es eine Möglichkeit, einen Iterator auf ein Kartesisches Produkt, wenn das (Tupel umgewandelt) Eingänge sind zu groß zu halten, im Speicher zu schaffen? Triviales Beispiel:

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

Ein praktischer Anwendungsfall würde in einer Reihe von (*iterables[, repeat]) wie die ursprünglichen Implementierung der Funktion übernehmen - die oben nur ein Beispiel ist. Es sieht nicht so aus, als könntest du die aktuelle Implementierung von itertools.product verwenden, also begrüße ich dich in reiner Python (obwohl du das C-Backend von itertools nicht schlagen kannst!).

Answer 1

Hier ist eine Implementierung der Callables und iteriert Iterables nennt, die wieder anlauf angenommen werden:

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

Ohne "Iterator-Wiederherstellung" ist möglicherweise der erste der Faktoren möglich. Aber das würde nur 1/n Speicherplatz sparen (wobei n die Anzahl der Faktoren ist) und Verwirrung stiften.

Also die Antwort ist Iterator Erholung. Ein Client der Funktion müsste sicherstellen, dass die Erzeugung der Iteratoren rein ist (keine Nebenwirkungen). Wie

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

Dies kann nicht mit Standard-Python-Generatoren erfolgen, weil einige der Iterables mehrmals durchlaufen werden müssen. Sie müssen einen Datentyp verwenden, der "Wiederholung" ermöglicht. Ich habe eine einfache "wiederholbare" Klasse und einen nicht-rekursiven Produktalgorithmus erstellt. product sollte mehr Fehlerprüfung haben, aber dies ist zumindest ein erster Ansatz. Die einfache reiterable Klasse ...

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

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

Geprüft:

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

Es tut mir leid um bis dieses Thema aber, nachdem er Stunden Debuggen Programm versucht über rekursiv generiertes kartesisches Produkt von Generatoren zu iterieren. Ich kann Ihnen sagen, dass keine der obigen Lösungen funktioniert, wenn nicht wie in allen obigen Beispielen mit konstanten Zahlen gearbeitet wird.

Korrektur:

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 

Wenn Generatoren Generatoren enthalten, müssen Sie eine Kopie an den rekursiven Aufruf zu übergeben.