[Python-es] Duplicados en una lista

[lasizoillo]

El día 19 de octubre de 2010 23:48, tny <a.porrua en gmail.com> escribió:
> El mar, 19-10-2010 a las 16:03 +0200, lasizoillo escribió:
>> 2010/10/19 Arnau Sanchez <pyarnau en gmail.com>:
>> > On Tue, 19 Oct 2010 13:50:37 +0200 tny wrote:
>> >
>> >> uno_de_cada_en_orden_original = [a[i] for i in range(len(a)) if a[i] not
>> >> in a[:i]]
>> >
>> > Uf, eso tiene pinta de O(n^2) en tiempo cuando unique puede (debería) ser O(n).
>>
>> Un unique sobre una colección ordenada debería ser O(n) porque basta
>> con comparar con el anterior. Si la lista no esta ordenada habría que
>> encontrar si ya hemos leido ese dato antes o no. Si puede hacer esa
>> búsqueda con O(1), seguiría siendo O(n), pero lo más probable es que
>> acabara siendo O(n log n). En su caso tiene pinta de O(n^2) u O(n^2 /
>> 2) si nos ponemos finos, cosa que es mejorable, pero tiene la ventaja
>> de no necesitar otra estructura adicional para hacer ese loopback. Es
>> más lento, pero requiere menos memoria.
>>
>> Resumiendo, me parece ideal para los casos en los que se quiera quitar
>> duplicados de una lista manteniendo el orden (desordenado) original de
>> esta y los requisitos de espacio/memoria sean necesarios. Para el
>> resto de los casos hay soluciones mejores ;-)
>>
>> Un saludo:
>>
>> Javi
>> _______________________________________________
>> Python-es mailing list
>> Python-es en python.org
>> http://mail.python.org/mailman/listinfo/python-es
>> FAQ: http://python-es-faq.wikidot.com/
>
> ¿Cual de los siguientes modos sería más rápido?

La respuesta ideal es ejecutarlos y medir el tiempo. Una forma cómoda
de hacerlo es usar la consola ipython y comando timeit. Te puede pasar
que una implementación más rápida en una versión de python sea más
lenta en otra.

El primero sería seguramente más lento porque la recursividad penaliza
bastante. Aparte de que podrías llegar al limite de llamadas
recursivas facilmente:
http://docs.python.org/library/sys.html?highlight=setrecursionlimit#sys.getrecursionlimit

> ¿Cual sería su complejidad?

Cuando solo cambies la implementación, sin cambiar el algoritmo que se
implementa, no cambia el orden de complejidad. Así que del segundo
deberías ya saber su complejidad.

Otro consejo practico de alguien sin estudios: Hasta coger práctica
calculando el orden de ejecución, puedes medirlo empíricamente.
Implementas, das distintos valores de n midiendo tiempos de ejecución
y pintas sobre una gráfica.

> ¿Beneficiaría en algo al rendimiento del primer algoritmo forkear cada
> mitad, y cuando estén calculadas unirlas?

Los procesos son útiles a veces.

Ventajas:
 * El código se puede ejecutar en varios procesadores

Desventajas:
 * Añaden complejidad de muchas formas:
   * Algorítmica. Separas el proceso en dos partes (manteniendo
complejidad algorítmica en cada una de ellas en el mejor de los casos)
y luego añades complejidad al mezclar los resultados.
   * De implementación. Sincronización de memoria compartida,
serializar datos a través de pipes, ...
 * La complejidad añadida afecta al rendimiento. Un código que se
ejecute en 8 cores nunca va a llegar a ir 8 veces más rápido que
ejecutándose en uno solo. Si el cuello de botella no es la cpu, puedes
obtener un código más lento.

>
> def unicos_manteniendo_orden(lista):
>    size = len(lista)
>    if size == 1:
>        return lista
>    primera_mitad = unicos_manteniendo_orden(lista[:size/2])
>    segunda_mitad = unicos_manteniendo_orden(lista[size/2:])
>    return primera_mitad + [x for x in segunda_mitad if x not in
> primera_mitad]
>
> def unicos_manteniendo_orden_2(lista):
>    resultado = []
>    for elemento in lista:
>        if elemento in resultado:
>            continue
>        resultado.append(elemento)
>    return resultado
>
>

Si te interesa mucho el rendimiento podrías hacer cosas como quitarle
el punto del append en la segunda implementación:
http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Avoidingdots...

Personalmente no suelo hacerlas. Lo optimo en la implementación del
intérprete de hoy puede ser peor en la implementación del intérprete o
JIT de python de mañana. Pero lo que es seguro es que tu código va a
perder en legibilidad y mantenibilidad. Y python sin legibilidad ya no
es python ;-)

Espero que este post de agüelo cebolleta te resulte de utilidad ;-)

Un saludo:

Javi