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

816

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])
Jean-Francois Gallant
źródło
5
W pythonie rzecz w nawiasach kwadratowych nazywana jest listą, a nie tablicą. Zamiast używać listy, użyj zestawu. Albo bisect
posortuj
Więc naprawdę potrzebujesz żonglować indeksami? Czy zamówienie nie ma znaczenia, a chcesz po prostu przeprowadzić testy wysyłkowe członków, skrzyżowania itp.? Porządek słów zależy od tego, co naprawdę próbujesz zrobić. Zestawy mogą dla Ciebie działać, a wtedy są naprawdę dobrą odpowiedzią, ale nie możemy tego stwierdzić na podstawie pokazanego kodu.
2
Prawdopodobnie musisz określić w swoim pytaniu, że nie potrzebujesz wartości, ale jej indeks.
Roman Bodnarchuk
Redaguję moje pytanie i staram się wyjaśnić jaśniej, co chcę zrobić ... Mam taką nadzieję ...
Jean-Francois Gallant
1
@StevenRumbalski: ponieważ zestaw nie może zawierać treści powielania, podczas gdy Jean chce przechowywać lokalizację cząstek (x, y, z mogą być takie same), nie możemy użyć zestawu w tym przypadku
Hieu Vo

Odpowiedzi:

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

Rafe Kettler
źródło
5
Ale nie masz tego indeksu, a uzyskanie go będzie kosztować to, co zaoszczędziłeś.
rodrigo
6
jak: Jeśli 7 w a: b = a.index (7)?
Jean-Francois Gallant
26
@StevenRumbalski: Zestawy są opcją tylko wtedy, gdy nie trzeba ich zamawiać (a zatem mają indeks). I zestawy wyraźnie wymienione w odpowiedzi, to po prostu także daje prostą odpowiedź na pytanie, jak OP poprosił go. Nie sądzę, że to jest warte -1.
Redaguję moje pytanie i staram się jaśniej wyjaśnić, co chcę zrobić ... Mam taką nadzieję ...
Jean-Francois Gallant
1
Okej, wypróbowuję twoją metodę w moim prawdziwym kodzie i zajmuje to trochę więcej czasu, prawdopodobnie dlatego, że muszę znać indeks wartości. Drugą metodą sprawdzam, czy istnieje i jednocześnie uzyskuję indeks.
Jean-Francois Gallant
212

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.

wprowadź opis zdjęcia tutaj

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()
xslittlegrass
źródło
15
Uwielbiam wycinać i wklejać, taki kod wykonywalny w odpowiedziach. Aby zaoszczędzić innym kilka sekund czasu, potrzebujesz 3 importów: import random / import bisect / import matplotlib.pyplot as plta następnie zadzwoń:profile()
kghastie
1
która to wersja Pythona?
cowbert
zawsze świetnie, aby uzyskać kod, ale po prostu heads up musiałem zaimportować czas do uruchomienia
co
I nie zapomnij o skromnym range()obiekcie. Podczas używania var in [integer list]sprawdź, czy range()obiekt może modelować tę samą sekwencję. Bardzo zbliżony do zestawu, ale bardziej zwięzły.
Martijn Pieters
37

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.

NPE
źródło
A jeśli potem chcę poznać indeks tej wartości, jest to możliwe i masz szybki sposób, aby to zrobić?
Jean-Francois Gallant
@ Jean-FrancoisGallant: W tym przypadku zestawy nie będą zbyt przydatne. Możesz wstępnie posortować listę, a następnie użyć wyszukiwania binarnego. Proszę zobaczyć moją zaktualizowaną odpowiedź.
NPE
Redaguję moje pytanie i staram się wyjaśnić jaśniej, co chcę zrobić ... Mam taką nadzieję ...
Jean-Francois Gallant
30
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.

Tiago Moutinho
źródło
71
return 'a' in a?
Shikiryu,
4
Musisz wstawić kod do definicji: def listValue (): a = [1,2,3,4, „a”, „b”, „c”] return „a” w ax = listValue () print ( x)
Tenzin,
12
To poprawna odpowiedź w języku Python, to po prostu zły, czytelny kod.
Rick Henderson
1
Uwaga! To pasuje, podczas gdy jest to prawdopodobnie to, czego się nie spodziewałeś:o='--skip'; o in ("--skip-ias"); # returns True !
Alex F
3
@Alex F inoperator działa w ten sam sposób, aby przetestować członkostwo w podciągu. Mylące jest tutaj to, że prawdopodobnie ("hello")nie jest to krotka o pojedynczej wartości, podczas gdy ("hello",)jest - przecinek robi różnicę. o in ("--skip-ias",)jest Falsezgodnie z oczekiwaniami.
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"

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.

Winston Ewert
źródło
Działa, ale nie jest zaimplementowany w moim kodzie: „Błąd typu: nieokreślony typ:„ lista ”
Jean-Francois Gallant
1
@ Jean-FrancoisGallant, prawdopodobnie dlatego, że używasz list, na których naprawdę powinieneś używać krotek. Jeśli potrzebujesz kompleksowych porad, jak przyspieszyć swój kod, powinieneś opublikować go na codereview.stackexchange.com. Tam otrzymasz porady dotyczące stylu i wydajności.
Winston Ewert
To bardzo sprytne rozwiązanie problemu. Zamiast try oprócz konstrukcja, zrobiłbym: a_index = index.get (7), który ustawi się na None, jeśli klucz nie zostanie znaleziony.
murphsp1,
14

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

wprowadź opis zdjęcia tutaj

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()
DarrylG
źródło
Literówka w twoim opisie („odwrotna pętla w górę” powinna brzmieć „wstecznego wyszukiwania”, nie?)
Cam U
@ CamU - tak, poprawiłem to. Dzięki za zauważenie.
DarrylG
7

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.

matt2000
źródło
7

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

Chris_Rands
źródło
NAN == Zwracanie false w sieci NAN nie ma w tym nic niezwykłego. Jest to zachowanie zdefiniowane w standardzie IEEE 754.
TommyD,
2

Lub użyj __contains__:

sequence.__contains__(value)

Próbny:

>>> l=[1,2,3]
>>> l.__contains__(3)
True
>>> 
U10 do przodu
źródło
2

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.

użytkownik3897315
źródło
1

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.

Adam
źródło
26
Zapomniałeś wspomnieć, że wyjaśniony algorytm to proste wyszukiwanie binarne.
diugalde
0

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.

Vaidøtas Ivøška
źródło
-2

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
Tabin1000
źródło
-2

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)
ravi tanwar
źródło