Question Le moyen le plus rapide de vérifier si une valeur existe dans une liste


Je cherche 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 mon exemple.

La première méthode que j'essaie est (3.8sec 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 seconde méthode que j'essaie est (2x plus rapide: 1.9sec sur 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 Stackoverflow (2.74sec sur mon code réel):

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.81sec et la deuxième méthode prend 1.88sec. C'est une bonne amélioration mais:

Je suis un débutant avec Python / scripting et je veux savoir si un moyen le plus rapide existe pour faire les mêmes choses et économiser plus de temps de traitement?

Explication plus spécifique pour mon application:

Dans l'API de blender un peut accéder à une liste de particules:

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

De là, je peux accéder à son emplacement:

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

Et je teste pour chaque particule si un voisin existe en cherchant à l'emplacement de chaque particule comme:

if [x+1,y,z] in particles.location
    "find the identity of this neighbour particles in x:the index 
    of the particles array"
    particles.index([x+1,y,z])

500
2017-09-27 15:23


origine


Réponses:


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 permettront d'économiser. La seule façon de s’assurer est de bien évaluer. (Cela dépend aussi des opérations dont vous avez besoin)


1018
2017-09-27 15:25



Comme indiqué par d'autres, in peut être très lent pour les grandes listes. Voici quelques comparaisons des performances pour in, set et bisect. Notez que l'heure (en seconde) est en échelle logarithmique.

enter image description here

Code pour les tests:

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

107
2017-12-04 20:44



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

Usage

check_availablity('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.


29
2017-09-27 15:33



Vous pourriez mettre vos objets dans un set. Les recherches de set 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 la position de l'élément. Une alternative consiste à pré-trier votre liste puis à utiliser recherche binaire chaque fois que vous avez besoin de trouver un élément.


21
2017-09-27 15:25



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 qu'une bonne idée si un ne change pas et que 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.


14
2017-09-27 16:26



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

En bref, une recherche de filtre anti-bloom peut vous dire très rapidement si une valeur n'est absolument 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 pourriez 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 la «bibliothèque de filtres python bloom» fournira au moins quelques implémentations utiles.


5
2018-01-27 22:46



Sachez que le in l'opérateur teste non seulement l'égalité (==) mais aussi identité (is), la in logique pour lists est à peu près équivalent à le suivant (il est en fait écrit en C et non en Python, du 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, numpy.NAN a la propriété inhabituelle d'être n'étant pas é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 pour lists avec any() serait:

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

Cependant, je dois souligner que c'est un cas limite, et pour la grande majorité des cas, le in opérateur est hautement optimisé et exactement ce que vous voulez bien sûr (soit avec un list ou avec un set).


3
2018-02-19 13:27



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 les chaînes: regardez en bas:

  • -let "n" soit la longueur de votre liste
  • -option 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 / 2ième élément de la liste
      • si elle est plus grande, boucle à nouveau entre les index n / 2-n
      • si plus petit, boucle à nouveau entre les index 0-n / 2
      • si la même chose: vous l'avez trouvé
  • continuez à restreindre la liste jusqu'à ce que vous l'ayez trouvée ou que vous ayez seulement 2 numéros (ci-dessous et au-dessus de celui que vous recherchez)
  • cela trouvera tout é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-le dans la seconde colonne, 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 peut comparer / commander des 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 en valoir la peine


1
2017-09-24 13:35



Pour moi, c'était 0.030s (réel), 0.026s (utilisateur) et 0.004s (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

1
2017-12-29 08:28