Der schnellste Weg zu prüfen, ob ein Wert in einer Liste existiert

Question

Was ist der schnellste Weg, um zu prüfen, ob ein Wert in einer sehr großen Liste vorhanden ist?

Answer 1

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 sinnvoll, wenn sich a nicht ändert, so dass wir den dict()-Teil einmal ausführen und ihn dann wiederholt verwenden können. Wenn sich a ändert, beschreiben Sie bitte genauer, was Sie vorhaben.

Answer 2

Wenn Sie nur das Vorhandensein eines Elements in einer Liste prüfen wollen,

7 in list_data

ist die schnellste Lösung. Beachten Sie jedoch, dass

7 in set_data

ist eine nahezu freie Operation, unabhängig von der Größe der Menge! Das Erstellen einer Menge aus einer großen Liste ist 300 bis 400 Mal langsamer als in Wenn Sie also nach vielen Elementen suchen müssen, ist es schneller, zuerst eine Menge zu erstellen.

Plot erstellt mit Perfplot :

import perfplot
import numpy as np

def setup(n):
    data = np.arange(n)
    np.random.shuffle(data)
    return data, set(data)

def list_in(data):
    return 7 in data[0]

def create_set_from_list(data):
    return set(data[0])

def set_in(data):
    return 7 in data[1]

b = perfplot.bench(
    setup=setup,
    kernels=[list_in, set_in, create_set_from_list],
    n_range=[2 ** k for k in range(24)],
    xlabel="len(data)",
    equality_check=None,
)
b.save("out.png")
b.show()

Answer 3

Beachten Sie, dass die in Operator prüft nicht nur die Gleichheit ( == ), sondern auch Identität ( is ), die in Logik für list s ist entspricht ungefähr das Folgende (es ist eigentlich 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 in einigen Fällen könnte es beispielsweise einen Python-Neuling überraschen, numpy.NAN hat die ungewöhnliche Eigenschaft, dass es sich selbst nicht gleichend :

>>> 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() mögen:

>>> 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 in Logik für list s mit any() wäre:

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

Ich möchte jedoch betonen, dass es sich hierbei um einen Sonderfall handelt und in den allermeisten Fällen die in Operator ist hochoptimiert und natürlich genau das, was Sie wollen (entweder mit einem list oder mit einer set ).

Answer 4

Es klingt, als ob Ihre Anwendung von der Verwendung einer Bloom-Filter-Datenstruktur profitieren könnte.

Kurz gesagt, ein Bloomfilter kann Ihnen sehr schnell sagen, ob ein Wert DEFINITIV NICHT in einer Menge vorhanden ist. Andernfalls können Sie eine langsamere Suche durchführen, um den Index eines Wertes zu erhalten, der möglicherweise in der Liste enthalten sein könnte. Wenn Ihre Anwendung also viel häufiger das Ergebnis "nicht gefunden" als das Ergebnis "gefunden" erhält, könnten Sie durch Hinzufügen eines Bloom-Filters eine Geschwindigkeitssteigerung feststellen.

Für Details bietet Wikipedia einen guten Überblick über die Funktionsweise von Bloom-Filtern, und eine Websuche nach "python bloom filter library" liefert zumindest einige nützliche Implementierungen.

Answer 5

Oder verwenden Sie __contains__ :

sequence.__contains__(value)

Demo:

>>> l = [1, 2, 3]
>>> l.__contains__(3)
True
>>>