La forma más rápida de verificar si existe un valor en una lista

¿Cuál es la forma más rápida de saber si existe un valor en una lista (una lista con millones de valores) y cuál es su índice?

Sé que todos los valores en la lista son únicos como en este ejemplo.

El primer método que intento es (3.8 segundos en mi código real):

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

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

El segundo método que intento es (2 veces más rápido: 1.9 segundos para mi código real):

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

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

Métodos propuestos del usuario de Stack Overflow (2.74 segundos para mi código real):

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

En mi código real, el primer método tarda 3.81 segundos y el segundo método lleva 1.88 segundos. Es una buena mejora, pero:

Soy un principiante con Python / scripting, y ¿hay una manera más rápida de hacer lo mismo y ahorrar más tiempo de procesamiento?

Explicación más específica para mi aplicación:

En la API de Blender puedo acceder a una lista de partículas:

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

Desde allí, puedo acceder a la ubicación de una partícula:

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

Y para cada partícula pruebo si existe un vecino buscando cada ubicación de la partícula de esta manera:

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

La forma más clara y rápida de hacerlo.

También puede considerar usar un set, pero construir ese conjunto de su lista puede llevar más tiempo del que ahorrará la prueba de membresía más rápida. La única forma de estar seguro es comparar bien. (esto también depende de las operaciones que requiera)

Como lo han dicho otros, inpuede ser muy lento para listas grandes. Aquí hay algunas comparaciones de las actuaciones para in, sety bisect. Tenga en cuenta que el tiempo (en segundos) está en escala logarítmica.

Código para pruebas:

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

Podrías poner tus artículos en un set. Las búsquedas de conjuntos son muy eficientes.

Tratar:

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

editar En un comentario, dice que desea obtener el índice del elemento. Desafortunadamente, los conjuntos no tienen noción de posición del elemento. Una alternativa es ordenar previamente su lista y luego usar la búsqueda binaria cada vez que necesite encontrar un elemento.

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

Uso

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

Creo que esta es la forma más rápida de saber si un valor elegido está en una matriz.

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"

Esto solo será una buena idea si a no cambia y, por lo tanto, podemos hacer la parte dict () una vez y luego usarla repetidamente. Si un cambio cambia, proporcione más detalles sobre lo que está haciendo.

La pregunta original fue:

¿Cuál es la forma más rápida de saber si existe un valor en una lista (una lista con millones de valores) y cuál es su índice?

Por lo tanto, hay dos cosas para encontrar:

1. es un elemento de la lista y
2. cuál es el índice (si está en la lista).

Hacia esto, modifiqué el código @xslittlegrass para calcular índices en todos los casos, y agregué un método adicional.

Resultados

Los métodos son:

1. en - básicamente si x en b: devuelve b.index (x)
2. try - try / catch en b.index (x) (omite tener que verificar si x en b)
3. set - básicamente si x en set (b): devuelve b.index (x)
4. bisect: ordena b con su índice, búsqueda binaria de x en sorted (b). Nota mod de @xslittlegrass que devuelve el índice en la ordenada b, en lugar de la b original)
5. reverse: forma un diccionario de búsqueda inversa d para b; entonces d [x] proporciona el índice de x.

Los resultados muestran que el método 5 es el más rápido.

Curiosamente, los métodos try y set son equivalentes en el tiempo.

Código de prueba

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

Parece que su aplicación podría obtener ventajas del uso de una estructura de datos de Bloom Filter.

En resumen, una búsqueda de filtro de floración puede decirle muy rápidamente si un valor NO ESTÁ DEFINITIVAMENTE presente en un conjunto. De lo contrario, puede realizar una búsqueda más lenta para obtener el índice de un valor que POSIBLEMENTE PUEDE SER en la lista. Entonces, si su aplicación tiende a obtener el resultado "no encontrado" con mucha más frecuencia que el resultado "encontrado", es posible que vea una mayor velocidad al agregar un filtro Bloom.

Para más detalles, Wikipedia proporciona una buena visión general de cómo funcionan los filtros Bloom, y una búsqueda en la web de "biblioteca de filtros de floración Python" proporcionará al menos un par de implementaciones útiles.

Tenga en cuenta que el inoperador prueba no solo la igualdad ( ==) sino también la identidad ( is), la inlógica para lists es aproximadamente equivalente a la siguiente (aunque en realidad está escrita en C y no en Python, al menos 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

En la mayoría de las circunstancias, este detalle es irrelevante, pero en algunas circunstancias puede sorprender a un principiante de Python, por ejemplo, numpy.NANtiene la propiedad inusual de no ser igual a sí mismo :

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

Para distinguir entre estos casos inusuales, puede usar any()como:

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

Tenga en cuenta que la inlógica para lists con any()sería:

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

Sin embargo, debo enfatizar que este es un caso extremo, y para la gran mayoría de los casos, el inoperador está altamente optimizado y, por supuesto, exactamente lo que desea (ya sea con listo con a set).

O use __contains__:

sequence.__contains__(value)

Manifestación:

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

La solución de @Winston Ewert produce una gran aceleración para listas muy grandes, pero esta respuesta de stackoverflow indica que la construcción try: / except: / else: se ralentizará si a menudo se alcanza la rama except. Una alternativa es aprovechar el .get()método para el dict:

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"

El .get(key, default)método es solo para el caso en el que no puede garantizar que una clave esté en el dict. Si la clave está presente, devuelve el valor (como lo haría dict[key]), pero cuando no lo está, .get()devuelve su valor predeterminado (aquí None). Debe asegurarse en este caso de que el valor predeterminado elegido no estará en a.

Este no es el código, sino el algoritmo para una búsqueda muy rápida.

Si su lista y el valor que está buscando son todos números, esto es bastante sencillo. Si las cadenas: mira en la parte inferior:

• -Deje que "n" sea la longitud de su lista
• -Paso opcional: si necesita el índice del elemento: agregue una segunda columna a la lista con el índice actual de elementos (0 a n-1) - vea más adelante
• Solicite su lista o una copia de ella (.sort ())
• Recorrer:
  • Compare su número con el elemento n / 2 de la lista
    • Si es más grande, repita nuevamente entre los índices n / 2-n
    • Si es más pequeño, repita nuevamente entre los índices 0-n / 2
    • Si es lo mismo: lo encontraste
• Siga reduciendo la lista hasta que la haya encontrado o solo tenga 2 números (debajo y encima del que está buscando)
• Esto encontrará cualquier elemento en un máximo de 19 pasos para una lista de 1,000,000 (log (2) n para ser precisos)

Si también necesita la posición original de su número, búsquela en la segunda columna de índice.

Si su lista no está compuesta de números, el método aún funciona y será más rápido, pero es posible que necesite definir una función que pueda comparar / ordenar cadenas.

Por supuesto, esto necesita la inversión del método sorted (), pero si sigue reutilizando la misma lista para verificar, puede valer la pena.

Debido a que no siempre se supone que la pregunta debe entenderse como la forma técnica más rápida, siempre sugiero la forma más directa y más rápida de entender / escribir: una lista de comprensión, una línea

[i for i in list_from_which_to_search if i in list_to_search_in]

Tuve un list_to_search_incon todos los elementos, y quería devolver los índices de los elementos en el list_from_which_to_search.

Esto devuelve los índices en una buena lista.

Hay otras formas de verificar este problema; sin embargo, las comprensiones de listas son lo suficientemente rápidas, lo que se suma al hecho de escribirlo lo suficientemente rápido como para resolver un problema.

Para mí fue 0.030 segundos (real), 0.026 segundos (usuario) y 0.004 segundos (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

Código para verificar si existen dos elementos en la matriz cuyo producto es igual a k:

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