Python: la suppression des doublons dans une liste de listes

Question

j'ai une liste de listes en Python:

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

Et je veux supprimer les doublons de lui. Était-ce si c'était une liste normale de listes que je pouvais utiliser set. Mais malheureux cette liste n'est pas hashable et ne peut pas faire un ensemble de listes. Seulement des tuples. Je peux donc transformer toutes les listes en tuples puis utiliser set et retourner aux listes. Mais ce n'est pas rapide.

Comment cela peut-il être fait de la manière la plus efficace?

Le résultat de la liste ci-dessus doit être:

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

Je ne me soucie pas de préserver l'ordre.

Note: this question est similaire mais pas tout à fait ce dont j'ai besoin. Cherché SO mais n'a pas trouvé le double exact.

---

Analyse comparative:

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) 

"boucle" (méthode quadratique) le plus rapide de toutes les listes courtes. Pour les longues listes, c'est plus rapide que tout le monde sauf la méthode groupby. Est-ce que ça a du sens?

Pour la liste courte (celle dans le code), 100000 itérations:

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

Pour une liste plus longue (une dans le code dupliqués 5 fois):

[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 offre souvent les plus rapides et les solutions les plus efficaces pour ce genre de problèmes, et est bien la peine de se connaît très bien -)

Modifier: comme je le mentionne dans un commentaire, Les efforts d'optimisation normaux sont axés sur les grandes intrants (l'approche big-O) car il est tellement plus facile qu'il offre de bons retours sur les efforts. Mais parfois (essentiellement pour les «goulots d'étranglement cruciaux» dans les boucles internes profondes du code qui repoussent les limites de performance), il faudra peut-être aller plus loin en fournissant des distributions de probabilités, en déterminant les mesures de performance à optimiser. le 90e centile est plus important qu'une moyenne ou une médiane, selon ses applications), effectuant des vérifications heuristiques possibles au début pour choisir différents algorithmes en fonction des caractéristiques des données d'entrée, et ainsi de suite.

Des mesures soigneuses des performances "ponctuelles" (code A contre code B pour une entrée spécifique) font partie de ce processus extrêmement coûteux, et le module de bibliothèque standard timeit aide ici. Cependant, il est plus facile de l'utiliser à l'invite du shell. Par exemple, voici un court module pour mettre en valeur l'approche générale de ce problème, enregistrez comme 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)) 

Notez la vérification de la santé mentale (effectué lorsque vous faites juste python nodup.py) et la technique de levage de base (faire des noms globaux constants local à chaque fonction pour la vitesse) pour mettre les choses sur un pied d'égalité.

Maintenant, nous pouvons effectuer des contrôles sur la petite liste d'exemples:

$ 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 

confirmant que l'approche du second degré a des constantes de petite assez pour le rendre attrayant pour les petites listes avec quelques valeurs dupliquées. Avec une courte liste sans doublons:

$ 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 

l'approche du second degré est pas mal, mais le genre et les GroupBy sont mieux. Si (comme l'obsession de la performance le suggère) cette opération est à la base d'une boucle interne de votre application push-the-boundaries, il vaut la peine d'essayer le même ensemble de tests sur d'autres échantillons représentatifs, en détectant éventuellement une mesure simple qui pourrait heuristiquement vous laisser choisir l'une ou l'autre approche (mais la mesure doit être rapide, bien sûr).

Cela vaut également la peine d'envisager de conserver une représentation différente pour k - pourquoi doit-il être une liste de listes plutôt qu'un ensemble de tuples en premier lieu? Si la tâche de suppression des doublons est fréquente et que le profilage montre qu'il s'agit du goulot d'étranglement des performances du programme, conserver un ensemble de tuples tout le temps et obtenir une liste de listes uniquement si et si nécessaire, peut être globalement plus rapide, par exemple.

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 Je ne sais pas si c'est forcément plus rapide, mais vous n'avez pas besoin d'utiliser des tuples et des sets.

Answer 3

le faire manuellement, la création d'une nouvelle liste k et l'ajout d'entrées non trouvé à ce jour:

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 à comprendre, et vous préservez l'ordre de la première occurrence de chaque élément devrait-il être utile, mais Je suppose que c'est complexe dans la complexité que vous recherchez l'ensemble de new_k pour chaque élément.

Answer 4

Même votre "longue" liste est assez courte. En outre, les avez-vous choisis pour correspondre aux données réelles? Les performances varient en fonction de ce à quoi ressemblent ces données. Par exemple, vous avez une liste courte répétée à plusieurs reprises pour faire une liste plus longue. Cela signifie que la solution quadratique est linéaire dans vos benchmarks, mais pas dans la réalité.

Pour les listes réellement grandes, le code de l'ensemble est votre meilleur choix: il est linéaire (bien qu'il ait besoin d'espace). Les méthodes de tri et groupby sont O (n log n) et la méthode de bouclage est évidemment quadratique, vous savez donc comment elles vont évoluer quand n devient vraiment grand. Si c'est la taille réelle des données que vous analysez, alors qui s'en soucie? C'est minuscule.

Soit dit en passant, je vois une remarque si je speedup ne forme pas une liste intermédiaire pour faire l'ensemble, c'est-à-dire si je remplace

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

avec

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

Le La vraie solution peut dépendre de plus d'informations: Êtes-vous sûr qu'une liste de listes est vraiment la représentation dont vous avez besoin?

Answer 5

Une autre solution probablement plus générique et plus simple est de créer un dictionnaire calée par la version chaîne des objets et obtenir les valeurs() à la fin:

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

Le hic est que cela ne fonctionne que pour les objets dont la représentation sous forme de chaîne est une clé unique assez bonne (ce qui est vrai pour la plupart des objets natifs).

Answer 6

Liste des tuple et {} peut être utilisé pour supprimer les doublons

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

Answer 7

Créer un dictionnaire avec tuple comme la clé, et imprimer les clés.

• créer dictionnaire avec tuple comme la clé et l'index en tant que valeur
liste d'impression
• des clés de dictionnaire

---

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