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. ¿Era una lista normal, no listas que pudiera usar set? Pero, lamentablemente, esa lista no se puede usar con hash y no se puede crear un conjunto de listas. Sólo de tuplas. Entonces puedo convertir todas las listas en tuplas, 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 es exactamente lo que necesito. Busqué SO pero no encontré un duplicado exacto.
Evaluación comparativa:
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)
"bucle" (método cuadrático) más rápido de todos para listas cortas. Para listas largas, es más rápido que todos, excepto el método groupby. ¿Esto tiene sentido?
Para una 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 duplicada 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]]
itertoolsa menudo ofrece las soluciones más rápidas y poderosas para este tipo de problemas, ¡y vale la pena familiarizarse con ellas!-)
Editar : como menciono en un comentario, los esfuerzos de optimización normales se centran en grandes entradas (el enfoque de gran O) porque es mucho más fácil y ofrece buenos retornos de los esfuerzos. Pero a veces (esencialmente en el caso de "cuellos de botella trágicamente cruciales" en bucles internos profundos de código que superan los límites de rendimiento) es posible que sea necesario entrar en muchos más detalles, proporcionando distribuciones de probabilidad, decidiendo qué medidas de rendimiento optimizar (tal vez el límite superior o el percentil 90 es más importante que un promedio o mediana, dependiendo de las aplicaciones de cada uno), realizar comprobaciones posiblemente heurísticas al principio para elegir diferentes algoritmos dependiendo de las características de los datos de entrada, etc.
Las mediciones cuidadosas del rendimiento "puntual" (código A versus código B para una entrada específica) son parte de este proceso extremadamente costoso, y el módulo de biblioteca estándar timeitayuda aquí. Sin embargo, es más fácil usarlo en el símbolo del shell. Por ejemplo, aquí hay un módulo breve 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 verificación de cordura (que se realiza cuando simplemente lo hace python nodup.py) y la técnica de elevación básica (hacer que los nombres globales constantes sean locales para cada función para la velocidad) para poner las cosas en pie de igualdad.
Ahora podemos ejecutar comprobaciones en 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ático tiene constantes lo suficientemente pequeñas como para hacerlo atractivo para listas pequeñas 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ático no es malo, pero los de clasificación y de 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 que traspasa 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 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 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 es un cuello de botella en el rendimiento del programa, mantener un conjunto de tuplas todo el tiempo y obtener una lista de listas solo cuando sea necesario, podría ser más rápido en general, por ejemplo.
Haciéndolo manualmente, creando una nueva klista y agregando entradas no encontradas 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 comprender y conserva el orden de la primera aparición de cada elemento en caso de que sea útil, pero supongo que tiene una complejidad cuadrática ya que busca cada new_kelemento en su totalidad.
>>> 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 es necesario utilizar tuplas y conjuntos.
