Abrufen der Anzahl der Elemente in einem Iterator in Python

137

Gibt es eine effiziente Methode, um zu wissen, wie viele Elemente sich in Python im Allgemeinen in einem Iterator befinden, ohne jedes Element zu durchlaufen und zu zählen?

Tomasz Wysocki
quelle

Antworten:

101

Nein, es ist nicht möglich.

Beispiel:

import random

def gen(n):
    for i in xrange(n):
        if random.randint(0, 1) == 0:
            yield i

iterator = gen(10)

Die Länge von iteratorist unbekannt, bis Sie sie durchlaufen.

Tomasz Wysocki
quelle
14
Alternativ def gen(): yield random.randint(0, 1)ist unendlich, so dass Sie niemals eine Länge finden können, indem Sie sie durchlaufen.
Tgray
1
Um das Offensichtliche zu bestätigen: Der beste Weg, um die "Größe" eines Iterators zu ermitteln, besteht darin, einfach zu zählen, wie oft Sie die Iteration durchlaufen haben, oder? In diesem Fall wäre es numIters = 0 ; while iterator: numIters +=1?
Mike Williamson
Interessant, also ist es das Halteproblem
Akababa
230

Dieser Code sollte funktionieren:

>>> iter = (i for i in range(50))
>>> sum(1 for _ in iter)
50

Obwohl jedes Element durchlaufen und gezählt wird, ist dies der schnellste Weg.

Es funktioniert auch, wenn der Iterator kein Element hat:

>>> sum(1 for _ in range(0))
0

Natürlich läuft es für immer für eine unendliche Eingabe. Denken Sie also daran, dass Iteratoren unendlich sein können:

>>> sum(1 for _ in itertools.count())
[nothing happens, forever]

Beachten Sie außerdem, dass der Iterator dadurch erschöpft ist und bei weiteren Versuchen, ihn zu verwenden, keine Elemente angezeigt werden . Dies ist eine unvermeidbare Folge des Python-Iterator-Designs. Wenn Sie die Elemente behalten möchten, müssen Sie sie in einer Liste oder etwas anderem speichern.

John Howard
quelle
10
Sieht für mich so aus, als würde dies genau das tun, was OP nicht tun möchte: durch den Iterator iterieren und zählen.
Adam Crossland
36
Dies ist eine platzsparende Methode, um die Elemente in einer iterierbaren zu zählen
Captain Lepton
9
Obwohl dies nicht das ist, was OP will, da seine Frage keine Antwort hat, vermeidet diese Antwort die Instanziierung einer Liste und ist empirisch um eine Konstante schneller als die oben aufgeführte Reduktionsmethode.
Phillip Nordwall
5
Kann nicht helfen: Ist der _Verweis auf Perl $_? :)
Alois Mahdal
17
@AloisMahdal Nein. In Python ist es üblich, den Namen _für eine Dummy-Variable zu verwenden, deren Wert Sie nicht interessieren.
Taymon
67

Nein, für jede Methode müssen Sie jedes Ergebnis auflösen. Du kannst tun

iter_length = len(list(iterable))

Aber wenn Sie das auf einem unendlichen Iterator ausführen, wird dies natürlich niemals zurückkehren. Es wird auch den Iterator verbrauchen und muss zurückgesetzt werden, wenn Sie den Inhalt verwenden möchten.

Wenn Sie uns mitteilen, welches echte Problem Sie lösen möchten, finden Sie möglicherweise einen besseren Weg, um Ihr eigentliches Ziel zu erreichen.

Bearbeiten: Mit list()wird das gesamte iterierbare Element sofort in den Speicher eingelesen, was möglicherweise unerwünscht ist. Ein anderer Weg ist zu tun

sum(1 for _ in iterable)

als eine andere Person gepostet. Dadurch wird vermieden, dass es im Speicher bleibt.

Daenyth
quelle
Das Problem ist, dass ich eine Datei mit "pysam" lese, die Millionen von Einträgen enthält. Pysam gibt einen Iterator zurück. Um eine bestimmte Menge zu berechnen, muss ich wissen, wie viele Lesevorgänge in der Datei enthalten sind, aber ich muss nicht jeden einzelnen lesen ... das ist das Problem.
6
Ich bin kein Pysam-Benutzer, aber es liest wahrscheinlich die Datei "faul". Es ist sinnvoll, weil Sie keine große Datei im Speicher haben möchten. Also, wenn Sie nein wissen müssen. Bei Datensätzen vor der Iteration werden nur zwei Iteratoren erstellt und der erste zum Zählen der Elemente und der zweite zum Lesen der Datei verwendet. Übrigens. Wenn Sie es nicht verwenden len(list(iterable)), werden alle Daten in den Speicher geladen. Sie können verwenden : reduce(lambda x, _: x+1, iterable, 0). Edit: Zonda333 Code mit Summe ist auch gut.
Tomasz Wysocki
1
@ user248237: Warum müssen Sie wissen, wie viele Einträge verfügbar sind, um eine bestimmte Menge zu berechnen? Sie können einfach eine feste Menge davon lesen und den Fall verwalten, wenn weniger als diese feste Menge vorhanden ist (ganz einfach mit iterslice). Gibt es einen anderen Grund, warum Sie alle Einträge lesen müssen?
Kriss
1
@Tomasz Beachten Sie, dass Reduzieren veraltet ist und in Python 3 und höher nicht mehr angezeigt wird.
Wilduck
7
@ Wilduck: Es ist nicht weg, nur umgezogen zufunctools.reduce
Daenyth
33

Sie können nicht (außer der Typ eines bestimmten Iterators implementiert einige spezifische Methoden, die dies ermöglichen).

Im Allgemeinen können Sie Iteratorelemente nur zählen, indem Sie den Iterator verwenden. Eine der wahrscheinlich effizientesten Möglichkeiten:

import itertools
from collections import deque

def count_iter_items(iterable):
    """
    Consume an iterable not reading it into memory; return the number of items.
    """
    counter = itertools.count()
    deque(itertools.izip(iterable, counter), maxlen=0)  # (consume at C speed)
    return next(counter)

(Für Python 3.x ersetzen itertools.izipdurch zip).

zuo
quelle
3
+1: Im Zeitvergleich mit sum(1 for _ in iterator)war dies fast doppelt so schnell.
Augustomen
1
Es ist genauer zu sagen, dass es ein Iterable verbraucht, indem jedes Element in den Speicher eingelesen und sofort verworfen wird.
Rockallite
Es ist wichtig zu beachten , (die ich übersehen) , dass die Reihenfolge der Argumente zu zipFragen : Wenn Sie weitergeben zip(counter, iterable), die Sie tatsächlich 1 mehr als die iterable Zählung bekommen!
Kye W Shi
sehr schöne Antwort. würde Kopfgeld darauf geben.
Reut Sharabani
18

Irgendwie. Sie könnten die __length_hint__Methode überprüfen , aber seien Sie gewarnt, dass es sich (zumindest bis zu Python 3.4, wie gsnedders hilfreich hervorhebt) um ein undokumentiertes Implementierungsdetail handelt ( folgende Meldung im Thread ), das sehr gut verschwinden oder stattdessen Nasendämonen beschwören könnte.

Ansonsten nein. Iteratoren sind nur ein Objekt, das nur die next()Methode verfügbar macht . Sie können es so oft wie nötig aufrufen und sie können eventuell erhöhen oder auch nicht StopIteration. Glücklicherweise ist dieses Verhalten für den Codierer die meiste Zeit transparent. :) :)

badp
quelle
5
Dies ist ab PEP 424 und Python 3.4 nicht mehr der Fall . __length_hint__ist jetzt dokumentiert, aber es ist ein Hinweis und gibt keine Garantie für die Richtigkeit.
Gsnedders
12

Ich mag das Kardinalitätspaket dafür, es ist sehr leicht und versucht, die schnellstmögliche Implementierung zu verwenden, die je nach Iterable verfügbar ist.

Verwendung:

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

Die tatsächliche count()Implementierung ist wie folgt:

def count(iterable):
    if hasattr(iterable, '__len__'):
        return len(iterable)

    d = collections.deque(enumerate(iterable, 1), maxlen=1)
    return d[0][0] if d else 0
Erwin Mayer
quelle
Ich gehe davon aus, dass Sie immer noch über den Iterator iterieren können, wenn Sie diese Funktion verwenden, ja?
JCollum
12

Also für diejenigen, die die Zusammenfassung dieser Diskussion wissen möchten. Die endgültigen Bestnoten für die Zählung eines Generatorausdrucks mit einer Länge von 50 Millionen unter Verwendung von:

  • len(list(gen)),
  • len([_ for _ in gen]),
  • sum(1 for _ in gen),
  • ilen(gen)(von more_itertool ),
  • reduce(lambda c, i: c + 1, gen, 0),

sortiert nach Ausführungsleistung (einschließlich Speicherverbrauch) werden Sie überrascht sein:

`` `

1: test_list.py:8: 0.492 KiB

gen = (i for i in data*1000); t0 = monotonic(); len(list(gen))

('list, sec', 1.9684218849870376)

2: test_list_compr.py:8: 0.867 KiB

gen = (i for i in data*1000); t0 = monotonic(); len([i for i in gen])

('list_compr, sec', 2.5885991149989422)

3: test_sum.py:8: 0,859 KiB

gen = (i for i in data*1000); t0 = monotonic(); sum(1 for i in gen); t1 = monotonic()

('sum, sec', 3.441088170016883)

4: more_itertools / more.py: 413: 1,266 KiB

d = deque(enumerate(iterable, 1), maxlen=1)

test_ilen.py:10: 0.875 KiB
gen = (i for i in data*1000); t0 = monotonic(); ilen(gen)

('ilen, sec', 9.812256851990242)

5: test_reduce.py:8: 0.859 KiB

gen = (i for i in data*1000); t0 = monotonic(); reduce(lambda counter, i: counter + 1, gen, 0)

('reduzieren, sek', 13.436614598002052) `` `

Ist len(list(gen))also der häufigste und am wenigsten verbrauchbare Speicher

Alex-Bogdanov
quelle
Wie haben Sie den Speicherverbrauch gemessen?
Normanius
Können Sie erklären, warum len(list(gen))weniger Speicher verbraucht werden sollte als der auf Reduzieren basierende Ansatz? Ersteres erstellt ein neues list, das eine Speicherzuweisung beinhaltet, während letzteres dies nicht tun sollte. Daher würde ich erwarten, dass Letzteres speichereffizienter ist. Der Speicherverbrauch hängt auch vom Elementtyp ab.
Normanius
Zu Ihrer Information: Ich kann für Python 3.6.8 (auf einem MacBookPro) reproduzieren, dass Methode 1 die anderen Methoden in Bezug auf die Laufzeit übertrifft (ich habe Methode 4 übersprungen).
Normanius
len(tuple(iterable))kann noch effizienter sein: Artikel von Nelson Minar
VMAtm
9

Ein Iterator ist nur ein Objekt, das einen Zeiger auf das nächste Objekt hat, das von einer Art Puffer oder Stream gelesen werden soll. Es ist wie eine LinkedList, in der Sie nicht wissen, wie viele Dinge Sie haben, bis Sie sie durchlaufen. Iteratoren sollen effizient sein, da sie Ihnen lediglich anhand von Referenzen mitteilen, was als nächstes kommt, anstatt die Indizierung zu verwenden (aber wie Sie gesehen haben, verlieren Sie die Fähigkeit, zu sehen, wie viele Einträge als nächstes kommen).

Jesus Ramos
quelle
2
Ein Iterator ist nichts anderes als eine verknüpfte Liste. Ein von einem Iterator zurückgegebenes Objekt zeigt nicht auf das nächste Objekt, und diese Objekte werden (notwendigerweise) nicht im Speicher gespeichert. Vielmehr kann es ein Objekt nach dem anderen ergeben, basierend auf der inneren Logik (die auf einer gespeicherten Liste basieren könnte, aber nicht muss).
Tom
1
@ Tom Ich habe LinkedList als Beispiel verwendet, hauptsächlich, weil Sie nicht wissen, wie viel Sie haben, da Sie nur in gewissem Sinne wissen, was als nächstes kommt (wenn es etwas gibt). Ich entschuldige mich, wenn mein Wortlaut ein wenig falsch erscheint oder wenn ich angedeutet habe, dass sie ein und dasselbe sind.
Jesus Ramos
8

In Bezug auf Ihre ursprüngliche Frage lautet die Antwort immer noch, dass es im Allgemeinen keine Möglichkeit gibt, die Länge eines Iterators in Python zu ermitteln.

Da Ihre Frage durch eine Anwendung der Pysam-Bibliothek motiviert ist, kann ich eine genauere Antwort geben: Ich bin ein Mitwirkender an PySAM und die endgültige Antwort lautet, dass SAM / BAM-Dateien keine exakte Anzahl ausgerichteter Lesevorgänge liefern. Diese Informationen sind auch nicht leicht aus einer BAM-Indexdatei verfügbar. Das Beste, was Sie tun können, ist, die ungefähre Anzahl von Ausrichtungen zu schätzen, indem Sie die Position des Dateizeigers verwenden, nachdem Sie eine Anzahl von Ausrichtungen gelesen und basierend auf der Gesamtgröße der Datei extrapoliert haben. Dies reicht aus, um einen Fortschrittsbalken zu implementieren, jedoch keine Methode zum Zählen von Ausrichtungen in konstanter Zeit.

Kevin Jacobs
quelle
6

Ein kurzer Maßstab:

import collections
import itertools

def count_iter_items(iterable):
    counter = itertools.count()
    collections.deque(itertools.izip(iterable, counter), maxlen=0)
    return next(counter)

def count_lencheck(iterable):
    if hasattr(iterable, '__len__'):
        return len(iterable)

    d = collections.deque(enumerate(iterable, 1), maxlen=1)
    return d[0][0] if d else 0

def count_sum(iterable):           
    return sum(1 for _ in iterable)

iter = lambda y: (x for x in xrange(y))

%timeit count_iter_items(iter(1000))
%timeit count_lencheck(iter(1000))
%timeit count_sum(iter(1000))

Die Ergebnisse:

10000 loops, best of 3: 37.2 µs per loop
10000 loops, best of 3: 47.6 µs per loop
10000 loops, best of 3: 61 µs per loop

Dh die einfachen count_iter_items sind der richtige Weg.

Anpassen für python3:

61.9 µs ± 275 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
74.4 µs ± 190 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
82.6 µs ± 164 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Michael
quelle
Hinweis: Dieser Test basiert auf python2
normanius
3

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 alles, was die Datei / Daten berührt, um sie zu ändern (oder eine Klasse, die nur Schnittstellen verfügbar macht -, aber es läuft auf dasselbe hinaus).

Die andere Möglichkeit besteht darin, darüber zu iterieren und zu zählen, wie groß es ist.

Wayne Werner
quelle
0

Es ist gängige Praxis, diese Art von Informationen in den Datei-Header einzufügen und mit pysam Zugriff darauf zu erhalten. Ich kenne das Format nicht, aber haben Sie die API überprüft?

Wie andere gesagt haben, können Sie die Länge des Iterators nicht kennen.

tom10
quelle
0

Dies widerspricht der Definition eines Iterators, der ein Zeiger auf ein Objekt ist, sowie Informationen darüber, wie Sie zum nächsten Objekt gelangen.

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

FCAlive
quelle
Es verstößt gegen nichts und es ist nichts Falsches daran, Vorkenntnisse anzuwenden, wenn ein Iterator verwendet wird. Es gibt zig Millionen Iteratoren, bei denen Sie wissen, dass die Anzahl der Elemente begrenzt ist. Denken Sie daran, einfach eine Liste zu filtern. Sie können leicht die maximale Länge angeben. Sie wissen nur nicht genau, wie viele Elemente tatsächlich zu Ihrer Filterbedingung passen. Die Anzahl der übereinstimmenden Elemente wissen zu wollen, ist eine gültige Anwendung, die keine mysteriöse Idee eines Iterators verletzt.
Michael
0

Obwohl es im Allgemeinen nicht möglich ist, das zu tun, was gefragt wurde, ist es oft nützlich, zu zählen, wie viele Elemente nach dem Durchlaufen wiederholt wurden. Dafür können Sie jaraco.itertools.Counter oder ähnliches verwenden. Hier ist ein Beispiel mit Python 3 und rwt zum Laden des Pakets.

$ 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
Jason R. Coombs
quelle
-1
def count_iter(iter):
    sum = 0
    for _ in iter: sum += 1
    return sum
hasen
quelle
-1

Vermutlich möchten Sie die Anzahl der Elemente zählen, ohne sie zu durchlaufen, damit der Iterator nicht erschöpft ist und Sie ihn später erneut verwenden. Dies ist mit copyoder möglichdeepcopy

import copy

def get_iter_len(iterator):
    return sum(1 for _ in copy.copy(iterator))

###############################################

iterator = range(0, 10)
print(get_iter_len(iterator))

if len(tuple(iterator)) > 1:
    print("Finding the length did not exhaust the iterator!")
else:
    print("oh no! it's all gone")

Die Ausgabe ist " Finding the length did not exhaust the iterator!"

Optional (und nicht empfohlen) können Sie die integrierte lenFunktion wie folgt schattieren :

import copy

def len(obj, *, len=len):
    try:
        if hasattr(obj, "__len__"):
            r = len(obj)
        elif hasattr(obj, "__next__"):
            r = sum(1 for _ in copy.copy(obj))
        else:
            r = len(obj)
    finally:
        pass
    return r
Zahnstocher Anemone
quelle
1
Bereiche sind keine Iteratoren. Es gibt einige Iteratortypen, die kopiert werden können, andere führen jedoch dazu, dass dieser Code mit einem TypeError (z. B. Generatoren) fehlschlägt. Das Durchlaufen eines kopierten Iterators kann dazu führen, dass Nebenwirkungen zweimal auftreten oder dass der Code willkürlich beschädigt wird. gab einen mapIterator zurück, der erwartete, dass die resultierenden Funktionsaufrufe nur einmal auftreten würden.
user2357112 unterstützt Monica