La creación de la nueva lista es todo lo eficiente que puede ser si se quiere mantener el orden y las repeticiones. El verdadero cuello de botella es el operador de pertenencia in en una lista (ind1
). Para cada elemento de indices
tienen que iterar desde el inicio hasta encontrar el elemento o en el peor caso hasta el final, lo cual es tremendamente ineficiente:
import random
indices = range(50001)
ind1 = random.sample(indices, 5)
%timeit [x for x in indices if x not in ind1]
6.95 ms ± 58.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
ind1 = random.sample(indices, 10000) # <<<<<<<<<<<<<<<
%timeit [x for x in indices if x not in ind1]
8.54 s ± 157 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
ind1 = random.sample(indices, 50000) # <<<<<<<<<<<<<<<
%timeit [x for x in indices if x not in ind1]
23 s ± 92.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
La solución es pasar ind2
a un conjunto, en el cual la búsqueda de un elemento es muchísimo más rápida gracias a la implementación mediante tablas hash:
import random
indices = range(50001)
ind1 = random.sample(indices, 5)
%%timeit
ind_set = set(ind1)
ind2 = [x for x in indices if x not in ind_set]
2.91 ms ± 67.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
indices = range(50001)
ind1 = random.sample(indices, 10000)
%%timeit
ind_set = set(ind1)
ind2 = [x for x in indices if x not in ind_set]
3.66 ms ± 84.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
indices = range(50001)
ind1 = random.sample(indices, 50000)
%%timeit
ind_set = set(ind1)
ind2 = [x for x in indices if x not in ind_set]
4.38 ms ± 60.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Otra posibilidad es que uses NumPy y filtres el array con np.in1d
:
import numpy as np
indices = np.arange(50001)
ind1 = np.random.choice(indices, size=10000, replace=False)
%timeit ind2 = indices[~np.in1d(indices, ind1)]
2.38 ms ± 22.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)