Come sapere che una sequenza generata è al massimo una certa lunghezza

Question

Voglio sapere se una sequenza generata ha meno di 2 voci.

>>> def sequence(): 
...  for i in xrange(secret): 
...   yield i 

Il mio metodo inefficiente è quello di creare una lista, e misurare la sua lunghezza:

>>> secret = 5 
>>> len(list(sequence())) < 2 
True 

Ovviamente, questo consuma l'intero generatore.

Nel mio caso reale il generatore potrebbe attraversare una grande rete. Voglio fare il controllo senza consumare l'intero generatore o costruire una grande lista.

C'è un recipe in the itertools documentation:

def take(n, iterable): 
    "Return first n items of the iterable as a list" 
    return list(islice(iterable, n)) 

Si costruisce solo un elenco di lunghezza massima n, che è meglio.

Così ho potuto dire:

>>> len(take(2, sequence()) < 2 

Esiste un modo efficiente ancora più divinatorio di farlo?

Answer 1

La soluzione con take utilizza islice, crea un elenco e prende la lunghezza di esso:

>>> from itertools import islice 
>>> len(list(islice(sequence(), 2)) 
2 

per evitare di creare la lista possiamo usare sum:

01.235.164,106 mila

>>> sum(1 for _ in islice(sequence(), 2) 
2 

Questa operazione richiede circa il 70% del tempo:

>>> timeit('len(list(islice(xrange(1000), 2)))', 'from itertools import islice') 
1.089650974650752 

>>> timeit('sum(1 for _ in islice(xrange(1000), 2))', 'from itertools import islice') 
0.7579448552500647 

avvolgendolo:

>>> def at_most(n, elements): 
...  return sum(1 for _ in islice(elements, n + 1)) <= n 

>>> at_most(5, xrange(5)) 
True 

>>> at_most(2, xrange(5)) 
False 

Answer 2

A partire da Python 3.4, i generatori possono implementare un length hint. Se un generatore implementa questo sarà esposto attraverso il object.__length_hint__() method.

È possibile testarlo con lo operator.length_hint() function.

Se è non disponibili, l'unica opzione è di consumare gli elementi, e l'utilizzo della ricetta take() è il modo più efficace per farlo:

from operator import length_hint 
from itertools import chain 

elements = [] 
length = length_hint(gen, None) 
if length is None: 
    elements = list(take(2, gen)) 
    length = len(elements) 
if length >= 2: 
    # raise an error 
# use elements, then gen 
gen = chain(elements, gen)