Najszybszy sposób sprawdzenia, czy wartość istnieje na liście

Jak stwierdzili inni, in może być bardzo wolny dla dużych list. Oto kilka porównań występów dla in, set i bisect. Uwaga czas (w sekundach) jest w skali dziennika.

Kod do testów:

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 to great or up if there are to 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()

Możesz umieścić swoje przedmioty w set. Ustawienia są bardzo wydajne.

Spróbuj:

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

Edit w komentarzu mówisz, że chcesz uzyskać indeks elementu. Niestety, zestawy nie mają pojęcia o pozycji elementu. Alternatywą jest wstępne posortowanie listy, a następnie użycie wyszukiwania binarnego za każdym razem, gdy musisz znaleźć element.

def check_availability(element, collection: iter):
    return element in collection

Użycie

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

Uważam, że jest to najszybszy sposób, aby dowiedzieć się, czy wybrana wartość znajduje się w tablicy.

Pierwotne pytanie brzmiało:

Jaki jest najszybszy sposób, aby dowiedzieć się, czy wartość istnieje na liście (Lista z milionami wartości) i jaki jest jego indeks?

Tak więc są dwie rzeczy do znalezienia:

1. jest pozycją na liście i
2. jaki jest indeks (jeśli jest na liście).

W tym celu zmodyfikowałem kod @xslittlegrass, aby obliczać indeksy we wszystkich przypadkach, i dodałem dodatkowe metoda.

Wyniki

Metody to:

1. in -- basically if x in b: return b. index (x)
2. try--try / catch na B. index (x) (pomija konieczność sprawdzenia czy x w b)
3. set -- zasadniczo jeśli x W set (b): return b. index (x)
4. bisect--sortowanie b z jego indeksem, binarne wyszukiwanie x w sortowaniu (b). Uwaga mod od @xslittlegrass który zwraca indeks w posortowanym b, zamiast oryginalnego b)
5. reverse--form a reverse lookup dictionary D for b; then d [x] dostarcza indeks x.

Wyniki pokazują, że metoda 5 jest najszybsza.

Co ciekawe, metody try i metody set są równoważne w czasie.

Kod Badania

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

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"

Będzie to dobry pomysł tylko wtedy, gdy a się nie zmieni i dlatego możemy wykonać część dict() raz, a następnie użyć jej wielokrotnie. Jeśli a się zmieni, proszę podać więcej szczegółów na temat tego, co robisz.

Wygląda na to, że Twoja aplikacja może zyskać przewagę dzięki wykorzystaniu struktury danych filtru Bloom.

W skrócie, filtr bloom look-up może powiedzieć bardzo szybko, jeśli wartość jest zdecydowanie nie obecny w zestawie. W przeciwnym razie możesz wykonać wolniejsze wyszukiwanie, aby uzyskać indeks wartości, która może znajdować się na liście. Więc jeśli aplikacja ma tendencję do uzyskania" Nie znaleziono "wynik znacznie częściej niż" znaleziono " wynik, można zobaczyć przyspieszenie przez dodanie filtra Bloom.

Dla szczegóły, Wikipedia zapewnia dobry przegląd tego, jak działają filtry Bloom, A wyszukiwanie w Internecie "python bloom filter library" zapewni co najmniej kilka przydatnych implementacji.

Należy pamiętać, że operatorin testuje nie tylko równość (==), ale także tożsamość (is), logika in dla list s jest w przybliżeniu równoważna następującym (w rzeczywistości jest napisany w C, a nie Pythonie, przynajmniej w 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

W większości okoliczności ten szczegół jest nieistotny, ale w niektórych okolicznościach może pozostawić początkującego Pythona zaskoczonego, na przykład numpy.NAN ma niezwykłą właściwość bycia nie równym :

>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True

Aby odróżnić te nietypowe przypadki można użyć any() Jak:

>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True 

Zwróć uwagę, że in Logika dla list S z any() będzie:

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

Należy jednak podkreślić, że jest to przypadek edge, a w zdecydowanej większości przypadków operator in jest wysoce zoptymalizowany i dokładnie to, co chcesz oczywiście(albo z list lub z set).

Lub __contains__:

sequence.__contains__(value)

Demo:

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

To nie jest kod, ale algorytm bardzo szybkiego wyszukiwania.

Jeśli Twoja lista i wartość, której szukasz, są liczbami, jest to dość proste. If strings: look at the bottom:

• -niech" n " będzie długością Twojej listy
• -opcjonalny krok: jeśli potrzebujesz indeksu elementu: Dodaj drugą kolumnę do listy z bieżącym indeksem elementów (0 do N-1) - patrz później
• zamów swoją listę lub jej kopię (.sort ())
• pętla przez:
  • porównaj swoją liczbę z N / 2 elementem listy
    • jeśli jest większy, pętla ponownie między indeksami n/2-N
    • jeśli jest mniejszy, pętla ponownie między indeksami 0-N / 2
    • If the same: you found it
• zawężaj listę, aż ją znajdziesz lub masz tylko 2 liczby (poniżej i powyżej tej, której szukasz)
• to znajdzie dowolny element w co najwyżej 19 kroków dla listy 1.000.000 (log(2)N być precyzyjne)

Jeśli potrzebujesz również oryginalnej pozycji numeru, poszukaj go w drugiej kolumnie indeksu.

Jeśli Twoja lista nie składa się z liczb, metoda nadal działa i będzie najszybsza, ale może być konieczne zdefiniowanie funkcji, która może porównywać/porządkować ciągi.

Oczywiście wymaga to Inwestycji w metodę sorted (), ale jeśli nadal używasz tej samej listy do sprawdzania, może być warto.

Ponieważ pytanie nie zawsze powinno być rozumiane jako najszybszy sposób techniczny - zawsze sugeruję najprostszy najszybszy sposób rozumienia/pisania: rozumienie listy, jednolinijkowe

[i for i in list_from_which_to_search if i in list_to_search_in]

Miałem list_to_search_in ze wszystkimi przedmiotami i chciałem zwrócić indeksy przedmiotów w list_from_which_to_search.

To zwraca indeksy w ładnej liście.

Istnieją inne sposoby na sprawdzenie tego problemu - jednak składanie list jest wystarczająco szybkie, dodając do fakt napisania go wystarczająco szybko, aby rozwiązać problem.

Kod sprawdzający, czy w tablicy istnieją dwa elementy, których iloczyn jest równy k:

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