1

Para explicarme mejor, ya que el título es confuso, imagínate que tienes una lista con todos los valores [x, y, z], y ademas tienes otra lista de los valores que quieres eliminar [x, z], estos valores normalmente números.

Además, solo se tiene que eliminar un valor en la lista principal por cada uno que haya en la otra lista, por ejemplo, si tienes una lista [x, y, z, x], y tienes que eliminar los elementos [x, y], te daría [z, x].

Intento que sea un código MUY eficiente, evitando usar bucles, siempre que se pueda, ya que la lista puede tener hasta una gran elementos.

# Así sería con bucle más o menos según yo

values = [3, 6, 2, 9, 1, 3]
del_values = [3, 2]
for i in del_values:
  values.remove(i)

print(values)

Quiero saber cual sería la manera más eficiente (si la hay) de hacer esto, no gastando muchos recursos.

2
  • Para hacer esto más eficiente habría que saber un poco más del contexto. Por ejemplo, ¿la lista se obtiene de listar un directorio con millones de archivos? Si fuera ese ejemplo, conviene usar un método generador en vez de una lista a secas con 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.
    – aeportugal
    Commented el 10 mar. a las 21:26
  • La forma más eficiente suele ser con list comprehension. De todos modos, Python es un lenguaje interpretado. Si buscas rendimiento piensa en un lenguaje de bajo nivel.
    – Mateo
    Commented el 11 mar. a las 15:49

1 respuesta 1

4

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.

Tu Respuesta

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

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