Eliminar duplicados de una lista de listas

Tengo una lista de listas en Python:

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] 

Y quiero eliminar elementos duplicados de ella. Era si era una lista normal no de listas que podría utilizar. Pero desafortunadamente esa lista no es hashable y no puede hacer un conjunto de listas. Solo de tuplas. Así que puedo convertir todas las listas en tuplas y luego usar set y volver a las listas. Pero esto no es rápido.

¿Cómo se puede hacer esto de la manera más eficiente?

El resultado de la lista anterior debe ser:

 k = [[5, 6, 2], [1, 2], [3], [4]] 

No me importa preservar el orden.

Nota: esta pregunta es similar pero no es exactamente lo que necesito. Busqué SO pero no encontré el duplicado exacto.


Benchmarking:

 import itertools, time class Timer(object): def __init__(self, name=None): self.name = name def __enter__(self): self.tstart = time.time() def __exit__(self, type, value, traceback): if self.name: print '[%s]' % self.name, print 'Elapsed: %s' % (time.time() - self.tstart) k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5 N = 100000 print len(k) with Timer('set'): for i in xrange(N): kt = [tuple(i) for i in k] skt = set(kt) kk = [list(i) for i in skt] with Timer('sort'): for i in xrange(N): ks = sorted(k) dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]] with Timer('groupby'): for i in xrange(N): k = sorted(k) dedup = list(k for k, _ in itertools.groupby(k)) with Timer('loop in'): for i in xrange(N): new_k = [] for elem in k: if elem not in new_k: new_k.append(elem) 

“loop in” (método cuadrático) más rápido de todos para listas cortas. Para las listas largas es más rápido que todos, excepto el método groupby. ¿Esto tiene sentido?

Para la lista corta (la que está en el código), 100000 iteraciones:

 [set] Elapsed: 1.3900001049 [sort] Elapsed: 0.891000032425 [groupby] Elapsed: 0.780999898911 [loop in] Elapsed: 0.578000068665 

Para una lista más larga (la del código duplicado 5 veces):

 [set] Elapsed: 3.68700003624 [sort] Elapsed: 3.43799996376 [groupby] Elapsed: 1.03099989891 [loop in] Elapsed: 1.85900020599 

 >>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] >>> import itertools >>> k.sort() >>> list(k for k,_ in itertools.groupby(k)) [[1, 2], [3], [4], [5, 6, 2]] 

itertools menudo ofrece las soluciones más rápidas y poderosas para este tipo de problemas, y vale la pena familiarizarse con él.

Edición : como menciono en un comentario, los esfuerzos normales de optimización se centran en grandes insumos (el enfoque de la O grande) porque es mucho más fácil que ofrece buenos retornos en los esfuerzos. Pero a veces (para los “cuellos de botella trágicamente cruciales” en los bucles internos profundos del código que están empujando los límites de los límites de rendimiento), es posible que deba entrar en mucho más detalle, proporcionar distribuciones de probabilidad, decidir qué medidas de rendimiento optimizar (tal vez el límite superior o el percentil 90 es más importante que el promedio o la mediana, dependiendo de las aplicaciones de cada uno), al realizar verificaciones posiblemente heurísticas al comienzo para seleccionar diferentes algoritmos según las características de los datos de entrada, y así sucesivamente.

Las medidas cuidadosas del rendimiento “puntual” (código A frente a código B para una entrada específica) son parte de este proceso extremadamente costoso, y el módulo de biblioteca estándar timeit ayuda aquí. Sin embargo, es más fácil de usar en un indicador de shell. Por ejemplo, aquí hay un módulo corto para mostrar el enfoque general de este problema, guárdelo como nodup.py :

 import itertools k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] def doset(k, map=map, list=list, set=set, tuple=tuple): return map(list, set(map(tuple, k))) def dosort(k, sorted=sorted, xrange=xrange, len=len): ks = sorted(k) return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]] def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list): ks = sorted(k) return [i for i, _ in itertools.groupby(ks)] def donewk(k): newk = [] for i in k: if i not in newk: newk.append(i) return newk # sanity check that all functions compute the same result and don't alter k if __name__ == '__main__': savek = list(k) for f in doset, dosort, dogroupby, donewk: resk = f(k) assert k == savek print '%10s %s' % (f.__name__, sorted(resk)) 

Tenga en cuenta la comprobación de cordura (realizada cuando acaba de hacer python nodup.py ) y la técnica básica de levantamiento (haga que los nombres globales constantes sean locales para cada función) para poner las cosas en pie de igualdad.

Ahora podemos ejecutar comprobaciones en la pequeña lista de ejemplos:

 $ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)' 100000 loops, best of 3: 11.7 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)' 100000 loops, best of 3: 9.68 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)' 100000 loops, best of 3: 8.74 usec per loop $ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)' 100000 loops, best of 3: 4.44 usec per loop 

confirmando que el enfoque cuadrático tiene constantes suficientemente pequeñas para hacerlo atractivo para listas pequeñas con pocos valores duplicados. Con una lista corta sin duplicados:

 $ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])' 10000 loops, best of 3: 25.4 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])' 10000 loops, best of 3: 23.7 usec per loop $ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])' 10000 loops, best of 3: 31.3 usec per loop $ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])' 10000 loops, best of 3: 25 usec per loop 

El enfoque cuadrático no es malo, pero los de tipo y de grupo son mejores. Etcétera etcétera.

Si (como lo sugiere la obsesión con el rendimiento) esta operación se encuentra en un bucle interno central de su aplicación de empujar los límites, vale la pena probar el mismo conjunto de pruebas en otras muestras de entrada representativas, posiblemente detectando alguna medida simple que podría permitirle heurísticamente Elija uno u otro enfoque (pero la medida debe ser rápida, por supuesto).

También vale la pena considerar mantener una representación diferente para k : ¿por qué tiene que ser una lista de listas en lugar de un conjunto de tuplas en primer lugar? Si la tarea de eliminación de duplicados es frecuente, y la creación de perfiles muestra que se trata del cuello de botella del rendimiento del progtwig, mantener un conjunto de tuplas todo el tiempo y obtener una lista de las listas solo si y donde sea necesario, podría ser más rápido en general, por ejemplo.

 >>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] >>> k = sorted(k) >>> k [[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]] >>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]] >>> dedup [[1, 2], [3], [4], [5, 6, 2]] 

No sé si es necesariamente más rápido, pero no tienes que usar tuplas y conjuntos.

Haciéndolo manualmente, creando una nueva lista k y agregando entradas no encontradas hasta ahora:

 k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] new_k = [] for elem in k: if elem not in new_k: new_k.append(elem) k = new_k print k # prints [[1, 2], [4], [5, 6, 2], [3]] 

Es fácil de comprender y preservar el orden de la primera aparición de cada elemento debería ser útil, pero supongo que es de complejidad cuadrática a medida que busca la totalidad de new_k para cada elemento.

Incluso su lista “larga” es bastante corta. Además, ¿los eligió para coincidir con los datos reales? El rendimiento variará con la apariencia de estos datos. Por ejemplo, tiene una lista corta repetida una y otra vez para hacer una lista más larga. Esto significa que la solución cuadrática es lineal en sus puntos de referencia, pero no en la realidad.

Para listas realmente grandes, el código establecido es su mejor apuesta: es lineal (aunque le falta espacio). Los métodos de clasificación y agrupación son O (n log n) y el método de bucle es obviamente cuadrático, por lo que se sabe cómo se escalarán a medida que n sea realmente grande. Si este es el tamaño real de los datos que está analizando, ¿a quién le importa? Es minúsculo

Por cierto, estoy viendo una notable aceleración si no formo una lista intermedia para hacer el conjunto, es decir, si reemplazo

 kt = [tuple(i) for i in k] skt = set(kt) 

con

 skt = set(tuple(i) for i in k) 

La solución real puede depender de más información: ¿Está seguro de que una lista de listas es realmente la representación que necesita?

La lista de tuplas y {} se pueden usar para eliminar duplicados

 >>> [list(tupl) for tupl in {tuple(item) for item in k }] [[1, 2], [5, 6, 2], [3], [4]] >>> 

Todas las soluciones relacionadas con los set para este problema hasta ahora requieren crear un set completo antes de la iteración.

Es posible hacer esto perezoso y, al mismo tiempo, mantener el orden, iterando la lista de listas y agregándolas a un conjunto “visto”. Luego, solo genere una lista si no se encuentra en este set rastreadores.

Esta receta unique_everseen está disponible en los documentos de itertools . También está disponible en la biblioteca de toolz terceros:

 from toolz import unique k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] # lazy iterator res = map(list, unique(map(tuple, k))) print(list(res)) [[1, 2], [4], [5, 6, 2], [3]] 

Tenga en cuenta que la conversión de la tuple es necesaria porque las listas no son hashable.

Esto debería funcionar.

 k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] k_cleaned = [] for ele in k: if set(ele) not in [set(x) for x in k_cleaned]: k_cleaned.append(ele) print(k_cleaned) # output: [[1, 2], [4], [5, 6, 2], [3]] 

Otra solución probablemente más genérica y más simple es crear un diccionario codificado por la versión de cadena de los objetos y obtener los valores () al final:

 >>> dict([(unicode(a),a) for a in [["A", "A"], ["A", "A"], ["A", "B"]]]).values() [['A', 'B'], ['A', 'A']] 

El problema es que esto solo funciona para los objetos cuya representación de cadena es una clave única suficientemente buena (lo que es cierto para la mayoría de los objetos nativos).

Cree un diccionario con la tupla como clave e imprima las claves.

  • Crear diccionario con tupla como clave e índice como valor
  • Imprimir lista de claves del diccionario

 k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]] dict_tuple = {tuple(item): index for index, item in enumerate(k)} print [list(itm) for itm in dict_tuple.keys()] # prints [[1, 2], [5, 6, 2], [3], [4]] 

Curiosamente, las respuestas anteriores eliminan los ‘duplicados’, pero ¿qué sucede si también quiero eliminar el valor duplicado? ¡Lo siguiente debería ser útil y no crea un nuevo objeto en la memoria!

 def dictRemoveDuplicates(self): a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']] print(a) temp = 0 position = -1 for pageNo, item in a: position+=1 if pageNo != temp: temp = pageNo continue else: a[position] = 0 a[position - 1] = 0 a = [x for x in a if x != 0] print(a) 

y la o / p es:

 [[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']] [[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]