Snelste manier om te controleren of een waarde bestaat in een lijst

Wat is de snelste manier om te weten of een waarde in een lijst bestaat (een lijst met miljoenen waarden erin) en wat de index is?

Ik weet dat alle waarden in de lijst uniek zijn zoals in dit voorbeeld.

De eerste methode die ik probeer is (3.8 sec in mijn echte code):

a = [4,2,3,1,5,6]
if a.count(7) == 1:
    b=a.index(7)
    "Do something with variable b"

De tweede methode die ik probeer is (2x sneller: 1,9 sec voor mijn echte code):

a = [4,2,3,1,5,6]
try:
    b=a.index(7)
except ValueError:
    "Do nothing"
else:
    "Do something with variable b"

Voorgestelde methoden van Stack Overflow-gebruiker (2.74 SEC voor mijn echte code):

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

In mijn echte code duurt de eerste methode 3.81 sec en de tweede methode duurt 1,88 sec.
Het is een goede verbetering, maar:

Ik ben een beginner met Python / Scripting, en is er een snellere manier om dezelfde dingen te doen en meer verwerkingstijd te besparen?

Meer specifieke uitleg voor mijn aanvraag:

In de Blender API heb ik toegang tot een lijst met deeltjes:

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

Vanaf daar kan ik toegang krijgen tot een ligging van een deeltjes:

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

En voor elk deeltje dat ik test als er een buurman bestaat door elke deeltjeslocatie zoals SO te zoeken:

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

Antwoord 1, Autoriteit 100%

7 in a

duidelijkste en snelste manier om het te doen.

U kunt ook overwegen om een ​​sette gebruiken, maar bouwen van die set uit uw lijst kan meer tijd kosten dan snellere lidmaatschapstests zal worden opgeslagen. De enige manier om zeker te zijn, is goed te benchmark. (Dit hangt ook af van welke operaties u nodig heeft)

Antwoord 2, Autoriteit 15%

Zoals vermeld door anderen, kan inzeer traag zijn voor grote lijsten. Hier zijn enkele vergelijkingen van de uitvoeringen voor in, setEN bisect. Let op de tijd (in de tweede) is in logschaal.

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

Antwoord 3, Autoriteit 3%

U kunt uw items in een set. Stel opzoekingen in zijn zeer efficiënt.

Probeer:

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

bewerken in een opmerking die u zegt dat u de index van het element wilt krijgen. Helaas hebben sets geen idee van elementpositie. Een alternatief is om uw lijst te sorteren en vervolgens te gebruiken binair zoeken elke keer dat u moet vinden een element.

Antwoord 4, Autoriteit 2%

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

Gebruik

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

Ik geloof dat dit de snelste manier is om te weten of een gekozen waarde in een array staat.

Antwoord 5

De oorspronkelijke vraag was:

Wat is de snelste manier om te weten of een waarde in een lijst (een lijst) voorkomt?
met miljoenen waarden erin) en wat zijn index is?

Er zijn dus twee dingen te vinden:

1. is een item in de lijst, en
2. wat is de index (indien in de lijst).

Hiervoor heb ik de @xslittlegrass-code aangepast om in alle gevallen indexen te berekenen, en een extra methode toegevoegd.

Resultaten

Methoden zijn:

1. in–in principe als x in b: return b.index(x)
2. try–try/catch op b.index(x) (sla de noodzaak om te controleren of x in b staat)
3. set–in principe als x in set(b): return b.index(x)
4. doorsnijden–sorteer b met zijn index, binair zoeken naar x in gesorteerd(b).
   Opmerking mod van @xslittlegrass die de index retourneert in de gesorteerde b,
   in plaats van het origineel b)
5. omgekeerd–vorm een omgekeerd opzoekwoordenboek d voor b; dan
   d[x] levert de index van x.

De resultaten laten zien dat methode 5 de snelste is.

Interessant is dat de probeeren de setmethoden equivalent zijn in de tijd.

Testcode

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

Antwoord 6

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"

Dit is alleen een goed idee als a niet verandert en dus kunnen we het dict()-gedeelte één keer doen en het dan herhaaldelijk gebruiken. Als a wel verandert, geef dan meer details over wat je aan het doen bent.

Antwoord 7

Het klinkt alsof uw toepassing voordeel kan halen uit het gebruik van een Bloom Filter-gegevensstructuur.

Kortom, een zoekactie van een bloeifilter kan u heel snel vertellen of een waarde ZEKER NIET aanwezig is in een set. Anders kunt u langzamer opzoeken om de index te krijgen van een waarde die MOGELIJK in de lijst staat. Dus als uw toepassing de neiging heeft om veel vaker het resultaat “niet gevonden” te krijgen dan het resultaat “gevonden”, ziet u mogelijk een versnelling door een Bloom-filter toe te voegen.

Voor details biedt Wikipedia een goed overzicht van hoe Bloom-filters werken, en een zoekopdracht op internet naar “python bloom-filterbibliotheek” levert op zijn minst een paar nuttige implementaties op.

Antwoord 8

Houd er rekening mee dat de operator inniet alleen gelijkheid (==) maar ook identiteit (is), de inlogica voor lists is ongeveer gelijk aanhet volgende (het is eigenlijk geschreven in C en niet Python, althans 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 de meeste gevallen is dit detail niet relevant, maar in sommige omstandigheden kan het een beginner in Python verbazen, bijvoorbeeld, numpy.NANheeft de ongebruikelijke eigenschap niet gelijk zijn aan zichzelf:

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

Om onderscheid te maken tussen deze ongebruikelijke gevallen kunt u any()gebruiken zoals:

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

Let op de inlogica voor lists met any()zou zijn:

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

Ik moet echter benadrukken dat dit een randgeval is, en voor de overgrote meerderheid van de gevallen is de in-operator sterk geoptimaliseerd en precies wat je wilt natuurlijk (ofwel met een listof met een set).

Antwoord 9

Of gebruik __contains__:

sequence.__contains__(value)

Demo:

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

Antwoord 10

Dit is niet de code, maar het algoritme voor zeer snel zoeken.

Als uw lijst en de waarde die u zoekt allemaal getallen zijn, is dit vrij eenvoudig. Als strings: kijk onderaan:

• -Laat “n” de lengte van je lijst zijn
• -Optionele stap: als je de index van het element nodig hebt: voeg een tweede kolom toe aan de lijst met de huidige index van elementen (0 tot n-1) – zie later
• Bestel uw lijst of een kopie ervan (.sort())
• Doorloop:
  • Vergelijk je nummer met het n/2e element van de lijst
    • Indien groter, loop opnieuw tussen indexen n/2-n
    • Indien kleiner, loop opnieuw tussen indexen 0-n/2
    • Als hetzelfde: je hebt het gevonden
• Blijf de lijst verfijnen tot je hem hebt gevonden of slechts 2 nummers hebt (onder en boven degene die je zoekt)
• Dit vindt elk element in maximaal 19 stappen voor een lijst van 1.000.000(log(2)n om precies te zijn)

Als je ook de originele positie van je nummer nodig hebt, zoek het dan op in de tweede indexkolom.

Als uw lijst niet uit getallen bestaat, werkt de methode nog steeds en is deze het snelst, maar u moet mogelijk een functie definiëren die strings kan vergelijken/ordenen.

Natuurlijk is hiervoor de investering van de methode Sort() nodig, maar als je dezelfde lijst blijft gebruiken om te controleren, kan het de moeite waard zijn.

Antwoord 11

Omdat de vraag niet altijd als de snelste technische manier moet worden begrepen, stel ik altijd voor de eenvoudigste snelste manier om te begrijpen/schrijven: een lijstbegrip, one-liner

[i for i in list_from_which_to_search if i in list_to_search_in]

Ik had een list_to_search_inmet alle items en wilde de indexen van de items in de list_from_which_to_searchretourneren.

Dit geeft de indexen terug in een mooie lijst.

Er zijn andere manieren om dit probleem te controleren, maar het begrijpen van de lijst is snel genoeg, en bovendien is het snel genoeg geschreven om een probleem op te lossen.

Antwoord 12

Als u slechts één element in een lijst wilt controleren,

7 in list_data

is de snelste oplossing. Merk echter op dat

7 in set_data

is een bijna gratis operatie, onafhankelijk van de grootte van de set! Het maken van een set uit een grote lijst is 300 tot 400 keer langzamer dan in, dus als u op veel elementen moet controleren, is het maken van een set eerst sneller.

Plot gemaakt met 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()