[Python-es] Duplicados en una lista

[lasizoillo]

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