Suche nach dem ersten und letzten Index eines Wertes in einer Liste in Python

Question

Gibt es irgendwelche eingebauten Methoden, die Teil von Listen sind, die mir den ersten und letzten Index eines Wertes geben würde, wie:

verts.IndexOf(12.345)
verts.LastIndexOf(12.345)

Answer 1

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

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

Answer 2

Vielleicht sind die beiden effizientesten Wege, die zuletzt Index:

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 zwei Die Umkehrung der ersten Lösung an Ort und Stelle ist viel schneller als die Erstellung einer umgekehrten Kopie. Vergleichen wir sie 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:

Dies dient der Suche nach einer Zahl in einer Liste mit einer Million Zahlen. Die x-Achse gibt die Position des gesuchten Elements an: 0% bedeutet, dass es sich am Anfang der Liste befindet, 100% bedeutet, dass es sich am Ende der Liste befindet. Alle Lösungen sind an der Stelle 100% am schnellsten, wobei die beiden reversed Lösungen, die so gut wie keine Zeit in Anspruch nehmen, die doppelt umgekehrte Lösung, die ein wenig Zeit in Anspruch nimmt, und die umgekehrte Kopie, die sehr viel Zeit in Anspruch nimmt.

Ein genauerer Blick auf das rechte Ende:

An der Stelle 100 % verbringen die Umkehrkopie-Lösung und die Doppelumkehr-Lösung ihre gesamte Zeit mit den Umkehrungen ( index() ist sofort), so dass die beiden Umkehrungen an Ort und Stelle etwa siebenmal so schnell sind wie die Erstellung der umgekehrten Kopie.

Die obigen Ausführungen wurden mit lst = list(range(1_000_000, 2_000_001)) die die int-Objekte quasi sequentiell im Speicher erstellt, was extrem cache-freundlich ist. Wiederholen wir das Ganze, nachdem wir die Liste mit random.shuffle(lst) (wahrscheinlich weniger realistisch, aber interessant):

Wie erwartet, wurden alle viel langsamer. Die Lösung mit der umgekehrten Kopie leidet am meisten, sie braucht jetzt bei 100 % etwa 32 Mal (!) so lange wie die Lösung mit der doppelten Umkehrung. Und die enumerate -Lösung ist nun die zweitschnellste nach dem Standort 98%.

Insgesamt gefällt mir die operator.indexOf Lösung am besten, da sie die schnellste für die letzte Hälfte oder das letzte Viertel aller Orte ist, die vielleicht die interessanteren Orte sind, wenn Sie tatsächlich etwas tun wollen. rindex für etwas. Und sie ist nur ein bisschen langsamer als die Lösung mit doppelter Umkehrung an früheren Standorten.

Alle Benchmarks wurden mit CPython 3.9.0 64-bit auf Windows 10 Pro 1903 64-bit durchgeführt.

Answer 3

Wenn Sie nach dem Index des letzten Vorkommens von myvalue sur mylist :

len(mylist) - mylist[::-1].index(myvalue) - 1

Answer 4

Als kleine Hilfsfunktion:

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

Answer 5

Python-Listen haben die index() Methode, die Sie verwenden können, um die Position des erste Auftreten eines Elements in einer Liste. Beachten Sie, dass list.index() hebt ValueError wenn das Element nicht in der Liste vorhanden ist, müssen Sie es also möglicherweise in try / except :

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

So finden Sie die Position der zuletzt Auftreten eines Elements in einer Liste auf effiziente Weise (d. h. ohne Erstellung einer umgekehrten Zwischenliste) können Sie diese Funktion verwenden:

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