Anzahl der Elemente in einem Iterator in Python ermitteln

Question

Gibt es einen effizienten Weg, um zu wissen, wie viele Elemente in einem Iterator in Python, im Allgemeinen, ohne Iteration durch jedes und Zählen sind?

Answer 1

Es gibt zwei Möglichkeiten, die Länge von "etwas" auf einem Computer zu ermitteln.

Die erste Möglichkeit besteht darin, eine Zählung zu speichern - dies erfordert, dass alles, was die Datei/Daten berührt, sie verändert (oder eine Klasse, die nur Schnittstellen offenlegt - aber es läuft auf dasselbe hinaus).

Die andere Möglichkeit ist, sie zu iterieren und zu zählen, wie groß sie ist.

Answer 2

Ich dachte, es könnte sich lohnen, einen Mikro-Benchmark durchzuführen, in dem die Laufzeiten der verschiedenen hier genannten Ansätze verglichen werden.

Haftungsausschluss: Ich benutze simple_benchmark (eine von mir geschriebene Bibliothek) für die Benchmarks verwenden und auch iteration_utilities.count_items (eine von mir geschriebene Funktion in einer Drittanbieter-Bibliothek).

Um ein differenzierteres Ergebnis zu erhalten, habe ich zwei Benchmarks durchgeführt, einen nur mit den Ansätzen, die keinen Zwischencontainer bauen, um ihn dann wegzuwerfen, und einen mit diesen:

from simple_benchmark import BenchmarkBuilder
import more_itertools as mi
import iteration_utilities as iu

b1 = BenchmarkBuilder()
b2 = BenchmarkBuilder()

@b1.add_function()
@b2.add_function()
def summation(it):
    return sum(1 for _ in it)

@b1.add_function()
def len_list(it):
    return len(list(it))

@b1.add_function()
def len_listcomp(it):
    return len([_ for _ in it])

@b1.add_function()
@b2.add_function()
def more_itertools_ilen(it):
    return mi.ilen(it)

@b1.add_function()
@b2.add_function()
def iteration_utilities_count_items(it):
    return iu.count_items(it)

@b1.add_arguments('length')
@b2.add_arguments('length')
def argument_provider():
    for exp in range(2, 18):
        size = 2**exp
        yield size, [0]*size

r1 = b1.run()
r2 = b2.run()

import matplotlib.pyplot as plt

f, (ax1, ax2) = plt.subplots(2, 1, sharex=True, figsize=[15, 18])
r1.plot(ax=ax2)
r2.plot(ax=ax1)
plt.savefig('result.png')

Die Ergebnisse waren:

Es werden log-log-Achsen verwendet, so dass alle Bereiche (kleine Werte, große Werte) untersucht werden können. Da die Diagramme für einen qualitativen Vergleich gedacht sind, sind die tatsächlichen Werte nicht allzu interessant. Im Allgemeinen steht die y-Achse (vertikal) für die Zeit und die x-Achse (horizontal) für die Anzahl der Elemente in der Eingabe-"iterable". Je niedriger der Wert auf der vertikalen Achse, desto schneller.

Die obere Grafik zeigt die Ansätze, bei denen keine Zwischenliste verwendet wurde. Dies zeigt, dass die iteration_utilities war der schnellste Ansatz, gefolgt von more_itertools und am langsamsten war die Verwendung von sum(1 for _ in iterator) .

Das untere Diagramm enthält auch die Ansätze, bei denen len() auf einer Zwischenliste, einmal mit list und einmal mit einem Listenverständnis. Der Ansatz mit len(list) war hier am schnellsten, aber der Unterschied zum iteration_utilities Ansatz ist nahezu vernachlässigbar. Der Ansatz mit dem Verständnis war deutlich langsamer als der mit list direkt.

Zusammenfassung

Jeder hier erwähnte Ansatz zeigte eine Abhängigkeit von der Länge der Eingabe und iterierte über jedes Element in der Iterable. Es gibt keine Möglichkeit, die Länge ohne die Iteration zu ermitteln (selbst wenn die Iteration ausgeblendet ist).

Wenn Sie keine Erweiterungen von Drittanbietern wünschen, sollten Sie len(list(iterable)) ist definitiv der schnellste Ansatz der getesteten Ansätze, er erzeugt jedoch eine Zwischenliste, die könnte erheblich mehr Speicherplatz verwenden.

Wenn Sie nichts gegen zusätzliche Pakete haben, dann iteration_utilities.count_items wäre fast so schnell wie die len(list(...)) Funktion, benötigt aber keinen zusätzlichen Speicherplatz.

Es ist jedoch wichtig zu beachten, dass der Mikro-Benchmark eine Liste als Eingabe verwendet. Das Ergebnis des Benchmarks könnte anders ausfallen, je nachdem, welche Iterabilien Sie abfragen möchten. Ich habe auch getestet mit range und eine einfache Genertor-Expression und die Trends waren sehr ähnlich, aber ich kann nicht ausschließen, dass sich das Timing nicht je nach Art der Eingabe ändert.

Answer 3

Dies verstößt gegen die eigentliche Definition eines Iterators, der ein Zeiger auf ein Objekt sowie Informationen darüber ist, wie man zum nächsten Objekt gelangt.

Ein Iterator weiß nicht, wie oft er noch iterieren kann, bis er abbricht. Dies könnte unendlich sein, also könnte unendlich Ihre Antwort sein.

Answer 4

Eine einfache Möglichkeit ist die Verwendung von set() eingebaute Funktion:

iter = zip([1,2,3],['a','b','c'])
print(len(set(iter)) # set(iter) = {(1, 'a'), (2, 'b'), (3, 'c')}
Out[45]: 3

o

iter = range(1,10)
print(len(set(iter)) # set(iter) = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Out[47]: 9

Answer 5

Obwohl es im Allgemeinen nicht möglich ist, das zu tun, worum man gebeten wurde, ist es dennoch oft nützlich, eine Übersicht darüber zu haben, wie viele Elemente durchlaufen wurden nach nachdem er über sie iteriert hat. Dazu können Sie verwenden jaraco.itertools.Zähler oder ähnlich. Hier ist ein Beispiel mit Python 3 und rwt um das Paket zu laden.

$ rwt -q jaraco.itertools -- -q
>>> import jaraco.itertools
>>> items = jaraco.itertools.Counter(range(100))
>>> _ = list(counted)
>>> items.count
100
>>> import random
>>> def gen(n):
...     for i in range(n):
...         if random.randint(0, 1) == 0:
...             yield i
... 
>>> items = jaraco.itertools.Counter(gen(100))
>>> _ = list(counted)
>>> items.count
48