Moyen le plus rapide de vérifier si une valeur existe dans une liste

Quel est le moyen le plus rapide de savoir si une valeur existe dans une liste (une liste contenant des millions de valeurs) et quel est son index?

Je sais que toutes les valeurs de la liste sont uniques comme dans cet exemple.

La première méthode que j'essaie est (3,8 secondes dans mon vrai code):

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

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

La deuxième méthode que j'essaie est (2x plus rapide: 1,9 sec pour mon vrai code):

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

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

Méthodes proposées par l'utilisateur Stack Overflow (2,74 s pour mon vrai code):

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

Dans mon code réel, la première méthode prend 3,81 secondes et la seconde méthode prend 1,88 secondes. C'est une bonne amélioration, mais:

Je suis un débutant en Python / scripting, et existe-t-il un moyen plus rapide de faire les mêmes choses et d'économiser plus de temps de traitement?

Explication plus spécifique pour mon application:

Dans l'API Blender, je peux accéder à une liste de particules:

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

De là, je peux accéder à l'emplacement d'une particule:

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

Et pour chaque particule, je teste si un voisin existe en recherchant chaque emplacement de particule comme ceci:

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

Le moyen le plus clair et le plus rapide de le faire.

Vous pouvez également envisager d'utiliser un set, mais la construction de cet ensemble à partir de votre liste peut prendre plus de temps que les tests d'adhésion plus rapides vous feront gagner. La seule façon d'en être certain est de bien se comparer. (cela dépend également des opérations dont vous avez besoin)

Comme indiqué par d'autres, inpeut être très lent pour les grandes listes. Voici quelques comparaisons des performances pour in, setet bisect. Notez que le temps (en secondes) est en échelle logarithmique.

Code de test:

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

Vous pouvez mettre vos articles dans un fichier set. Les recherches d'ensemble sont très efficaces.

Essayer:

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

modifier Dans un commentaire, vous dites que vous souhaitez obtenir l'index de l'élément. Malheureusement, les ensembles n'ont aucune notion de position des éléments. Une alternative consiste à pré-trier votre liste, puis à utiliser la recherche binaire chaque fois que vous avez besoin de trouver un élément.

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

Usage

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

Je crois que c'est le moyen le plus rapide de savoir si une valeur choisie est dans un tableau.

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"

Ce ne sera une bonne idée que si a ne change pas et nous pouvons donc faire la partie dict () une fois, puis l'utiliser à plusieurs reprises. Si cela change, veuillez fournir plus de détails sur ce que vous faites.

La question initiale était:

Quel est le moyen le plus rapide de savoir si une valeur existe dans une liste (une liste contenant des millions de valeurs) et quel est son index?

Il y a donc deux choses à trouver:

1. est un élément de la liste, et
2. quel est l'index (si dans la liste).

Pour cela, j'ai modifié le code @xslittlegrass pour calculer les index dans tous les cas et ajouté une méthode supplémentaire.

Résultats

Les méthodes sont:

1. in - fondamentalement si x dans b: retourne b.index (x)
2. try - try / catch sur b.index (x) (ignore la nécessité de vérifier si x dans b)
3. set - fondamentalement si x dans set (b): retourne b.index (x)
4. bissecte - trie b avec son index, recherche binaire de x dans trié (b). Notez le mod de @xslittlegrass qui retourne l'index dans le b trié, plutôt que dans le b d'origine)
5. reverse - forme un dictionnaire de recherche inversée d pour b; alors d [x] fournit l'indice de x.

Les résultats montrent que la méthode 5 est la plus rapide.

Fait intéressant, les méthodes try et set sont équivalentes dans le temps.

Code de test

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

Il semble que votre application puisse tirer avantage de l'utilisation d'une structure de données Bloom Filter.

En bref, une recherche de filtre de bloom peut vous dire très rapidement si une valeur n'est DEFINITIVEMENT PAS présente dans un ensemble. Sinon, vous pouvez effectuer une recherche plus lente pour obtenir l'index d'une valeur QUI POURRAIT ÊTRE POSSIBLE dans la liste. Donc, si votre application a tendance à obtenir le résultat "non trouvé" beaucoup plus souvent que le résultat "trouvé", vous pouvez voir une accélération en ajoutant un filtre Bloom.

Pour plus de détails, Wikipedia fournit un bon aperçu du fonctionnement des filtres Bloom, et une recherche sur le Web pour "bibliothèque de filtres Bloom Python" fournira au moins quelques implémentations utiles.

Sachez que l' inopérateur teste non seulement l'égalité ( ==) mais aussi l'identité ( is), la inlogique delist s est à peu près équivalente à la suivante (elle est en fait écrite en C et non en Python cependant, au moins en 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

Dans la plupart des cas, ce détail n'est pas pertinent, mais dans certaines circonstances, il peut surprendre un novice Python, par exemple, qui numpy.NANa la propriété inhabituelle de ne pas être égal à lui - même :

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

Pour distinguer ces cas inhabituels, vous pouvez utiliser any()comme:

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

Noter la in logique de lists avec any()serait:

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

Cependant, je dois souligner qu'il s'agit d'un cas de bord, et pour la grande majorité des cas, l' inopérateur est hautement optimisé et exactement ce que vous voulez bien sûr (avec listou avec un set).

Ou utilisez __contains__:

sequence.__contains__(value)

Démo:

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

La solution de @Winston Ewert donne une grande accélération pour les très grandes listes, mais cette réponse de stackoverflow indique que la construction try: / except: / else: sera ralentie si la branche except est souvent atteinte. Une alternative est de profiter de la .get()méthode de dictée:

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"

La .get(key, default)méthode est juste pour le cas où vous ne pouvez pas garantir qu'une clé sera dans le dict. Si la clé est présente, elle renvoie la valeur (comme le ferait dict[key]), mais lorsqu'elle ne l'est pas, .get()renvoie votre valeur par défaut (ici None). Vous devez vous assurer dans ce cas que la valeur par défaut choisie ne sera pas a.

Ce n'est pas le code, mais l'algorithme pour une recherche très rapide.

Si votre liste et la valeur que vous recherchez sont tous des nombres, c'est assez simple. Si cordes: regardez en bas:

• -Laissez "n" la longueur de votre liste
• -Étape facultative: si vous avez besoin de l'index de l'élément: ajoutez une deuxième colonne à la liste avec l'index actuel des éléments (0 à n-1) - voir plus loin
• Commandez votre liste ou une copie de celle-ci (.sort ())
• Boucle à travers:
  • Comparez votre numéro au n / 2ème élément de la liste
    • Si plus grand, boucle à nouveau entre les index n / 2-n
    • Si plus petit, boucle à nouveau entre les index 0-n / 2
    • Si pareil: tu l'as trouvé
• Continuez à restreindre la liste jusqu'à ce que vous l'ayez trouvée ou ayez seulement 2 chiffres (en dessous et au-dessus de celui que vous recherchez)
• Cela trouvera n'importe quel élément dans au plus 19 étapes pour une liste de 1.000.000 (log (2) n pour être précis)

Si vous avez également besoin de la position d'origine de votre numéro, recherchez-la dans la deuxième colonne d'index.

Si votre liste n'est pas composée de nombres, la méthode fonctionne toujours et sera la plus rapide, mais vous devrez peut-être définir une fonction qui pourra comparer / ordonner les chaînes.

Bien sûr, cela nécessite l'investissement de la méthode sorted (), mais si vous continuez à réutiliser la même liste pour la vérification, cela peut valoir la peine.

Parce que la question n'est pas toujours censée être comprise comme le moyen technique le plus rapide - je suggère toujours le moyen le plus simple et le plus rapide pour comprendre / écrire: une compréhension de liste, une ligne

[i for i in list_from_which_to_search if i in list_to_search_in]

J'ai eu un list_to_search_inavec tous les éléments, et je voulais retourner les index des éléments dans le list_from_which_to_search.

Cela renvoie les index dans une belle liste.

Il existe d'autres façons de vérifier ce problème - cependant, la compréhension des listes est assez rapide, ajoutant au fait de l'écrire assez rapidement, pour résoudre un problème.

Pour moi, c'était 0,030 s (réel), 0,026 s (utilisateur) et 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

Code pour vérifier si deux éléments existent dans un tableau dont le produit est égal à k:

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