Lunghezza di un generatore finita

Question

Ho queste due implementazioni per calcolare la lunghezza di un generatore finita, mantenendo i dati per ulteriori elaborazioni:

def count_generator1(generator): 
    '''- build a list with the generator data 
     - get the length of the data 
     - return both the length and the original data (in a list) 
     WARNING: the memory use is unbounded, and infinite generators will block this''' 
    l = list(generator) 
    return len(l), l 

def count_generator2(generator): 
    '''- get two generators from the original generator 
     - get the length of the data from one of them 
     - return both the length and the original data, as returned by tee 
     WARNING: tee can use up an unbounded amount of memory, and infinite generators will block this''' 
    for_length, saved = itertools.tee(generator, 2) 
    return sum(1 for _ in for_length), saved 

Entrambi hanno inconvenienti, sia fare il lavoro. Qualcuno potrebbe commentarli o addirittura offrire un'alternativa migliore?

Answer 1

Se si deve fare questo, il primo metodo è molto meglio - poiché si consumano tutti i valori, itertools.tee() dovrà memorizzare comunque tutti i valori, il che significa che un elenco sarà più efficiente.

di citare the docs:

Questo itertools può richiedere notevole spazio di memoria (a seconda di quantità di dati temporanei devono essere memorizzati). In generale, se un iteratore utilizza la maggior parte o tutti i dati prima che inizi un altro iteratore, è più veloce usare list() invece di tee().

Answer 2

ho corse Windows a 64 bit Python 3.4.3 timeit su alcuni approcci mi veniva in mente:

>>> from timeit import timeit 
>>> from textwrap import dedent as d 
>>> timeit(
...  d(""" 
...  count = -1 
...  for _ in s: 
...   count += 1 
...  count += 1 
...  """), 
...  "s = range(1000)", 
...) 
50.70772041983173 
>>> timeit(
...  d(""" 
...  count = -1 
...  for count, _ in enumerate(s): 
...   pass 
...  count += 1 
...  """), 
...  "s = range(1000)", 
...) 
42.636973504498656 
>>> timeit(
...  d(""" 
...  count, _ = reduce(f, enumerate(range(1000)), (-1, -1)) 
...  count += 1 
...  """), 
...  d(""" 
...  from functools import reduce 
...  def f(_, count): 
...   return count 
...  s = range(1000) 
...  """), 
...) 
121.15513102540672 
>>> timeit("count = sum(1 for _ in s)", "s = range(1000)") 
58.179126025925825 
>>> timeit("count = len(tuple(s))", "s = range(1000)") 
19.777029680237774 
>>> timeit("count = len(list(s))", "s = range(1000)") 
18.145157531932 
>>> timeit("count = len(list(1 for _ in s))", "s = range(1000)") 
57.41422175998332 

Incredibilmente, l'approccio più veloce è stato quello di utilizzare un list (nemmeno un tuple) a esaurire l'iteratore e ottenere la lunghezza da lì:

>>> timeit("count = len(list(s))", "s = range(1000)") 
18.145157531932 

Naturalmente, questo rischia di problemi di memoria. La migliore alternativa a basso memoria è stato quello di utilizzare enumerare su un NOOP for -loop:

>>> timeit(
...  d(""" 
...  count = -1 
...  for count, _ in enumerate(s): 
...   pass 
...  count += 1 
...  """), 
...  "s = range(1000)", 
...) 
42.636973504498656 

Cheers!