En Python, quel est l'algorithme le plus rapide pour supprimer les doublons d'une liste afin que tous les éléments soient uniques * tout en préservant l'ordre *?

Question

Par exemple:

 >>> x = [1, 1, 2, 'a', 'a', 3]
>>> unique(x)
[1, 2, 'a', 3]
 

Supposer que les éléments de la liste sont hashable.

Précision: le résultat devrait conserver le premier duplicata dans la liste. Par exemple, [1, 2, 3, 2, 3, 1] devient [1, 2, 3].

Answer 1

def unique(items):
    found = set([])
    keep = []

    for item in items:
        if item not in found:
            found.add(item)
            keep.append(item)

    return keep

print unique([1, 1, 2, 'a', 'a', 3])

Answer 2

À l'aide de:

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]

Et en utilisant le module timeit:

$ python -m timeit -s 'import uniquetest' 'uniquetest.etchasketch(uniquetest.lst)'

(et ainsi de suite pour les autres fonctions, j'ai nommé après leurs affiches), j'ai les résultats suivants (sur ma première génération de processeurs Intel MacBook Pro):

• Allen: 14.6 usec par boucle [1]
• Terhorst: 26.6 usec par boucle
• Tarle: 44.7 usec par boucle
• ctcherry: 44.8 usec par boucle
• Etchasketch 1 (court terme): 64.6 usec par boucle
• Schinckel: 65 µs par boucle
• Etchasketch 2: 71.6 usec par boucle
• Peu: 89.4 usec par boucle
• Tyler: 179 usec par boucle

[1] il est à Noter que Allen modifie la liste en place – je crois que cela a faussé le temps, en ce que le module timeit exécute le code 100000 fois et 99999 sont avec la dupe-moins de la liste.

Résumé: Straight-forward de la mise en œuvre avec des sets gagne plus de confusion one-liners :-)

Answer 3

Voici la solution la plus rapide à ce jour (pour l’entrée suivante):

 def del_dups(seq):
    seen = {}
    pos = 0
    for item in seq:
        if item not in seen:
            seen[item] = True
            seq[pos] = item
            pos += 1
    del seq[pos:]

lst = [8, 8, 9, 9, 7, 15, 15, 2, 20, 13, 2, 24, 6, 11, 7, 12, 4, 10, 18, 
       13, 23, 11, 3, 11, 12, 10, 4, 5, 4, 22, 6, 3, 19, 14, 21, 11, 1, 
       5, 14, 8, 0, 1, 16, 5, 10, 13, 17, 1, 16, 17, 12, 6, 10, 0, 3, 9, 
       9, 3, 7, 7, 6, 6, 7, 5, 14, 18, 12, 19, 2, 8, 9, 0, 8, 4, 5]
del_dups(lst)
print(lst)
# -> [8, 9, 7, 15, 2, 20, 13, 24, 6, 11, 12, 4, 10, 18, 23, 3, 5, 22, 19, 14, 
#     21, 1, 0, 16, 17]
 

La recherche par dictionnaire est légèrement plus rapide que celle de l'ensemble dans Python 3.

Answer 4

Ce qui sera le plus rapide dépend du pourcentage de doublons dans votre liste. Si ce sont presque tous des doublons, avec quelques éléments uniques, la création d'une nouvelle liste sera probablement plus rapide. S'il s'agit principalement d'éléments uniques, les supprimer de la liste d'origine (ou d'une copie) sera plus rapide.

En voici une pour modifier la liste en place:

 def unique(items):
  seen = set()
  for i in xrange(len(items)-1, -1, -1):
    it = items[i]
    if it in seen:
      del items[i]
    else:
      seen.add(it)
 

Une itération en arrière sur les index garantit que la suppression d'éléments n'affecte pas l'itération.

Answer 5

C'est la méthode sur place la plus rapide que j'ai trouvée (en supposant une grande proportion de doublons):

 def unique(l):
    s = set(); n = 0
    for x in l:
        if x not in s: s.add(x); l[n] = x; n += 1
    del l[n:]
 

C'est 10% plus rapide que l'implémentation d'Allen, sur laquelle elle est basée (timed with timeit.repeat, JIT compilé par psyco). Il conserve la première instance de tout doublon.

Repton-infinity: Je serais intéressé si vous pouviez confirmer mes timings.