Finden des ersten und letzten Index eines Werts in einer Liste in Python

78

Gibt es integrierte Methoden, die Teil von Listen sind, die mir den ersten und letzten Index eines Werts geben würden, wie zum Beispiel:

verts.IndexOf(12.345)
verts.LastIndexOf(12.345)
Joan Venge
quelle
1
Vielleicht sollten Sie die Listen in den Python-Dokumenten nachlesen : docs.python.org/library/stdtypes.html#mutable-sequence-types . Ich denke, das wird viel schneller gehen, als viele Fragen zu stellen.
2
Ich lese sie auch, aber nichts über Python zu wissen macht die Sache schwieriger. Ich finde seine Syntax sehr kryptisch.
Joan Venge
Wenn Ihre Listen sortiert sind, sollten Sie das Halbierungsmodul < docs.python.org/3/library/bisect.html > überprüfen .
Tommy.carstensen
Sehen Sie die brillante Antwort von Dikei hier mit den integrierten Funktionen aufzählen und umkehren: stackoverflow.com/questions/9836425/…
tommy.carstensen

Antworten:

117

Sequenzen haben eine Methode, index(value)die den Index des ersten Auftretens zurückgibt - in Ihrem Fall wäre dies verts.index(value).

Sie können es ausführen verts[::-1], um den letzten Index herauszufinden. Hier wäre daslen(verts) - 1 - verts[::-1].index(value)

SilentGhost
quelle
Danke, wie führt man die Liste [:: - 1] durch? verts [:: - 1]?
Joan Venge
2
Btw verts [:: - 1] kehrt die Liste einfach um, oder? Also muss ich den Index kompensieren, oder?
Joan Venge
12
sicher, es wird sein: len (verts) - 1 - verts [:: - 1] .index (Wert)
SilentGhost
18

Wenn Sie nach dem Index des letzten Auftretens von myvaluein suchen mylist:

len(mylist) - mylist[::-1].index(myvalue) - 1
user2669486
quelle
Dies wirft ein ValueErrorwenn myvaluenicht vorhanden in mylist.
Eugene Yarmash
10

Als kleine Hilfsfunktion:

def rindex(mylist, myvalue):
    return len(mylist) - mylist[::-1].index(myvalue) - 1
Caridorc
quelle
5

Python-Listen verfügen über die index()Methode, mit der Sie die Position des ersten Auftretens eines Elements in einer Liste ermitteln können. Beachten Sie, dass dies list.index()ausgelöst wird, ValueErrorwenn das Element nicht in der Liste vorhanden ist. Daher müssen Sie es möglicherweise in try/ einschließen except:

try:
    idx = lst.index(value)
except ValueError:
    idx = None

Mit der folgenden Funktion können Sie die Position des letzten Auftretens eines Elements in einer Liste effizient ermitteln (dh ohne eine umgekehrte Zwischenliste zu erstellen):

def rindex(lst, value):
    for i, v in enumerate(reversed(lst)):
        if v == value:
            return len(lst) - i - 1  # return the index in the original list
    return None    

print(rindex([1, 2, 3], 3))     # 2
print(rindex([3, 2, 1, 3], 3))  # 3
print(rindex([3, 2, 1, 3], 4))  # None
Eugene Yarmash
quelle
5

Vielleicht die zwei effizientesten Wege, um den letzten Index zu finden :

def rindex(lst, value):
    lst.reverse()
    i = lst.index(value)
    lst.reverse()
    return len(lst) - i - 1
def rindex(lst, value):
    return len(lst) - operator.indexOf(reversed(lst), value) - 1

Beide benötigen nur O (1) zusätzlichen Platz und die beiden direkten Umkehrungen der ersten Lösung sind viel schneller als das Erstellen einer Umkehrkopie. Vergleichen wir es mit den anderen zuvor veröffentlichten Lösungen:

def rindex(lst, value):
    return len(lst) - lst[::-1].index(value) - 1

def rindex(lst, value):
    return len(lst) - next(i for i, val in enumerate(reversed(lst)) if val == value) - 1

Benchmark-Ergebnisse, meine Lösungen sind die roten und grünen: ungemischt, volle Reichweite

Dies dient zum Suchen einer Nummer in einer Liste mit einer Million Nummern. Die x-Achse steht für die Position des gesuchten Elements: 0% bedeutet, dass es am Anfang der Liste steht, 100% bedeutet, dass es am Ende der Liste steht. Alle Lösungen sind am Standort zu 100% am schnellstenreversed Lösungen so gut wie keine Zeit dafür benötigen, die Double-Reverse-Lösung etwas Zeit in Anspruch nimmt und die Reverse-Kopie viel Zeit in Anspruch nimmt.

Ein genauerer Blick auf das rechte Ende: ungemischt, Schwanzteil

Am Standort 100% verbringen die Reverse-Copy-Lösung und die Double-Reverse-Lösung ihre ganze Zeit mit den Umkehrungen (index() erfolgt sofort). Wir sehen also, dass die beiden vorhandenen Umkehrungen etwa siebenmal so schnell sind wie das Erstellen der Umkehrkopie.

Das obige war mit lst = list(range(1_000_000, 2_000_001)), das die int-Objekte so ziemlich sequentiell im Speicher erstellt, was extrem cache-freundlich ist. Machen wir es noch einmal, nachdem wir die Liste mit gemischt haben random.shuffle(lst)(wahrscheinlich weniger realistisch, aber interessant):

gemischte Liste, volle Reichweite

gemischte Liste, Schwanzteil

Wie erwartet wurde alles viel langsamer. Die Reverse-Copy-Lösung leidet am meisten. Mit 100% dauert sie jetzt etwa 32-mal (!) So lange wie die Double-Reverse-Lösung. Und die enumerate-Lösung ist jetzt erst nach Standort 98% die zweitschnellste.

Insgesamt gefällt mir die operator.indexOfLösung am besten, da sie die schnellste für die letzte Hälfte oder das letzte Viertel aller Standorte ist. Dies sind möglicherweise die interessanteren Standorte, wenn Sie dies tatsächlich tunrindex etwas . Und es ist nur ein bisschen langsamer als die Double-Reverse-Lösung an früheren Standorten.

Alle Benchmarks mit CPython 3.9.0 64-Bit unter Windows 10 Pro 1903 64-Bit.

Stefan Pochmann
quelle
0

Diese Methode kann optimiert werden als oben

def rindex(iterable, value):
    try:
        return len(iterable) - next(i for i, val in enumerate(reversed(iterable)) if val == value) - 1
    except StopIteration:
        raise ValueError
111
quelle
4
"Optimiert" in dem Sinne, dass es platzsparender ist, aber es ist ungefähr 50% langsamer.
Dubiousjim
0
s.index(x[, i[, j]])

Index des ersten Auftretens von x in s (am oder nach dem Index i und vor dem Index j)

Qinsheng Zhang
quelle