Jaki jest najkrótszy sposób policzenia liczby elementów w generatorze / iteratorze?

Metoda, która jest znacznie szybsza niż sum(1 for i in it), gdy iterable może być długi (a nie znacznie wolniejszy, gdy iterable jest krótki), przy zachowaniu stałego narzutu pamięci (w przeciwieństwie do len(list(it))), Aby uniknąć wymiany narzutu i realokacji na większe wejścia:

# On Python 2 only, get zip that lazily generates results instead of returning list
from future_builtins import zip

from collections import deque
from itertools import count

def ilen(it):
    # Make a stateful counting iterator
    cnt = count()
    # zip it with the input iterator, then drain until input exhausted at C level
    deque(zip(it, cnt), 0) # cnt must be second zip arg to avoid advancing too far
    # Since count 0 based, the next value is the count
    return next(cnt)

Podobnie jak len(list(it)) wykonuje pętlę w kodzie C na Cpythonie (deque, count i zip są zaimplementowane w C); unikanie wykonania kodu bajtowego na pętlę jest zwykle kluczem do wydajności w CPython.

Zaskakująco trudno jest wymyślić uczciwe przypadki testowe do porównywania wydajności (list cheaty przy użyciu __length_hint__, które prawdopodobnie nie będą dostępne dla dowolnych iterabli wejściowych, itertools funkcje, które nie dostarczają __length_hint__ często mają specjalne tryby pracy, które działają szybciej, gdy wartość zwracana w każdej pętli jest zwolniona / zwolniona przed żądaniem następnej wartości, co deque z maxlen=0 wystarczy). Przypadek testowy, którego użyłem, polegał na stworzeniu funkcji generatora, która zajęłaby wprowadzenie i zwrócenie generatora poziomu C, który nie miał specjalnych itertools zwraca optymalizacje kontenera lub __length_hint__, używając Pythona 3.3 yield from:

def no_opt_iter(it):
    yield from it

Następnie używając ipython %timeit Magia (podstawienie różnych stałych dla 100):

>>> %%timeit -r5 fakeinput = (0,) * 100
... ilen(no_opt_iter(fakeinput))

Gdy wejście nie jest wystarczająco duże, aby len(list(it)) powodowało problemy z pamięcią, na Linuksie z Pythonem 3.5 x64 moje rozwiązanie trwa około 50% dłużej niż def ilen(it): return len(list(it)), niezależnie od długości wejścia.

Dla najmniejszego z wejść, konfiguracja kosztuje call deque/zip/count/next oznacza to, że w ten sposób zajmuje nieskończenie dużo więcej czasu niż def ilen(it): sum(1 for x in it) (około 200 ns więcej na mojej maszynie dla wejścia o długości 0, co jest 33% wzrostem w porównaniu z prostym podejściem sum), ale dla dłuższych wejść, działa w około połowie czasu na dodatkowy element; dla wejść o długości 5, koszt jest równoważny, a gdzieś w zakresie długości 50-100, początkowy narzut jest niezauważalny w porównaniu z rzeczywistą pracą; podejście {27]} zajmuje mniej więcej dwa razy więcej czasu niż w rzeczywistości; długa.

Zasadniczo, jeśli użycie pamięci ma znaczenie lub dane wejściowe nie mają ograniczonego rozmiaru i zależy Ci bardziej na szybkości niż zwięzłości, użyj tego rozwiązania. Jeśli Dane wejściowe są ograniczone i małe, len(list(it)) jest prawdopodobnie najlepsze, a jeśli są nieograniczone, ale liczy się prostota/zwięzłość, użyjesz sum(1 for x in it).

Krótka droga to:

def ilen(it):
    return len(list(it))

Zauważ, że jeśli generujesz partię elementów (powiedzmy dziesiątki tysięcy lub więcej), umieszczenie ich na liście może stać się problemem z wydajnością. Jest to jednak proste wyrażenie idei, w której wydajność nie będzie miała znaczenia w większości przypadków.

more_itertools jest biblioteką innej firmy, która implementuje ilen narzędzie. pip install more_itertools

import more_itertools as mit


mit.ilen(x for x in range(10))
# 10

Podoba mi się pakiet cardinality do tego jest bardzo lekki i stara się wykorzystać jak najszybszą dostępną implementację w zależności od iterable.

Użycie:

>>> import cardinality
>>> cardinality.count([1, 2, 3])
3
>>> cardinality.count(i for i in range(500))
500
>>> def gen():
...     yield 'hello'
...     yield 'world'
>>> cardinality.count(gen())
2

To byłby mój wybór albo jeden, albo drugi:

print(len([*gen]))
print(len(list(gen)))

len(list(it))