Python: la eliminación de duplicados de una lista de listas

Question

que tienen una lista de listas en Python:

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

Y quieren eliminar elementos duplicados de la misma. 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 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 acerca de preservar el orden.

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

---

Análisis comparativo:

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ática) más rápido de todos para las listas cortas. Para las listas largas, es más rápido que todos, excepto el método groupby. ¿Esto tiene sentido?

Para lista corta (el que en el código), 100.000 iteraciones:

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

Para una lista más larga (el uno en el código duplicado 5 veces):

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

Answer 1

>>> 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 potentes a este tipo de problemas, y es así pena conseguir íntimamente familiarizados con -)

Editar: como menciono en un comentario, los esfuerzos normales de optimización se centran en grandes insumos (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 "puntual" (código A frente al 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 usarlo en un intérprete de comandos de shell. Por ejemplo, he aquí una breve módulo de mostrar el enfoque general para este problema, guardarlo 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)) 

Nota la comprobación de validez (realizada cuando se acaba de hacer python nodup.py) y la técnica básica de elevación (hacer constantes nombres globales local para cada función por velocidad) para poner las cosas en igualdad de condiciones.

Ahora podemos ejecutar comprobaciones sobre la pequeña lista de ejemplo:

$ 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ática tiene constantes pequeñas suficiente para que sea atractivo para los pequeños listas con pocos valores duplicados. Con una breve lista 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ática no es malo, pero el tipo y las GroupBy son mejores. Etc, etc.

Si (como lo sugiere la obsesión por el rendimiento) esta operación se encuentra en un bucle interior central de su aplicación de empujar los 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 ayudar heurísticamente a elegir 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 vez 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.

Answer 2

>>> 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]] 

I no sé si necesariamente es más rápido, pero no es necesario utilizarlo para tuplas y conjuntos.

Answer 3

hacerlo manualmente, creando una nueva lista k y la adición de las entradas no se ha encontrado 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]] 

simple de comprender, y preservar el orden de la primera aparición de cada elemento debe que sea útil, pero Supongo que es de complejidad cuadrática ya que estás buscando el total de new_k para cada elemento.

Answer 4

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 listas realmente grandes, el código configurado es su mejor apuesta: es lineal (aunque con mucho 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

Por cierto, estoy viendo una aceleración notable si yo 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) 

El 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?

Answer 5

Otra solución probablemente más genérico y más simple es crear un diccionario introducido 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 sólo funciona para los objetos cuya representación de cadena es una clave única suficientemente buena (que es verdadera para la mayoría de los objetos nativos).

Answer 6

Lista de tupla y {} se puede utilizar para eliminar duplicados

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

Answer 7

Crear un diccionario con tupla como la clave, e imprimir las llaves.

• crear diccionario con tupla como clave y el índice como valor
• lista de impresión de claves de 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]]