Schnellste Methode, um zu überprüfen, ob ein Wert in einer Liste vorhanden ist

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

• -Lass "n" die Länge deiner Liste sein
• -Optionaler Schritt: Wenn Sie den Index des Elements benötigen: Fügen Sie der Liste eine zweite Spalte mit dem aktuellen Index der Elemente (0 bis n-1) hinzu - siehe später
• Bestellen Sie Ihre Liste oder eine Kopie davon (.sort ())
• Schleife durch:
  • Vergleichen Sie Ihre Nummer mit dem n/2-ten Element der Liste
    • Wenn größer, wiederholen Sie die Schleife zwischen den Indizes n/2-n
    • Wenn kleiner, wiederholen Sie die Schleife zwischen den Indizes 0-n/2
    • Wenn das gleiche: du hast es gefunden
• Reduzieren Sie die Liste so lange, bis Sie sie gefunden haben oder nur noch 2 Nummern (unter und über der gesuchten)
• Dies findet jedes Element in höchstens 19 Schritte für eine Liste von 1.000.0 (log (2) n um genau zu sein)

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)