La forma más rápida de comprobar si existe un valor en una lista
¿Cuál es la forma más rápida de comprobar si un valor existe en una lista muy grande (con millones de valores) y cuál es su índice?
7 in a
La forma más clara y rápida de hacerlo.
También puedes considerar usar un set, pero construir ese conjunto a partir de tu lista puede llevar más tiempo del que ahorrará una prueba de membresía más rápida. La única forma de estar seguro es realizar una buena evaluación comparativa. (esto también depende de las operaciones que requiera)
Como han dicho otros, inpuede ser muy lento para listas grandes. A continuación se muestran algunas comparaciones de las actuaciones de in, sety bisect. Tenga en cuenta que el tiempo (en segundos) está en escala logarítmica.
Código para probar:
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 too long or up if there are too 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()
Podrías poner tus artículos en un archivo set. Las búsquedas de conjuntos son muy eficientes.
Intentar:
s = set(a)
if 7 in s:
# do stuff
editar En un comentario dices que te gustaría obtener el índice del elemento. Desafortunadamente, los conjuntos no tienen noción de la posición de los elementos. Una alternativa es ordenar previamente la lista y luego utilizar la búsqueda binaria cada vez que necesite encontrar un elemento.
La pregunta original era:
¿Cuál es la forma más rápida de saber si un valor existe en una lista (una lista con millones de valores) y cuál es su índice?
Por tanto, hay dos cosas que encontrar:
- es un elemento en la lista, y
- ¿Cuál es el índice (si está en la lista)?
Para lograr esto, modifiqué el código @xslittlegrass para calcular índices en todos los casos y agregué un método adicional.
Resultados
Los métodos son:
- en - básicamente si x en b: devuelve b.index(x)
- try--try/catch en b.index(x) (evita tener que comprobar si x está en b)
- set--básicamente si x en set(b): devuelve b.index(x)
- bisect: ordenar b con su índice, búsqueda binaria de x en ordenado (b). Nota mod de @xslittlegrass que devuelve el índice en la b ordenada, en lugar de la b original)
- inversa: 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()