Wie kann man am schnellsten feststellen, ob ein Wert in einer Liste vorhanden ist (eine Liste mit Millionen von Werten) und welchen Index hat sie?
Ich weiß, dass alle Werte in der Liste wie in diesem Beispiel eindeutig sind.
Die erste Methode, die ich versuche, ist (3,8 Sekunden in meinem realen Code):
a = [4,2,3,1,5,6]
if a.count(7) == 1:
b=a.index(7)
"Do something with variable b"
Die zweite Methode, die ich versuche, ist (2x schneller: 1,9 Sekunden für meinen realen Code):
a = [4,2,3,1,5,6]
try:
b=a.index(7)
except ValueError:
"Do nothing"
else:
"Do something with variable b"
Vorgeschlagene Methoden vom Benutzer "Stack Overflow" (2,74 Sek. Für meinen tatsächlichen Code):
a = [4,2,3,1,5,6]
if 7 in a:
a.index(7)
In meinem realen Code dauert die erste Methode 3,81 Sekunden und die zweite Methode 1,88 Sekunden. Es ist eine gute Verbesserung, aber:
Ich bin ein Anfänger mit Python/Scripting, und gibt es eine schnellere Möglichkeit, dieselben Dinge zu tun und mehr Verarbeitungszeit zu sparen?
Genauere Erklärung für meine Bewerbung:
In der Blender-API kann ich auf eine Liste von Partikeln zugreifen:
particles = [1, 2, 3, 4, etc.]
Von dort aus kann ich auf die Position eines Partikels zugreifen:
particles[x].location = [x,y,z]
Und für jedes Partikel teste ich, ob ein Nachbar existiert, indem ich jeden Partikelort wie folgt durchsuche:
if [x+1,y,z] in particles.location
"Find the identity of this neighbour particle in x:the particle's index
in the array"
particles.index([x+1,y,z])
7 in a
Der einfachste und schnellste Weg, dies zu tun.
Sie können auch die Verwendung von set
in Betracht ziehen, aber das Erstellen dieses Satzes aus Ihrer Liste kann mehr Zeit in Anspruch nehmen, als ein schnelleres Testen der Mitgliedschaft spart. Der einzige Weg, um sicher zu sein, ist ein gutes Benchmarking. (Dies hängt auch davon ab, welche Operationen Sie benötigen)
Wie von anderen angegeben, kann in
für große Listen sehr langsam sein. Hier sind einige Vergleiche der Leistungen für in
, set
und bisect
. Beachten Sie, dass die Zeit (in Sekunden) in logarithmischer Skala angegeben ist.
Code zum Testen:
import random
import bisect
import matplotlib.pyplot as plt
import math
import time
def method_in(a,b,c):
start_time = time.time()
for i,x in enumerate(a):
if x in b:
c[i] = 1
return(time.time()-start_time)
def method_set_in(a,b,c):
start_time = time.time()
s = set(b)
for i,x in enumerate(a):
if x in s:
c[i] = 1
return(time.time()-start_time)
def method_bisect(a,b,c):
start_time = time.time()
b.sort()
for i,x in enumerate(a):
index = bisect.bisect_left(b,x)
if index < len(a):
if x == b[index]:
c[i] = 1
return(time.time()-start_time)
def profile():
time_method_in = []
time_method_set_in = []
time_method_bisect = []
Nls = [x for x in range(1000,20000,1000)]
for N in Nls:
a = [x for x in range(0,N)]
random.shuffle(a)
b = [x for x in range(0,N)]
random.shuffle(b)
c = [0 for x in range(0,N)]
time_method_in.append(math.log(method_in(a,b,c)))
time_method_set_in.append(math.log(method_set_in(a,b,c)))
time_method_bisect.append(math.log(method_bisect(a,b,c)))
plt.plot(Nls,time_method_in,marker='o',color='r',linestyle='-',label='in')
plt.plot(Nls,time_method_set_in,marker='o',color='b',linestyle='-',label='set')
plt.plot(Nls,time_method_bisect,marker='o',color='g',linestyle='-',label='bisect')
plt.xlabel('list size', fontsize=18)
plt.ylabel('log(time)', fontsize=18)
plt.legend(loc = 'upper left')
plt.show()
def check_availability(element, collection: iter):
return element in collection
Verwendung
check_availability('a', [1,2,3,4,'a','b','c'])
Ich glaube, dass dies der schnellste Weg ist, um festzustellen, ob ein ausgewählter Wert in einem Array enthalten ist.
Sie können Ihre Artikel in ein set
einfügen. Set-Lookups sind sehr effizient.
Versuchen:
s = set(a)
if 7 in s:
# do stuff
edit In einem Kommentar geben Sie an, dass Sie den Index des Elements erhalten möchten. Leider haben Mengen keine Vorstellung von der Elementposition. Alternativ können Sie Ihre Liste vorsortieren und dann jedes Mal binäre Suche verwenden, wenn Sie ein Element suchen müssen.
a = [4,2,3,1,5,6]
index = dict((y,x) for x,y in enumerate(a))
try:
a_index = index[7]
except KeyError:
print "Not found"
else:
print "found"
Dies ist nur dann eine gute Idee, wenn sich a nicht ändert. Daher können wir den Teil dict () einmal ausführen und ihn dann wiederholt verwenden. Wenn sich a ändert, machen Sie bitte nähere Angaben zu Ihren Tätigkeiten.
Es hört sich so an, als würde Ihre Anwendung von der Verwendung einer Bloom Filter-Datenstruktur profitieren.
Kurz gesagt, ein Bloom-Filter-Lookup kann Ihnen sehr schnell mitteilen, ob ein Wert ENDGÜLTIG NICHT in einem Set vorhanden ist. Andernfalls können Sie eine langsamere Suche durchführen, um den Index eines Werts abzurufen, der möglicherweise in der Liste enthalten ist. Wenn Ihre Anwendung also viel häufiger das Ergebnis "Nicht gefunden" als das Ergebnis "Gefunden" erzielt, können Sie möglicherweise eine Beschleunigung feststellen, indem Sie einen Bloom-Filter hinzufügen.
Für Details bietet Wikipedia einen guten Überblick über die Funktionsweise von Bloom-Filtern, und eine Websuche nach "Python Bloom-Filter-Bibliothek" bietet mindestens einige nützliche Implementierungen.
Beachten Sie, dass der Operator in
nicht nur die Gleichheit (==
) testet, sondern auch die Identität (is
), die in
-Logik für list
s ist ungefähr äquivalent zu dem Folgenden (es ist tatsächlich in C geschrieben und nicht in Python, zumindest nicht in CPython):
for element in s: if element is target: # fast check for identity implies equality return True if element == target: # slower check for actual equality return True return False
In den meisten Fällen ist dieses Detail irrelevant, aber in einigen Fällen kann es einen Python Anfänger überraschen, zum Beispiel hat numpy.NAN
die ungewöhnliche Eigenschaft, nicht zu sein sich selbst gleich sein :
>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True
Um zwischen diesen ungewöhnlichen Fällen zu unterscheiden, können Sie any()
wie folgt verwenden:
>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True
Beachten Sie, dass die in
-Logik für list
s mit any()
wie folgt lautet:
any(element is target or element == target for element in lst)
Ich möchte jedoch betonen, dass dies ein Edge-Fall ist, und in den meisten Fällen ist der Operator in
hochoptimiert und genau das, was Sie natürlich möchten (entweder mit einem list
oder mit einem set
).
Oder benutze __contains__
:
sequence.__contains__(value)
Demo:
>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>>
Dies ist nicht der Code, sondern der Algorithmus für eine sehr schnelle Suche.
Wenn Ihre Liste und der Wert, nach dem Sie suchen, Zahlen sind, ist dies ziemlich einfach. Wenn Zeichenfolgen: siehe unten:
Wenn Sie auch die ursprüngliche Position Ihrer Nummer benötigen, suchen Sie sie in der zweiten Indexspalte.
Wenn Ihre Liste nicht aus Zahlen besteht, funktioniert die Methode weiterhin und ist am schnellsten. Möglicherweise müssen Sie jedoch eine Funktion definieren, mit der Zeichenfolgen verglichen/sortiert werden können.
Dies erfordert natürlich die Investition in die sorted () -Methode, aber wenn Sie dieselbe Liste weiterhin zur Überprüfung verwenden, kann es sich lohnen.
present = False
searchItem = 'd'
myList = ['a', 'b', 'c', 'd', 'e']
if searchItem in myList:
present = True
print('present = ', present)
else:
print('present = ', present)
Die Lösung von @Winston Ewert führt zu einer großen Beschleunigung für sehr große Listen, aber diese Stackoverflow-Antwort gibt an, dass das try:/except:/else: -Konstrukt verlangsamt wird, wenn die except-Verzweigung häufig erreicht wird . Eine Alternative besteht darin, die .get()
-Methode für das Diktat zu nutzen:
a = [4,2,3,1,5,6]
index = dict((y, x) for x, y in enumerate(a))
b = index.get(7, None)
if b is not None:
"Do something with variable b"
Die .get(key, default)
-Methode ist nur für den Fall geeignet, dass Sie nicht garantieren können, dass ein Schlüssel im Diktat enthalten ist. Wenn der Schlüssel vorhanden ist , gibt er den Wert zurück (wie bei dict[key]
), aber wenn dies nicht der Fall ist, gibt .get()
Ihren Wert zurück Standardwert (hier None
). Sie müssen in diesem Fall sicherstellen, dass der ausgewählte Standardwert nicht in a
enthalten ist.
Für mich waren es 0,030 Sekunden (real), 0,026 Sekunden (Benutzer) und 0,004 Sekunden (sys).
try:
print("Started")
x = ["a", "b", "c", "d", "e", "f"]
i = 0
while i < len(x):
i += 1
if x[i] == "e":
print("Found")
except IndexError:
pass
Code, um zu überprüfen, ob zwei Elemente in einem Array vorhanden sind, dessen Produkt gleich k ist:
n = len(arr1)
for i in arr1:
if k%i==0:
print(i)