Actualmente tengo una colección de cientos de miles de ID como números enteros y estoy realizando la siguiente tarea (digamos que esta colección está almacenada en una lista cache por ahora):

cache = list()
# lets say this cache is populated
for x in range(0,1000000):
    if x not in cache:
        #do_something

¿Cuánto me cuesta usar una lista para buscar not in algo? ¿Me beneficiaría de utilizar otra estructura de datos y, de ser así, cuál sería la mejor?

3
JC1 12 nov. 2017 a las 20:40

2 respuestas

La mejor respuesta

Debería considerar usar un set. Si bien la complejidad del tiempo en el peor de los casos para x in cache aún sería O (n), el caso promedio es O (1) (fuente).

4
Mureinik 12 nov. 2017 a las 17:44

Si pudieras crear los datos en cache a través de un generador, podrías renunciar a crear una lista del orden de 1e5 y aprovechar los ahorros de memoria. Luego, simplemente puede probar x not in con lo siguiente:

desired_id = 123456
cache = some_function_to_generate_integer_ids()  # cache is a generator
print desired_id in cache

En el que se imprimirá False si desired_id no está en la caché.

1
ebb-earl-co 12 nov. 2017 a las 18:21