Comment supprimer les doublons d'une liste tout en préservant l'ordre ?

Question

Existe-t-il un intégré qui supprime les doublons d'une liste en Python, tout en préservant l'ordre ? Je sais que je peux utiliser un ensemble pour supprimer les doublons, mais cela détruit l'ordre original. Je sais aussi que je peux créer mon propre programme comme ceci :

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(Merci à Détendez-vous pour cela exemple de code .)

Mais j'aimerais profiter d'un idiome intégré ou plus pythique si possible.

Question connexe : 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 ?

Answer 1

Vous avez ici quelques alternatives : http://www.peterbe.com/plog/uniqifiers-benchmark

Le plus rapide :

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

Pourquoi attribuer seen.add a seen_add au lieu de simplement appeler seen.add ? Python est un langage dynamique, et résoudre seen.add chaque itération est plus coûteuse que la résolution d'une variable locale. seen.add pourrait avoir changé entre les itérations, et le runtime n'est pas assez intelligent pour l'exclure. Pour être sûr, il doit vérifier l'objet à chaque fois.

Si vous prévoyez d'utiliser souvent cette fonction sur le même ensemble de données, il serait peut-être préférable d'utiliser un ensemble ordonné : http://code.activestate.com/recipes/528878/

O (1) insertion, suppression et vérification des membres par opération.

(Petite note supplémentaire : seen.add() retourne toujours None donc le or ci-dessus n'est là que comme moyen de tenter une mise à jour de l'ensemble, et non comme partie intégrante du test logique).

Answer 2

Edit 2020

À partir de CPython/PyPy 3.6 (et en tant que garantie du langage dans la version 3.7), le langage simple dict est ordonnée par insertion, et encore plus efficace que la méthode (également implémentée en C) collections.OrderedDict . Ainsi, la solution la plus rapide, et de loin, est aussi la plus simple :

>>> items = [1, 2, 0, 1, 3, 2]
>>> list(dict.fromkeys(items))
[1, 2, 0, 3]

Comme list(set(items)) cela repousse tout le travail vers la couche C (sur CPython), mais puisque dict sont ordonnés par insertion, dict.fromkeys ne perd pas l'ordre. C'est plus lent que list(set(items)) (cela prend 50 à 100 % plus de temps en général), mais beaucoup plus rapide que n'importe quelle autre solution de préservation de l'ordre (il faut environ la moitié du temps de Les piratages impliquant l'utilisation de set s dans une listecomp ).

Edit 2016

En tant que Raymond a souligné dans python 3.5+ où OrderedDict est implémenté en C, l'approche par la compréhension de liste sera plus lente que OrderedDict (sauf si vous avez réellement besoin de la liste à la fin - et encore, seulement si l'entrée est très courte). La meilleure solution pour les versions 3.5+ est donc la suivante OrderedDict .

Important Edit 2015

Comme @abarnert notes, le more_itertools bibliothèque ( pip install more_itertools ) contient un unique_everseen fonction qui est construite pour résoudre ce problème sans aucune illisible ( not seen.add ) mutations dans les compréhensions de listes. C'est également la solution la plus rapide :

>>> from  more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

Une simple importation de bibliothèque et pas de bidouillage. Ceci provient d'une implémentation de la recette itertools unique_everseen ce qui ressemble à :

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

---

En Python 2.7+ le site idiome courant accepté (qui fonctionne mais n'est pas optimisé pour la vitesse, j'utiliserais maintenant unique_everseen ) pour cette utilisation collections.OrderedDict :

Durée d'exécution : O(N)

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

Ça a l'air beaucoup plus joli que :

seen = set()
[x for x in seq if x not in seen and not seen.add(x)]

et n'utilise pas le Mauvais coup :

not seen.add(x)

qui s'appuie sur le fait que set.add est une méthode in-place qui renvoie toujours None donc not None évalue à True .

Notez cependant que la solution du hack est plus rapide en vitesse brute bien qu'elle ait la même complexité d'exécution O(N).

Answer 3

sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

unique ['1', '2', '3', '6', '4', '5']

Answer 4

from itertools import groupby
[ key for key,_ in groupby(sortedList)]

La liste n'a même pas besoin d'être trié la condition suffisante est que les valeurs égales soient regroupées.

Edit : J'ai supposé que "préserver l'ordre" implique que la liste est réellement ordonnée. Si ce n'est pas le cas, alors la solution de MizardX est la bonne.

Modification de la communauté : C'est pourtant la manière la plus élégante de "comprimer des éléments consécutifs en double en un seul élément".

Answer 5

Je pense que si vous voulez maintenir l'ordre,

vous pouvez essayer ceci :

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

OU de la même manière, vous pouvez faire ceci :

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

Vous pouvez également le faire :

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

On peut aussi l'écrire comme ceci :

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2