Suppression des doublons d'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 en supprimer les éléments en double. Si c'était une liste normale et non des listes, je pourrais utiliser set . Mais malheureusement, la liste n'est pas hachable et on ne peut pas faire un ensemble de listes. Seulement des tuples. Je peux donc transformer toutes les listes en tuples, puis utiliser set et revenir aux listes. Mais ce n'est pas rapide.

Comment y parvenir de la manière la plus efficace possible ?

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

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

Je me fiche de l'ordre de conservation.

Note : cette question est similaire mais pas tout à fait ce dont j'ai besoin. J'ai cherché dans SO mais je n'ai pas trouvé de copie exacte.

---

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éthode quadratique) le plus rapide de tous pour les listes courtes. Pour les listes longues, elle est plus rapide que toutes les autres méthodes, sauf la méthode groupby. Cela a-t-il un sens ?

Pour la liste courte (celle du 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 (celle du code dupliquée 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 solutions les plus rapides et les plus puissantes à ce type de problèmes, et est bien Cela vaut la peine de se familiariser intimement avec elle !-)

Modifier Comme je l'ai mentionné dans un commentaire, les efforts d'optimisation normaux se concentrent sur les grandes entrées (l'approche big-O) parce que c'est tellement plus facile que cela offre un bon retour sur les efforts. Mais parfois (essentiellement pour les "goulots d'étranglement tragiquement cruciaux" dans les boucles internes profondes d'un code qui repousse les limites de performance), il peut être nécessaire d'aller beaucoup plus loin dans le détail, en fournissant des distributions de probabilité, en décidant des mesures de performance à optimiser (la limite supérieure ou le 90e centile est peut-être plus important qu'une moyenne ou une médiane, selon les applications), en effectuant des vérifications éventuellement heuristiques 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 minutieuses de la performance "ponctuelle" (code A par rapport au code B pour une entrée spécifique) font partie de ce processus extrêmement coûteux, et le module standard de bibliothèque timeit est utile ici. Cependant, il est plus facile de l'utiliser à l'invite d'un shell. Par exemple, voici un court module pour présenter l'approche générale de ce problème, enregistrez-le sous le nom de 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 le contrôle de sanité (effectué lorsque vous faites simplement python nodup.py ) et la technique de levage de base (rendre les noms globaux constants locaux à chaque fonction pour plus de rapidité) pour mettre les choses sur un pied d'égalité.

Nous pouvons maintenant effectuer des vérifications 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 quadratique a des constantes suffisamment petites pour la rendre intéressante pour les petites listes avec peu de 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 quadratique n'est pas mauvaise, mais celles de sort et groupby sont meilleures. Etc, etc.

Si (comme l'obsession de la performance le suggère) cette opération est au cœur de la boucle interne de votre application qui repousse les limites, il vaut la peine d'essayer le même ensemble de tests sur d'autres échantillons d'entrée représentatifs, en détectant éventuellement une mesure simple qui pourrait heuristiquement vous permettre de choisir l'une ou l'autre approche (mais la mesure doit être rapide, bien sûr).

Il est également intéressant d'envisager de conserver une représentation différente pour les éléments suivants k -- pourquoi faut-il que ce soit 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 que c'est le goulot d'étranglement des performances du programme, conserver un ensemble de tuples en permanence et n'en tirer une liste de listes que si et quand cela est nécessaire, pourrait être plus rapide dans l'ensemble, par exemple.

Answer 2

En le faisant manuellement, en créant une nouvelle k et ajouter les entrées non trouvées jusqu'à présent :

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

C'est simple à comprendre, et vous conservez l'ordre de la première occurrence de chaque élément si cela s'avère utile, mais je suppose que la complexité est quadratique puisque vous cherchez dans l'ensemble de new_k pour chaque élément.

Answer 3

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

Je ne sais pas si c'est nécessairement plus rapide, mais vous n'avez pas besoin d'utiliser des tuples et des ensembles.

Answer 4

Liste de 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 5

Même votre "longue" liste est plutôt courte. De plus, les avez-vous choisis pour qu'ils correspondent aux données réelles ? Les performances varient en fonction de ce à quoi ressemblent réellement ces données. Par exemple, vous avez une liste courte répétée à l'infini pour obtenir une liste plus longue. Cela signifie que la solution quadratique est linéaire dans vos repères, mais pas dans la réalité.

Pour les listes réellement grandes, le code set est votre meilleure option - il est linéaire (bien que gourmand en espace). Les méthodes sort et groupby sont O(n log n) et la méthode loop in est évidemment quadratique, vous savez donc comment elles évoluent lorsque n devient très grand. Si c'est la taille réelle des données que vous analysez, alors qui s'en soucie ? C'est minuscule.

Incidemment, je constate une accélération notable si je ne forme pas de 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)

La véritable 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 ?