Länge eines endlichen Generator

Question

Ich habe diese beiden Implementierungen, die Länge eines endlichen Generator zu berechnen, während die Daten für die Weiterverarbeitung zu halten:

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 

Beide haben Nachteile, die beide die Arbeit machen. Könnte jemand sie kommentieren oder sogar eine bessere Alternative anbieten?

Answer 1

Wenn Sie dies tun müssen, ist die erste Methode viel besser - wie Sie alle Werte verbrauchen, muss itertools.tee() alle Werte trotzdem speichern, was bedeutet, dass eine Liste effizienter sein wird.

Zitat aus the docs:

Diese itertool können erhebliche Zusatzspeicher erforderlich (je nach wie viele temporären Daten gespeichert werden muss). Im Allgemeinen, wenn ein Iterator die meisten oder alle Daten verwendet, bevor ein anderer Iterator startet, ist es schneller, list() anstelle von tee() zu verwenden, .

Answer 2

Ich lief Windows 64-Bit-Python 3.4.3 timeit auf ein paar Ansätze, die ich denken konnte:

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

Schockierend, der schnellste Ansatz ein list (nicht einmal ein tuple) zu verwenden, war zu Erschöpfen Sie den Iterator und erhalten Sie die Länge von dort:

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

Natürlich gefährdet dies Speicherprobleme. Die beste Low-Memory-Alternative war auf einem NOOP for -loop aufzählen zu verwenden:

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

Prost!