Finden Sie den Index des n-ten Eintrags in einer Liste
Ich möchte den Index des n-ten Vorkommens eines Elements in einer Liste finden. z.B.,
x=[False,True,True,False,True,False,True,False,False,False,True,False,True]
Was ist der Index der n-ten Wahrheit? Wenn ich das fünfte Vorkommen wollte (4., wenn es sich um null indexiert), lautet die Antwort 10.
Ich habe mir ausgedacht mit:
indargs = [ i for i,a in enumerate(x) if a ]
indargs[n]
Beachten Sie, dass x.index das erste Vorkommen oder das erste Vorkommen nach einem bestimmten Punkt zurückgibt und daher, soweit ich das beurteilen kann, keine Lösung ist.
Es gibt auch eine Lösung für ähnliche Fälle wie oben, z. mit cumsum und where, aber ich würde gerne wissen, ob es einen numpy-freien Weg gibt, um das Problem zu lösen.
Ich mache mir Sorgen um die Leistung, seit ich das erste Mal während der Implementierung eines Sieve von Eratosthenes für ein Project Euler - Problem aufgetreten bin. Dies ist jedoch eine allgemeinere Frage, die ich in anderen Situationen gesehen habe.
EDIT: Ich habe viele großartige Antworten erhalten, also habe ich beschlossen, einige Leistungstests durchzuführen. Nachfolgend finden Sie timeit Ausführungszeiten in Sekunden für Listen mit len nelements, die nach dem 4000sten Wert suchen. Die Listen sind zufällig wahr/falsch. Quellcode unten verlinkt; Es ist ein bisschen unordentlich. Ich habe kurze/modifizierte Versionen der Namen der Plakate verwendet, um die Funktionen mit Ausnahme von listcomp zu beschreiben, was das einfache Listenverständnis oben darstellt.
True Test (100'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.007824 0.031117 0.002144 0.007694 0.026908 0.003563 0.003563
10000: 0.018424 0.103049 0.002233 0.018063 0.088245 0.003610 0.003769
50000: 0.078383 0.515265 0.002140 0.078074 0.442630 0.003719 0.003608
100000: 0.152804 1.054196 0.002129 0.152691 0.903827 0.003741 0.003769
200000: 0.303084 2.123534 0.002212 0.301918 1.837870 0.003522 0.003601
True Test (1000'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.038461 0.031358 0.024167 0.039277 0.026640 0.035283 0.034482
10000: 0.049063 0.103241 0.024120 0.049383 0.088688 0.035515 0.034700
50000: 0.108860 0.516037 0.023956 0.109546 0.442078 0.035269 0.035373
100000: 0.183568 1.049817 0.024228 0.184406 0.906709 0.035135 0.036027
200000: 0.333501 2.141629 0.024239 0.333908 1.826397 0.034879 0.036551
True Test (20000'th True in a list containing True/False)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.004520 0.004439 0.036853 0.004458 0.026900 0.053460 0.053734
10000: 0.014925 0.014715 0.126084 0.014864 0.088470 0.177792 0.177716
50000: 0.766154 0.515107 0.499068 0.781289 0.443654 0.707134 0.711072
100000: 0.837363 1.051426 0.501842 0.862350 0.903189 0.707552 0.706808
200000: 0.991740 2.124445 0.498408 1.008187 1.839797 0.715844 0.709063
Number Test (750'th 0 in a list containing 0-9)
nelements eyquem_occur eyquem_occurrence graddy taymon listcomp hettinger26 hettinger
3000: 0.026996 0.026887 0.015494 0.030343 0.022417 0.026557 0.026236
10000: 0.037887 0.089267 0.015839 0.040519 0.074941 0.026525 0.027057
50000: 0.097777 0.445236 0.015396 0.101242 0.371496 0.025945 0.026156
100000: 0.173794 0.905993 0.015409 0.176317 0.762155 0.026215 0.026871
200000: 0.324930 1.847375 0.015506 0.327957 1.536012 0.027390 0.026657
Die itertools-Lösung von Hettinger ist fast immer die beste. Die Lösungen von Taylor und Graddy sind in den meisten Situationen die beste Lösung, obwohl der Listenverständnisansatz für kurze Arrays besser geeignet ist, wenn Sie die n-te Instanz so wünschen, dass n hoch ist oder Listen, in denen weniger als n Vorkommen auftreten. Wenn die Wahrscheinlichkeit besteht, dass weniger als n Vorkommen auftreten, spart die anfängliche count-Prüfung Zeit. Außerdem ist Graddys effizienter bei der Suche nach Zahlen anstelle von Wahr/Falsch ... nicht klar, warum das so ist. Die Lösungen von eyquem sind im Wesentlichen gleichwertig mit etwas mehr oder weniger Mehraufwand. eyquem_occur ist ungefähr die gleiche Lösung wie die von Taymon, während eyquem_occurrence der von listcomp ähnelt.
Die Antwort von @Taymon mit list.index war großartig.
FWIW, hier ist ein funktionaler Ansatz unter Verwendung des Moduls itertools . Es funktioniert mit jeder iterierbaren Eingabe, nicht nur mit Listen:
>>> from itertools import compress, count, imap, islice
>>> from functools import partial
>>> from operator import eq
>>> def nth_item(n, item, iterable):
indicies = compress(count(), imap(partial(eq, item), iterable))
return next(islice(indicies, n, None), -1)
Das Beispiel ist Nizza, weil es zeigt, wie das funktionale Toolset von Python effektiv kombiniert werden kann. Wenn die Pipeline einmal eingerichtet ist, gibt es keine Umleitungen um Pythons Eval-Loop. Alles wird mit C-Geschwindigkeit, geringem Speicherbedarf, langsamer Auswertung, ohne Zuweisung von Variablen und mit separat testbaren Komponenten ausgeführt. IOW, es ist alles, was funktionale Programmierer davon träumen :-)
Probelauf:
>>> x = [False,True,True,False,True,False,True,False,False,False,True,False,True]
>>> nth_item(50, True, x)
-1
>>> nth_item(0, True, x)
1
>>> nth_item(1, True, x)
2
>>> nth_item(2, True, x)
4
>>> nth_item(3, True, x)
6
Ich kann nicht mit Sicherheit sagen, dass dies der schnellste Weg ist, aber ich kann mir vorstellen, dass es ziemlich gut wäre:
i = -1
for j in xrange(n):
i = x.index(True, i + 1)
Die Antwort ist i.
wenn Effizienz ein Problem ist, denke ich, ist es besser, das normale (O(N)) anstelle des Listenverständnisses zu iterieren, wobei O(L) gilt, wobei L die Länge der Liste ist
Beispiel: Betrachten Sie eine sehr große Liste, und Sie möchten das erste Vorkommen N = 1 finden. Es ist offensichtlich besser zu stoppen, sobald Sie das erste Vorkommen finden
count = 0
for index,i in enumerate(L):
if i:
count = count + 1
if count==N:
return index
Wenn Sie sich mit der Leistung beschäftigen, sollten Sie am besten prüfen, ob Sie algorithmische Optimierungen vornehmen können. Wenn Sie zum Beispiel diese Funktion mehrmals mit denselben Werten aufrufen, möchten Sie möglicherweise frühere Berechnungen zwischenspeichern (wenn Sie beispielsweise das 50. Vorkommen eines Elements gefunden haben, können Sie jedes frühere Vorkommen in O(1) time finden).
Andernfalls möchten Sie sicherstellen, dass Ihre Technik auf (faulen) Iteratoren funktioniert.
Die * in * elegante und leistungsfreudige Art und Weise, die ich mir vorstellen kann, ist:
def indexOfNthOccurrence(N, element, stream):
"""for N>0, returns index or None"""
seen = 0
for i,x in enumerate(stream):
if x==element:
seen += 1
if seen==N:
return i
(Wenn Sie wirklich auf den Leistungsunterschied zwischen Aufzählung und anderen Techniken achten, müssen Sie auf Profiling zurückgreifen, insbesondere mit den numpy-Funktionen, die auf C zurückgreifen können.)
So bereiten Sie den gesamten Stream vor und unterstützen O(1)-Abfragen:
from collections import *
cache = defaultdict(list)
for i,elem in enumerate(YOUR_LIST):
cache[elem] += [i]
# e.g. [3,2,3,2,5,5,1]
# 0 1 2 3 4 5 6
# cache: {3:[0,2], 1:[6], 2:[1,3], 5:[4,5]}
Eine Lösung, die zuerst ein Listenobjekt erstellt und das nth-1-Element dieser Liste zurückgibt: Funktion Vorkommen ()
Und eine Lösung, die auch funktionale Programmierer erfüllt, denke ich, mit Generatoren, weil ich sie liebe: Funktion Vorkommen ()
S = 'stackoverflow.com is a fantastic amazing site'
print 'object S is string %r' % S
print "indexes of 'a' in S :",[indx for indx,elem in enumerate(S) if elem=='a']
def occurence(itrbl,x,nth):
return [indx for indx,elem in enumerate(itrbl)
if elem==x ][nth-1] if x in itrbl \
else None
def occur(itrbl,x,nth):
return (i for pos,i in enumerate(indx for indx,elem in enumerate(itrbl)
if elem==x)
if pos==nth-1).next() if x in itrbl\
else None
print "\noccurence(S,'a',4th) ==",occurence(S,'a',4)
print "\noccur(S,'a',4th) ==",occur(S,'a',4)
ergebnis
object S is string 'stackoverflow.com is a fantastic amazing site'
indexes of 'a' in S : [2, 21, 24, 27, 33, 35]
occur(S,'a',4th) == 27
occurence(S,'a',4th) == 27
Die zweite Lösung scheint komplex zu sein, ist es aber nicht wirklich. Das Iterable muss nicht vollständig durchlaufen werden: Der Prozess stoppt, sobald das gewünschte Vorkommen gefunden wird.
[y for y in enumerate(x) if y[1]==True][z][0]
Anmerkung: Hier ist Z das n-te Vorkommen,
Hier finden Sie eine weitere Möglichkeit, das Vorkommen von nthvon xin einer Liste itrblzu finden:
def nthoccur(nth,x,itrbl):
count,index = 0,0
while count < nth:
if index > len(itrbl) - 1:
return None
Elif itrbl[index] == x:
count += 1
index += 1
else:
index += 1
return index - 1
Ich denke das sollte funktionieren.
def get_nth_occurrence_of_specific_term(my_list, term, n):
assert type(n) is int and n > 0
start = -1
for i in range(n):
if term not in my_list[start + 1:]:
return -1
start = my_list.index(term, start + 1)
return start
Sie könnten count verwenden:
from itertools import count
x = [False, True, True, False, True, False, True, False, False, False, True, False, True]
def nth_index(n, item, iterable):
counter = count(1)
return next((i for i, e in enumerate(iterable) if e == item and next(counter) == n), -1)
print(nth_index(3, True, x))
Ausgabe
4
Die Idee ist, dass aufgrund des Kurzschlusscharakters von e == item and next(counter) == n) der Ausdruck next(counter) == n nur ausgewertet wird, wenn e == item so zählt, dass nur die Elemente gleich item gezählt werden.
hier ist ein weg:
für das obige Beispiel:
x=[False,True,True,False,True,False,True,False,False,False,True,False,True]
wir können eine Funktion find_index definieren
def find_index(lst, value, n):
c=[]
i=0
for element in lst :
if element == value :
c .append (i)
i+=1
return c[n]
und wenn wir die Funktion anwenden:
nth_index = find_index(x, True, 4)
print nth_index
das Ergebnis ist:
10
Sie können next mit enumerate und einem Generatorausdruck verwenden. itertools.islice ermöglicht es Ihnen, eine Iterable nach Bedarf zu schneiden.
from itertools import islice
x = [False,True,True,False,True,False,True,False,False,False,True,False,True]
def get_nth_index(L, val, n):
"""return index of nth instance where value in list equals val"""
return next(islice((i for i, j in enumerate(L) if j == val), n-1, n), -1)
res = get_nth_index(x, True, 3) # 4
Wenn der Iterator erschöpft ist, d. H. Das Vorkommen des angegebenen Wertes n th nicht vorhanden ist, kann next einen Standardwert zurückgeben, in diesem Fall -1: