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

Jaki jest najszybszy sposób sprawdzenia, czy wartość istnieje na liście (lista zawierająca miliony wartości) i jaki jest jej indeks?

Wiem, że wszystkie wartości na liście są unikalne, jak w tym przykładzie.

Pierwszą metodą, którą wypróbowałem, jest (3,8 s w moim prawdziwym kodzie):

a = [4,2,3,1,5,6]

if a.count(7) == 1:
    b=a.index(7)
    "Do something with variable b"

Drugą metodą, którą próbuję, jest (2x szybszy: 1,9 s dla mojego prawdziwego kodu):

a = [4,2,3,1,5,6]

try:
    b=a.index(7)
except ValueError:
    "Do nothing"
else:
    "Do something with variable b"

Proponowane metody od użytkownika Przepełnienie stosu (2,74 s dla mojego prawdziwego kodu):

a = [4,2,3,1,5,6]
if 7 in a:
    a.index(7)

W moim prawdziwym kodzie pierwsza metoda zajmuje 3,81 sekundy, a druga metoda 1,88 sekundy. To dobra poprawa, ale:

Jestem początkującym w Pythonie / skryptach i czy istnieje szybszy sposób na robienie tych samych rzeczy i oszczędność czasu?

Bardziej szczegółowe wyjaśnienie mojej aplikacji:

W interfejsie API Blendera mogę uzyskać dostęp do listy cząstek:

particles = [1, 2, 3, 4, etc.]

Stamtąd mogę uzyskać dostęp do lokalizacji cząsteczki:

particles[x].location = [x,y,z]

I dla każdej cząstki sprawdzam, czy sąsiad istnieje, przeszukując każdą lokalizację cząstek w ten sposób:

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

7 in a

Najczystszy i najszybszy sposób na zrobienie tego.

Możesz również rozważyć użycie setzestawu, ale utworzenie tego zestawu z listy może zająć więcej czasu niż zaoszczędzi szybsze testowanie członkostwa. Jedynym sposobem, aby być pewnym, jest dokładne porównanie. (zależy to również od wymaganych operacji)

Jak twierdzą inni, inmoże być bardzo powolny w przypadku dużych list. Oto kilka porównań występów dla in, seti bisect. Zauważ, że czas (w sekundach) jest w skali logarytmicznej.

Kod do testowania:

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

Możesz umieścić swoje przedmioty w set. Wyszukiwanie zestawów jest bardzo wydajne.

Próbować:

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

edytuj W komentarzu mówisz, że chcesz uzyskać indeks elementu. Niestety zestawy nie mają pojęcia pozycji elementu. Alternatywą jest wstępne sortowanie listy, a następnie wyszukiwanie binarne za każdym razem, gdy trzeba znaleźć element.

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

Stosowanie

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

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

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 nie zmieni się, dlatego możemy raz wykonać część dict (), a następnie użyć jej wielokrotnie. Jeśli coś się zmieni, podaj więcej szczegółów na temat tego, co robisz.

Pierwotne pytanie brzmiało:

Jaki jest najszybszy sposób sprawdzenia, czy wartość istnieje na liście (lista zawierająca miliony wartości) i jaki jest jej indeks?

Zatem są dwie rzeczy do znalezienia:

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

W tym celu zmodyfikowałem kod @xslittlegrass, aby obliczać indeksy we wszystkich przypadkach, i dodałem dodatkową metodę.

Wyniki

Metody to:

1. in - w zasadzie jeśli x in b: return b.index (x)
2. try - spróbuj / złap na b.index (x) (pomija sprawdzanie, czy x in b)
3. set - w zasadzie jeśli x w zestawie (b): return b.index (x)
4. bisect - sortuj b z jego indeksem, binarne wyszukiwanie x w posortowanym (b). Uwaga mod z @xslittlegrass, który zwraca indeks w posortowanym b, a nie w oryginalnym b)
5. rewers - tworzy słownik wyszukiwania wstecznego d dla b; następnie d [x] zapewnia indeks x.

Wyniki pokazują, że metoda 5 jest najszybsza.

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

Kod testowy

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

Wygląda na to, że Twoja aplikacja może zyskać na zastosowaniu struktury danych Bloom Filter.

Krótko mówiąc, wyszukiwanie filtra Blooma może bardzo szybko stwierdzić, czy wartość NIE JEST ZDECYDOWO obecna w zestawie. W przeciwnym razie możesz wykonać wolniejsze wyszukiwanie, aby uzyskać indeks wartości, KTÓRE MOŻLIWE MOGĄ BYĆ na liście. Jeśli więc twoja aplikacja ma tendencję do uzyskiwania wyniku „nie znaleziono” znacznie częściej niż wynik „znaleziono”, możesz przyspieszyć dodając Filtr Blooma.

Aby uzyskać szczegółowe informacje, Wikipedia zapewnia dobry przegląd działania filtrów Blooma, a wyszukiwanie w Internecie dla „biblioteki filtrów filtrów python” zapewni co najmniej kilka przydatnych implementacji.

Należy pamiętać, że inoperator testuje nie tylko równość ( ==), ale także tożsamość ( is), inlogika dla lists jest mniej więcej równoważna z następującą (jest napisana w C, a nie w 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 przypadków ten szczegół jest nieistotny, ale w niektórych okolicznościach może zaskoczyć nowicjusza w Pythonie, na przykład numpy.NANma niezwykłą właściwość polegającą na tym, że nie jest sobie równy :

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

Aby rozróżnić te niezwykłe przypadki, możesz użyć 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 

Zauważ, że inlogika dla lists z any()będzie następująca:

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

Powinienem jednak podkreślić, że jest to przypadek skrajny i dla zdecydowanej większości przypadków inoperator jest wysoce zoptymalizowany i dokładnie tego, czego chcesz oczywiście (albo z a listalbo z set).

Lub użyj __contains__:

sequence.__contains__(value)

Próbny:

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

Rozwiązanie @Winston Ewert zapewnia duże przyspieszenie dla bardzo dużych list, ale ta odpowiedź na przepełnienie stosu wskazuje, że próba: / wyjątek: / else: konstrukcja zostanie spowolniona, jeśli gałąź wyjątków jest często osiągana. Alternatywą jest skorzystanie z .get()metody dyktowania:

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"

Ta .get(key, default)metoda jest tylko w przypadku, gdy nie możesz zagwarantować, że klucz będzie w nagraniu. Jeśli klucz jest obecny, zwraca wartość (jak by to zrobił dict[key]), ale gdy nie jest, .get()zwraca wartość domyślną (tutaj None). W takim przypadku musisz upewnić się, że wybrane ustawienie domyślne nie będzie dostępne a.

To nie jest kod, ale algorytm bardzo szybkiego wyszukiwania.

Jeśli twoja lista i szukana wartość są liczbami, jest to dość proste. Jeśli ciągi znaków: spójrz na dół:

• - 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 (od 0 do n-1) - patrz później
• Zamów swoją listę lub jej kopię (.sort ())
• Pętla przez:
  • Porównaj swój numer z n / 2 elementem listy
    • Jeśli większy, ponownie zapętlić między indeksami n / 2-n
    • Jeśli jest mniejszy, ponownie zapętlić między indeksami 0-n / 2
    • Jeśli to samo: znalazłeś
• Przewężaj listę, dopóki jej nie znajdziesz lub nie masz tylko 2 liczb (poniżej i powyżej tej, której szukasz)
• Znajdzie to dowolny element w co najwyżej 19 krokach dla listy 1.000.000 (log (2) n to dokładnie)

Jeśli potrzebujesz także oryginalnej pozycji swojego numeru, poszukaj jej w drugiej kolumnie indeksu.

Jeśli lista nie zawiera 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 znaków.

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

Ponieważ pytanie nie zawsze powinno być rozumiane jako najszybszy sposób techniczny - zawsze sugeruję najprostszy najszybszy sposób na zrozumienie / napisanie: zrozumienie listy, jedno-liniowy

[i for i in list_from_which_to_search if i in list_to_search_in]

Miałem list_to_search_inwszystkie elementy i chciałem zwrócić indeksy elementów w list_from_which_to_search.

To zwraca indeksy na ładnej liście.

Istnieją inne sposoby sprawdzenia tego problemu - jednak listy ze zrozumieniem są wystarczająco szybkie, dodatkowo dodając fakt, że pisanie jest wystarczająco szybkie, aby rozwiązać problem.

Dla mnie było to 0,030 s (rzeczywiste), 0,026 s (użytkownik) i 0,004 s (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

Kod sprawdzający, czy w tablicy istnieją dwa elementy, których iloczyn równa się k:

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