Der schnellste Weg, um zu überprüfen, ob ein Wert in einer Liste vorhanden ist

816

Was ist der schnellste Weg, um festzustellen, ob ein Wert in einer Liste vorhanden ist (eine Liste mit Millionen von Werten) und wie der Index lautet?

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 echten 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 Stack Overflow-Benutzer (2,74 Sek. Für meinen echten 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, die gleichen Dinge zu tun und mehr Verarbeitungszeit zu sparen?

Spezifischere Erklärung für meine Anwendung:

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

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])
Jean-Francois Gallant
quelle
5
In Python wird das Ding in eckigen Klammern als Liste bezeichnet, nicht als Array. Verwenden Sie anstelle einer Liste einen Satz. Oder halten Sie Ihre Liste sortiert und verwenden Sie das bisectModul
Steven Rumbalski
Sie müssen also wirklich mit Indizes jonglieren? Oder spielt die Bestellung eigentlich keine Rolle und Sie möchten nur Schiffstests, Kreuzungen usw. für Mitglieder durchführen? Mit anderen Worten, es hängt davon ab, was Sie wirklich versuchen. Sets mögen für Sie funktionieren, und dann sind sie eine wirklich gute Antwort, aber wir können es nicht an dem Code erkennen, den Sie gezeigt haben.
2
Wahrscheinlich müssen Sie in Ihrer Frage angeben, dass Sie nicht den Wert, sondern dessen Index benötigen.
Roman Bodnarchuk
Ich bearbeite meine Frage und versuche klarer zu erklären, was ich tun möchte ... Ich hoffe es ...
Jean-Francois Gallant
1
@StevenRumbalski: Da set keinen Duplizierungsinhalt enthalten kann, während Jean die Position von Partikeln speichern möchte (x, y, z könnten gleich sein), können wir set in diesem Fall nicht verwenden
Hieu Vo

Antworten:

1569
7 in a

Der klarste und schnellste Weg, dies zu tun.

Sie können auch die Verwendung von a in Betracht ziehen set, aber das Erstellen dieses Satzes aus Ihrer Liste kann mehr Zeit in Anspruch nehmen, als ein schnellerer Mitgliedschaftstest spart. Der einzige Weg, um sicher zu sein, ist ein gutes Benchmarking. (Dies hängt auch davon ab, welche Vorgänge Sie benötigen.)

Rafe Kettler
quelle
5
Aber Sie haben den Index nicht und das Erhalten kostet Sie, was Sie gespeichert haben.
Rodrigo
6
wie: Wenn 7 in a: b = a.index (7)?
Jean-Francois Gallant
26
@StevenRumbalski: Sets sind nur dann eine Option, wenn Sie sie nicht bestellen müssen (und daher einen Index haben). Und Sätze sind klar in der Antwort erwähnt, es ist einfach auch eine einfache Antwort auf die Frage gibt , wie OP sie gefragt. Ich denke nicht, dass dies -1 wert ist.
Ich bearbeite meine Frage und versuche klarer zu erklären, was ich tun möchte ... Ich hoffe es ...
Jean-Francois Gallant
1
Okay, ich probiere Ihre Methode in meinem realen Code aus und es dauert wahrscheinlich etwas länger, weil ich den Index des Werts kennen muss. Bei meiner zweiten Methode überprüfe ich, ob sie vorhanden ist, und erhalte gleichzeitig den Index.
Jean-Francois Gallant
213

Wie von anderen angegeben, inkann es bei großen Listen sehr langsam sein. Hier einige Vergleiche der Leistungen für in, setund bisect. Beachten Sie, dass die Zeit (in Sekunden) in der Protokollskala angegeben ist.

Geben Sie hier die Bildbeschreibung ein

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()
xslittlegrass
quelle
15
Lieben Sie das Ausschneiden und Einfügen von ausführbarem Code wie diesen in Antworten. Um anderen ein paar Sekunden Zeit zu sparen, benötigen Sie 3 Importe: import random / import bisect / import matplotlib.pyplot as pltund rufen Sie dann an:profile()
kghastie
1
Welche Version von Python ist das?
Cowbert
immer toll , den Code , sondern nur Köpfe aufstehen ich Import Zeit hatte zu laufen
whla
Und vergiss das bescheidene range()Objekt nicht. Überprüfen Sie bei der Verwendung var in [integer list], ob ein range()Objekt dieselbe Sequenz modellieren kann. Sehr nahe an der Leistung eines Sets, aber prägnanter.
Martijn Pieters
37

Sie könnten Ihre Artikel in eine set. Set-Lookups sind sehr effizient.

Versuchen:

s = set(a)
if 7 in s:
  # do stuff

Bearbeiten In einem Kommentar sagen Sie, dass Sie den Index des Elements erhalten möchten. Leider haben Mengen keine Vorstellung von der Elementposition. Eine Alternative besteht darin, Ihre Liste vorab zu sortieren und dann jedes Mal die binäre Suche zu verwenden, wenn Sie ein Element suchen müssen.

NPE
quelle
Und wenn ich danach den Index dieses Wertes wissen möchte, ist es möglich und Sie haben einen schnellen Weg, dies zu tun?
Jean-Francois Gallant
@ Jean-FrancoisGallant: In diesem Fall sind Sets nicht sehr nützlich. Sie können die Liste vorsortieren und dann die binäre Suche verwenden. Bitte beachten Sie meine aktualisierte Antwort.
NPE
Ich bearbeite meine Frage und versuche klarer zu erklären, was ich tun möchte ... Ich hoffe es ...
Jean-Francois Gallant
30
def check_availability(element, collection: iter):
    return element in collection

Verwendungszweck

check_availability('a', [1,2,3,4,'a','b','c'])

Ich glaube, dies ist der schnellste Weg, um festzustellen, ob sich ein ausgewählter Wert in einem Array befindet.

Tiago Moutinho
quelle
71
return 'a' in a?
Shikiryu
4
Sie müssen den Code in eine Definition einfügen: def listValue (): a = [1,2,3,4, 'a', 'b', 'c'] return 'a' in ax = listValue () print ( x)
Tenzin
12
Es ist eine gültige Python-Antwort, es ist einfach kein guter, lesbarer Code.
Rick Henderson
1
In acht nehmen ! Dies passt, obwohl dies sehr wahrscheinlich das ist, was Sie nicht erwartet haben:o='--skip'; o in ("--skip-ias"); # returns True !
Alex F
3
@Alex F Der inOperator testet auf die gleiche Weise die Teilstring-Mitgliedschaft. Der verwirrende Teil hier ist wahrscheinlich, dass ("hello")es sich nicht um ein einwertiges Tupel handelt, während ("hello",)- das Komma den Unterschied macht. o in ("--skip-ias",)ist Falsewie erwartet.
MoxieBall
16
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 dict () - Teil einmal ausführen und ihn dann wiederholt verwenden. Wenn sich a ändert, geben Sie bitte detaillierter an, was Sie tun.

Winston Ewert
quelle
Es funktioniert, aber nicht, wenn es in meinem Code implementiert ist: "TypeError: nicht zerlegbarer Typ: 'list'
Jean-Francois Gallant
1
@ Jean-FrancoisGallant, das liegt wahrscheinlich daran, dass Sie Listen verwenden, in denen Sie wirklich Tupel verwenden sollten. Wenn Sie umfassende Ratschläge zur Beschleunigung Ihres Codes wünschen, sollten Sie diese unter codereview.stackexchange.com veröffentlichen. Dort erhalten Sie Stil- und Leistungsratschläge.
Winston Ewert
Dies ist eine sehr clevere Lösung für das Problem. Anstelle des Versuchs außer Konstrukt würde ich Folgendes tun: a_index = index.get (7), das standardmäßig None ist, wenn der Schlüssel nicht gefunden wird.
Murphsp1
14

Die ursprüngliche Frage war:

Was ist der schnellste Weg, um festzustellen, ob ein Wert in einer Liste vorhanden ist (eine Liste mit Millionen von Werten) und wie der Index lautet?

Es gibt also zwei Dinge zu finden:

  1. ist ein Element in der Liste, und
  2. Was ist der Index (wenn in der Liste).

Zu diesem Zweck habe ich den @ xslittlegrass-Code geändert, um in allen Fällen Indizes zu berechnen, und eine zusätzliche Methode hinzugefügt.

Ergebnisse

Geben Sie hier die Bildbeschreibung ein

Methoden sind:

  1. in - im Grunde genommen, wenn x in b: return b.index (x)
  2. try - try / catch auf b.index (x) (überspringt die Überprüfung, ob x in b ist)
  3. set - im Grunde genommen, wenn x in set (b): b.index (x) zurückgeben
  4. halbieren - sortiere b mit seinem Index, binäre Suche nach x in sortiert (b). Beachten Sie den Mod von @xslittlegrass, der den Index im sortierten b und nicht im Original zurückgibt. B)
  5. reverse - bilde ein Reverse-Lookup-Wörterbuch d für b; dann liefert d [x] den Index von x.

Die Ergebnisse zeigen, dass Methode 5 die schnellste ist.

Interessanterweise sind die try- und die set- Methode zeitlich gleichwertig.


Testcode

import random
import bisect
import matplotlib.pyplot as plt
import math
import timeit
import itertools

def wrapper(func, *args, **kwargs):
    " Use to produced 0 argument function for call it"
    # Reference https://www.pythoncentral.io/time-a-python-function/
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

def method_in(a,b,c):
    for i,x in enumerate(a):
        if x in b:
            c[i] = b.index(x)
        else:
            c[i] = -1
    return c

def method_try(a,b,c):
    for i, x in enumerate(a):
        try:
            c[i] = b.index(x)
        except ValueError:
            c[i] = -1

def method_set_in(a,b,c):
    s = set(b)
    for i,x in enumerate(a):
        if x in s:
            c[i] = b.index(x)
        else:
            c[i] = -1
    return c

def method_bisect(a,b,c):
    " Finds indexes using bisection "

    # Create a sorted b with its index
    bsorted = sorted([(x, i) for i, x in enumerate(b)], key = lambda t: t[0])

    for i,x in enumerate(a):
        index = bisect.bisect_left(bsorted,(x, ))
        c[i] = -1
        if index < len(a):
            if x == bsorted[index][0]:
                c[i] = bsorted[index][1]  # index in the b array

    return c

def method_reverse_lookup(a, b, c):
    reverse_lookup = {x:i for i, x in enumerate(b)}
    for i, x in enumerate(a):
        c[i] = reverse_lookup.get(x, -1)
    return c

def profile():
    Nls = [x for x in range(1000,20000,1000)]
    number_iterations = 10
    methods = [method_in, method_try, method_set_in, method_bisect, method_reverse_lookup]
    time_methods = [[] for _ in range(len(methods))]

    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)]

        for i, func in enumerate(methods):
            wrapped = wrapper(func, a, b, c)
            time_methods[i].append(math.log(timeit.timeit(wrapped, number=number_iterations)))

    markers = itertools.cycle(('o', '+', '.', '>', '2'))
    colors = itertools.cycle(('r', 'b', 'g', 'y', 'c'))
    labels = itertools.cycle(('in', 'try', 'set', 'bisect', 'reverse'))

    for i in range(len(time_methods)):
        plt.plot(Nls,time_methods[i],marker = next(markers),color=next(colors),linestyle='-',label=next(labels))

    plt.xlabel('list size', fontsize=18)
    plt.ylabel('log(time)', fontsize=18)
    plt.legend(loc = 'upper left')
    plt.show()

profile()
DarrylG
quelle
Tippfehler in Ihrer Beschreibung ("Reverse Loop Up" sollte "Reverse Lookup" sein, nein?)
Cam U
@ CamU - ja, korrigiert. Danke fürs bemerken.
DarrylG
7

Es hört sich so an, als würde Ihre Anwendung von der Verwendung einer Bloom Filter-Datenstruktur profitieren.

Kurz gesagt, eine Bloom-Filter-Suche kann Ihnen sehr schnell sagen, ob ein Wert in einem Satz definitiv NICHT vorhanden ist. Andernfalls können Sie langsamer nachschlagen, um den Index eines Werts zu erhalten, der möglicherweise in der Liste enthalten ist. Wenn Ihre Anwendung also dazu neigt, das Ergebnis "nicht gefunden" viel häufiger als das Ergebnis "gefunden" zu erhalten, wird möglicherweise eine Beschleunigung durch Hinzufügen eines Bloom-Filters angezeigt.

Für Details bietet Wikipedia einen guten Überblick über die Funktionsweise von Bloom-Filtern, und eine Websuche nach "Python Bloom Filter Library" bietet mindestens einige nützliche Implementierungen.

matt2000
quelle
7

Beachten Sie, dass der inOperator nicht nur Gleichheit ( ==), sondern auch Identität ( is) testet. Die inLogik für lists entspricht in etwa der folgenden (sie ist tatsächlich in C und nicht in Python geschrieben, zumindest 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 unter bestimmten Umständen kann es einen Python-Neuling überraschen, der beispielsweise numpy.NANdie ungewöhnliche Eigenschaft hat, nicht gleich sich selbst zu 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 Folgendes verwenden any():

>>> 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 die inLogik für lists mit any()wäre:

any(element is target or element == target for element in lst)

Ich möchte jedoch betonen, dass dies ein Randfall ist und in den allermeisten Fällen der inOperator hochoptimiert ist und natürlich genau das, was Sie wollen (entweder mit a listoder mit a set).

Chris_Rands
quelle
NAN == NAN, das false zurückgibt, hat nichts Ungewöhnliches. Dies ist das im IEEE 754-Standard definierte Verhalten.
TommyD
2

Oder verwenden Sie __contains__:

sequence.__contains__(value)

Demo:

>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>> 
U10-Vorwärts
quelle
2

Die Lösung von @Winston Ewert führt zu einer großen Beschleunigung für sehr große Listen. Diese Stackoverflow-Antwort zeigt jedoch an, dass das Konstrukt try: / Except : / else: verlangsamt wird, wenn der Zweig Except 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 gedacht, dass Sie nicht garantieren können, dass ein Schlüssel im Diktat enthalten ist. Wenn Schlüssel ist vorhanden, gibt sie den Wert (wie es dict[key]), aber wenn es nicht der Fall, .get()kehrt Ihr Standardwert (hier None). In diesem Fall müssen Sie sicherstellen, dass der ausgewählte Standard nicht aktiviert ist a.

user3897315
quelle
1

Dies ist nicht der Code, sondern der Algorithmus für eine sehr schnelle Suche.

Wenn Ihre Liste und der gesuchte Wert alle Zahlen sind, ist dies ziemlich einfach. Wenn Zeichenfolgen: Schauen Sie unten:

  • - Lassen Sie "n" die Länge Ihrer 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 erneut zwischen den Indizes n / 2-n
      • Wenn kleiner, wiederholen Sie die Schleife zwischen den Indizes 0-n / 2
      • Wenn das gleiche: Sie haben es gefunden
  • Grenzen Sie die Liste so lange ein, bis Sie sie gefunden haben oder nur noch 2 Zahlen haben (unter und über der gesuchten)
  • Dies findet jedes Element in höchstens 19 Schritten für eine Liste von 1.000.000 (log (2) n um genau zu sein)

Wenn Sie auch die ursprüngliche Position Ihrer Nummer benötigen, suchen Sie diese 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 der sorted () -Methode, aber wenn Sie dieselbe Liste weiterhin zur Überprüfung verwenden, kann es sich lohnen.

Adam
quelle
26
Sie haben vergessen zu erwähnen, dass der von Ihnen erläuterte Algorithmus eine einfache binäre Suche ist.
Diugalde
0

Da die Frage nicht immer als der schnellste technische Weg verstanden werden soll, schlage ich immer den einfachsten und schnellsten Weg zum Verstehen / Schreiben vor: ein Listenverständnis, einzeilig

[i for i in list_from_which_to_search if i in list_to_search_in]

Ich hatte eine list_to_search_inmit allen Elementen und wollte die Indizes der Elemente in der zurückgeben list_from_which_to_search.

Dies gibt die Indizes in einer schönen Liste zurück.

Es gibt andere Möglichkeiten, um dieses Problem zu überprüfen. Das Listenverständnis ist jedoch schnell genug, um ein Problem zu lösen.

Vaidøtas Ivøška
quelle
-2

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
Tabin1000
quelle
-2

Code zum Überprüfen, ob zwei Elemente in einem Array vorhanden sind, deren Produkt gleich k ist:

n = len(arr1)
for i in arr1:
    if k%i==0:
        print(i)
Ravi Tanwar
quelle