2

Tengo un conjunto de índices en una lista. Utilizando la librería random obtengo una sublista pseudoaleatoria de esos índices:

indices = [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]
ind1 = random.sample(ind, 3)

Una vez hecho esto, me gustaría obtener en otra sublista, los valores que no estén en ind1 pero sí en indices. He utilizado esto:

 ind2 = [x for x in indices if x not in ind1]

Obtengo los valores que deseo, pero si la lista de indices inicial es muy grande, este proceso tarda mucho. Por ejemplo, para una lista de 50.000 elementos tarda 10,52s. ¿Hay alguna manera de hacerlo más rápido?

2
  • ¿ind2 debe mantener el mismo orden que indices?¿Si hay repeticiones en indices deben apaarecer también repetidos en ind2?
    – FJSevilla
    el 20 mar. 2020 a las 9:12
  • Si, deben mantenerse las repeticiones (en el caso de que en ind1 no esten). ¿A qué te refieres con el mismo orden? Si te refieres a que la secuencia de aparición sea la misma, no es necesario, sólo quiero que los contenga.
    – Jimena
    el 20 mar. 2020 a las 9:17

1 respuesta 1

2

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)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.