Intento que sea un código MUY eficiente, evitando usar bucles
Va a ser complicado por la naturaleza del problema y por la de la estructura de datos en si misma. Tendrás que iterar sobre la lista, explícitamente o implícitamente.
La paradoja es que tu código usa "muchos bucles", lo hace de forma encubierta en la implementación en C de list.remove
. Las dos partes de la función en las que quiero hacer hincapié son:
El ciclo que itera sobre la lista:
for (i = 0; i < Py_SIZE(self); i++) {...}
La comparación:
int cmp = PyObject_RichCompareBool(obj, value, Py_EQ);
Cuando llamamos a list.remove
por debajo lo que se hace es iterar sobre la lista e ir comparando cada item para ver si es igual al que queremos eliminar, si se encuentra se elimina y se rompe el ciclo, si no se encuentra (se completa el ciclo sin encontrarlo) se genera una excepción.
Si implementáramos list.remove
en Python podríamos hacer algo como:
def remove(self, value):
for index, item in enumerate(self):
if item == value:
del self[index]
return None
raise ValueError(f"value" not in list)
En definitiva, aplicar list.remove
repetidamente tiene dos problemas que penalizan mucho el tiempo de ejecución:
Por cada llamada se ejecuta un ciclo que itera sobre la lista, en el peor de los casos (el valor no existe en la lista) se iterara sobre la lista completa.
Por cada iteración del ciclo anterior se tiene que comprobar si el item es igual al valor a eliminar.
Esto implica que en tu código hay realmente len(del_values)
ciclos implícitos iterando sobre values
, cada uno con un número de iteraciones determinado por la posición del item a eliminar en la lista values
con respecto al inicio de la lista (más iteraciones cuanto mayor sea su indice).
¿Hay formas de hacerlo más eficiente?
La respuesta a este tipo de preguntas no es normalmente simple. Podemos hacernos muchas preguntas que tendran respuestas variadas dependiendo del caso real de uso concretro, por ejemplo, con respecto a las listas y su contenido, ¿Se puede asumir que la lista de valores a eliminar no tiene duplicados o no? ¿La lista de valores a eliminar es en la gran mayoría de casos grande o no?
¿Alguna de las listas están pre-ordenadas o no? y muchos más factores que pueden ayudar a mejorar la eficiencia para un caso de uso concreto.
Por otro lado hacer un algoritmo "más eficiente" tampoco es algo universal, por ejemplo ¿queremos minimizar a toda costa el tiempo de ejecución o queremos priorizar el mínimo uso de memoria?.
Más que evitar usar ciclos generalmente lo que se debe intentar conseguir es iterar las menos veces posibles sobre las listas y evitar todas las operaciones de comparación que se puedan.
Si queremos maximizar el tiempo de ejecución a costa de usar más memoria, una opción muy obvia suele ser recurrir a tablas hash. Las tablas hash son muy eficientes para realizar búsquedas, la complejidad temporal media de una búsqueda es de O(1), siendo O(N) en el peor de los casos (algoritmo hash realmente nefasto con gran numero de colisiones).
Por ejemplo, si creamos creamos un diccionario a partir de la lista de items a eliminar de la forma:
{item_a_eliminar: veces_que_ese_item_aparece}
podemos iterar una sola vez sobre la lista objetivo e ir buscando cada item en el diccionario para ver si se debe eliminar o no.
Por otro lado, eliminar un item de un array (dado que son elementos contiguos en memoria) tiene un coste también, principalmente porque es necesario desplazar los items siguientes al eliminado para "rellenar el hueco dejado".
A esto hay que sumar que cuando copiamos una lista en Python (con lista[::]
o copy()
por ejemplo) no copiamos sus items. Las lista en realidad contiene referencias a los objetos en memoria (a grandes rasgos). Esto hace que en muchas situaciones salga más "barato" crear una nueva lista que eliminar items in-place, especialmente si vamos a eliminar muchos.
Siguiendo con una posible solución basada en diccionarios, podríamos hacer algo como:
from collections import Counter
from typing import Iterator
def removed_from_list(target: list, values: list) -> Iterator[list]:
target_iter = iter(target)
if not values:
yield from target_iter
return
values_dict = Counter(values)
items_to_delete = sum(values_dict.values())
for item in target_iter:
if values_dict.get(item):
values_dict[item] -= 1
if (items_to_delete := items_to_delete - 1) == 0:
yield from target_iter
else:
yield item
La función es en realidad un generador, si queremos una lista de salida basta con resultado = list(removed_from_list(lista, valores))
.
Otra diferencia con tu ejemplo es que si algún item a eliminar no está en la lista no genera ninguna excepción, simplemente se ignora.
Téngase en cuenta que es solo un ejemplo rápido, puede admitir optimizaciones o no ser una buena opción para casos concretos. Por ejemplo, si se pudiera asumir que no existen valores repetidos en la lista de items a eliminar podemos usar un conjunto en vez de un diccionario y simplificar todo aún más.
Si jugamos un poco con timeit:
%%timeit
values = list(range(100000))
del_values = values[:50000]
for i in del_values:
values.remove(i)
541 ms ± 4.15 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
values = list(range(100000))
del_values = values[:50000]
list(removed_from_list(lista, values))
37.8 ms ± 867 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Este es un caso muy ventajoso en teoría para remove
porque todos los itemns a eliminar son siempre el primero de la lista. Si nos vamos al caso contrario:
%%timeit
values = list(range(100000))
del_values = values[-1:-50001:-1]
for i in del_values:
values.remove(i)
1min 12s ± 184 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
values = list(range(100000))
del_values = values[-1:-50001:-1]
list(removed_from_list(values, del_values))
43.1 ms ± 536 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Como cabe esperar list.remove
escala fatal, pero si ademas los items a eliminar están concentrados al final de la lista la cosa se vuelve realmente mala.
En definitiva, si tu lista de elementos a eliminar tiene frecuentemente un solo item o muy pocos, list.remove
puede ser opción simple y buena. Si tu lista de items a eliminar es relativamente grande list.remove
se puede volver una opción muy pero que muy mala, especialmente cuanto mayor sea la lista objetivo y cuanto mas al final de ésta estén los items a eliminar.
listdir()
. Otros casos pudieran ser resultados de una consulta a una BD, o leer un archivo extremadamente grande. Los generadores son útiles cuando se requiere iterar sobre muchisimos elementos.