[Python-es] Duplicados en una lista

[tny]

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?
¿Cual sería su complejidad?
¿Beneficiaría en algo al rendimiento del primer algoritmo forkear cada
mitad, y cuando estén calculadas unirlas?
Gracias.

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