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

7 in a

Der klarste und schnellste Weg, dies zu tun.

Sie können auch die Verwendung eines set aber die Erstellung dieser Menge aus Ihrer Liste kann mehr Zeit in Anspruch nehmen, als durch schnellere Mitgliedschaftstests eingespart werden kann. Die einzige Möglichkeit, sicher zu sein, ist ein gutes Benchmarking. (dies hängt auch davon ab, welche Operationen Sie benötigen)

Answer 2

Wie bereits von anderen erwähnt, in kann bei großen Listen sehr langsam sein. Hier sind einige Vergleiche der Leistungen für in , set et bisect . Beachten Sie, dass die Zeit (in Sekunden) in logarithmischem Maßstab 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 = []

    # adjust range down if runtime is too long or up if there are too many zero entries in any of the time_method lists
    Nls = [x for x in range(10000, 30000, 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(method_in(a, b, c))
        time_method_set_in.append(method_set_in(a, b, c))
        time_method_bisect.append(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.yscale('log')
    plt.show()

profile()

Answer 3

Sie könnten Ihre Gegenstände in eine set . Set-Lookups sind sehr effizient.

Versuchen Sie es:

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

editar In einem Kommentar sagen Sie, dass Sie den Index des Elements abfragen möchten. Leider haben Sets keine Vorstellung von der Position eines Elements. Eine Alternative ist die Vorsortierung der Liste und die anschließende Verwendung von binäre Suche jedes Mal, wenn Sie ein Element finden müssen.

Answer 4

Die ursprüngliche Frage lautete:

Wie kann man am schnellsten feststellen, ob ein Wert in einer Liste vorhanden ist (eine Liste mit Millionen von Werten) und wie hoch sein Index ist?

Es gibt also zwei Dinge zu finden:

1. ein Eintrag in der Liste ist, und
2. wie lautet der Index (falls in der Liste).

Zu diesem Zweck habe ich den Code von @xslittlegrass so geändert, dass in allen Fällen Indizes berechnet werden, und eine zusätzliche Methode hinzugefügt.

Ergebnisse

Methoden sind:

1. in--grundsätzlich if x in b: return b.index(x)
2. try--try/catch on b.index(x) (überspringt die Prüfung, ob x in b ist)
3. set--grundsätzlich if x in set(b): return b.index(x)
4. bisect--sortiert b mit seinem Index, binäre Suche nach x in sorted(b). Hinweis mod von @xslittlegrass, der den Index im sortierten b zurückgibt, und nicht das ursprüngliche b)
5. reverse--bilden Sie ein Reverse-Lookup-Dictionary d für b; dann d[x] liefert den Index von x.

Die Ergebnisse zeigen, dass Methode 5 die schnellste ist.

Interessanterweise ist die Versuchen Sie und die einstellen. Methoden zeitlich gleichwertig sind.

---

Test Code

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

Answer 5

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.