todos - Python: eliminar duplicados de una lista de listas

python eliminar duplicados de lista (8)

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 fuera una lista normal no de listas que podría usar set . 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 debería ser:

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

No me importa mantener el orden.

Nota: esta pregunta es similar pero no 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) el 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 una lista corta (la del 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 duplicada 5 veces):

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

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

crear diccionario con tupla como clave e índice como valor
imprimir la lista de teclas 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]]

Hacerlo manualmente, crear una nueva lista k y agregar entradas que no se encuentran hasta el momento:

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 entender y conserva el orden de la primera aparición de cada elemento si eso es útil, pero supongo que es de complejidad cuadrática ya que está buscando la totalidad de new_k para cada elemento.

Incluso su lista "larga" es bastante corta. Además, ¿los eligió para que coincida con los datos reales? El rendimiento variará con el aspecto real de estos datos. Por ejemplo, tiene una lista breve 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 las listas realmente grandes, el código establecido es su mejor apuesta: es lineal (aunque tenga hambre de espacio). Los métodos sort y groupby son O (n log n) y el método loop in es obviamente cuadrático, por lo que se sabe cómo se escalarán cuando n se vuelve realmente grande. Si este es el tamaño real de los datos que está analizando, ¿a quién le importa? Es muy pequeño

A propósito, estoy viendo una aceleración notable si no formo una lista intermedia para hacer el set, 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 puede usar para eliminar duplicados

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

Otra solución probablemente más genérica y 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'']]

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

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

Es posible hacer que esto sea flojo y, al mismo tiempo, conservar el orden, al iterar la lista de listas y agregarlas a un conjunto "visto". A continuación, solo obtenga una lista si no se encuentra en este set seguimiento.

Esta receta unique_everseen está disponible en los docs 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 tuple es necesaria porque las listas no son manejables.

>>> 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 esto! -)

Edición : como menciono en un comentario, los esfuerzos normales de optimización se centran en grandes entradas (el enfoque de la gran O) porque es mucho más fácil que ofrezca buenos rendimientos en los esfuerzos. Pero a veces (esencialmente para "cuellos de botella trágicamente cruciales" en profundos bucles interiores de código que están superando los límites de rendimiento) es posible que deba entrar en más detalles, 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 un promedio o mediana, según las aplicaciones), realizar comprobaciones posiblemente heurísticas al inicio para elegir diferentes algoritmos en función de las características de los datos de entrada, y así sucesivamente.

Las mediciones cuidadosas del rendimiento del "punto" (código A frente al código B para una entrada específica) son parte de este proceso extremadamente costoso, y el tiempo timeit módulo de biblioteca estándar ayuda aquí. Sin embargo, es más fácil usarlo en un intérprete de comandos de shell. Por ejemplo, aquí hay un breve módulo para mostrar el enfoque general para 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 elevación (hacer nombres globales constantes locales para cada función de velocidad) para poner las cosas en igualdad de condiciones.

Ahora podemos ejecutar verificaciones en la lista de ejemplos minúsculos:

$ 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 lo 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 el género y el grupo son mejores. Etcétera etcétera.

Si (como sugiere la obsesión por el rendimiento) esta operación se encuentra en un bucle interno central de su aplicación de límites, vale la pena intentar el mismo conjunto de pruebas en otras muestras de entrada representativas, posiblemente detectando alguna medida simple que podría permitirle heurísticamente elija uno o el 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 duplicada es frecuente y el perfil muestra que es el cuello de botella de rendimiento del programa, mantener un conjunto de tuplas todo el tiempo y obtener una lista de ellas 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 necesariamente es más rápido, pero no es necesario usar tuplas y conjuntos.