python - tamaño - La forma más rápida de verificar si existe un valor en una lista

saber indice de una lista python

Question

Estoy buscando la forma más rápida de saber si existe un valor en una lista (una lista con millones de valores en ella) y cuál es su índice. Sé que todos los valores en la lista son únicos como mi ejemplo.

El primer método que intento es (3.8sec 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 seg en 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 por el usuario de Stackoverflow (2.74 segundos en 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 toma 3.81sec y el segundo método toma 1.88sec. Es una buena mejora pero:

Soy un principiante en Python / scripting y quiero saber si existe una manera más rápida de hacer las mismas cosas y ahorrar más tiempo de proceso.

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

En la API de blender puede acceder a una lista de partículas:

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

Desde allí, puedo acceder a su ubicación:

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

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

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

Answer 1

Como han dicho otros, in puede ser muy lento para listas grandes. Aquí hay algunas comparaciones de las actuaciones para in , set y bisect . Tenga en cuenta que el tiempo (en segundo) está en la escala de registro.

Código de prueba:

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

Answer 2

Este no es el código, sino el algoritmo para búsquedas muy rápidas.

Si su lista y el valor que está buscando son todos números, esto es bastante sencillo, si se trata de cadenas: mire la parte inferior:

• -let "n" sea la longitud de tu 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
• ordene su lista o una copia de ella (.sort ())
• bucle a través de
  • compara tu número con el elemento n / 2 de la lista
    • si es más grande, repite el ciclo entre los índices n / 2-n
    • Si es más pequeño, repite el bucle 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 (por debajo y por encima del que busca)
• Esto encontrará cualquier elemento en un máximo de 19 pasos para obtener 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úsquelo en la segunda columna, índice

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

Por supuesto, esto requiere la inversión del método ordenado (), pero si continúa reutilizando la misma lista para la comprobación, puede valer la pena.

Answer 3

O use __contains__ :

sequence.__contains__(value)

Manifestación:

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

Answer 4

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

Answer 5

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

En resumen, una búsqueda de filtro de floración puede indicarle muy rápidamente si un valor NO ESTÁ DEFINITIVAMENTE presente en un conjunto. De lo contrario, puede hacer una búsqueda más lenta para obtener el índice de un valor que POSIBLEMENTE PODRÍA ESTAR EN la lista. Entonces, si su aplicación tiende a obtener el resultado "no encontrado" con mucha mayor frecuencia que el resultado "encontrado", es posible que vea una aceleración agregando un filtro Bloom.

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

Answer 6

Tenga en cuenta que el operador in comprueba no solo la igualdad ( == ) sino también la identidad ( is ), la lógica in para la list s es aproximadamente equivalente a la siguiente (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 dejar sorprendido a un principiante de Python, por ejemplo, numpy.NAN tiene 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 in cuenta que la lógica de la list s con any() sería:

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

Sin embargo, debo enfatizar que este es un caso de ventaja, y para la gran mayoría de los casos, el operador in está altamente optimizado y es exactamente lo que quiere, por supuesto (ya sea con una list o con un set ).

Answer 7

Usted podría poner sus artículos en un set . Los conjuntos de búsquedas son muy eficientes.

Tratar:

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

editar En un comentario usted dice que le gustaría 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.

Answer 8

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)

Answer 9

7 in a

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

También puede considerar el uso de un set , pero construir ese conjunto a partir de su lista puede llevar más tiempo de lo que ahorrará una prueba de membresía más rápida. La única manera de estar seguro es hacer una buena referencia. (Esto también depende de las operaciones que requiera)

Answer 10

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 a sí cambia, proporcione más detalles sobre lo que está haciendo.

Answer 11

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.

Answer 12

present = False
searchItem = ''d''
myList = [''a'', ''b'', ''c'', ''d'', ''e'']
if searchItem in myList:
   present = True
   print(''present = '', present)
else:
   print(''present = '', present)