Question Comment supprimer les doublons d'une liste tout en préservant la commande?


Y a-t-il un built-in qui supprime les doublons de la 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 d'origine. Je sais aussi que je peux rouler les miens comme ceci:

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

(Grâce à se détendre pour ça exemple de code.)

Mais j'aimerais me servir d'un idiome intégré ou plus pythonien 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?


603
2018-01-26 15:43


origine


Réponses:


Ici vous avez 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 à seen_add au lieu de simplement appeler seen.add? Python est un langage dynamique, et résolvant seen.add chaque itération est plus coûteuse que la résolution d'une variable locale. seen.add aurait pu changer entre les itérations, et le runtime n'est pas assez intelligent pour l'exclure. Pour jouer en toute sécurité, il doit vérifier l'objet à chaque fois.

Si vous prévoyez d'utiliser beaucoup cette fonction sur le même jeu de données, vous feriez peut-être mieux d'utiliser un ensemble ordonné: http://code.activestate.com/recipes/528878/

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


640
2018-01-26 15:47



Modifier 2016

Comme Raymond souligné, en python 3.5+ où OrderedDict est implémenté en C, l'approche de compréhension de liste sera plus lente que OrderedDict (sauf si vous avez réellement besoin de la liste à la fin - et même alors, seulement si l'entrée est très courte). Donc, la meilleure solution pour 3.5+ est OrderedDict.

Important Modifier 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 aucun illisible (not seen.add) mutations dans les listes de compréhension. C'est aussi 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]

Juste une simple importation de bibliothèque et aucun hacks. Cela vient d'une implémentation de la recette d'itertools unique_everseen 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+ la idiome commun accepté (qui fonctionne mais n'est pas optimisé pour la vitesse, j'utiliserais maintenant unique_everseen) pour cette utilisation collections.OrderedDict:

Runtime: SUR)

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

Cela semble beaucoup plus agréable que:

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

et n'utilise pas le vilain hack:

not seen.add(x)

qui repose sur le fait que set.add est une méthode en place qui revient toujours None alors not None évalue à True.

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


289
2017-10-03 15:47



En Python 2.7, la nouvelle façon de supprimer les doublons d'un itérable tout en le gardant dans l'ordre original est:

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

En Python 3.5, OrderedDict a une implémentation C. Mes minutages montrent que c'est maintenant la plus rapide et la plus courte des différentes approches pour Python 3.5.

En Python 3.6, la dict régulière devient à la fois ordonnée et compacte. (Cette fonctionnalité est valide pour CPython et PyPy mais peut ne pas être présente dans d'autres implémentations). Cela nous donne un nouveau moyen de déduplication tout en conservant l'ordre:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

En Python 3.7, la dict régulière est garantie à la fois ordonnée dans toutes les implémentations. Donc, la solution la plus courte et la plus rapide est:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

Réponse à @max: Une fois que vous passez à 3.6 ou 3.7 et utilisez la dict régulière au lieu de OrderedDict, vous ne pouvez pas vraiment battre la performance d'une autre manière. Le dictionnaire est dense et convertit facilement en une liste avec presque aucun frais généraux. La liste cible est pré-dimensionnée en len (d), ce qui enregistre toutes les redimensionnements qui se produisent dans une liste de compréhension. De plus, comme la liste des clés internes est dense, la copie des pointeurs est presque aussi rapide qu'une copie de liste.


54
2018-04-13 17:32



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


39
2018-01-26 15:47



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

La liste n'a même pas à être trié, la condition suffisante est que des 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, la solution de MizardX est la bonne.

Community edit: Ceci est cependant la façon la plus élégante de "compresser des éléments consécutifs en double dans un seul élément".


22
2018-05-27 21:37



Je pense que si tu veux maintenir la commande,

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 même, vous pouvez le faire:

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

Vous pouvez aussi faire ceci:

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

Il peut aussi être écrit 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 

18
2017-10-09 18:27



Pour une autre réponse très tardive à une autre très vieille question:

le itertools recettes avoir une fonction qui fait cela, en utilisant le seen définir la technique, mais:

  • Gère une norme key fonction.
  • N'utilise aucun hacks inconvenant.
  • Optimise la boucle en pré-reliant seen.add au lieu de le chercher N fois. (f7 fait aussi cela, mais certaines versions ne le font pas.)
  • Optimise la boucle en utilisant ifilterfalse, vous n'avez donc qu'à boucler les éléments uniques de Python, au lieu de tous. (Vous continuez de parcourir tous à l'intérieur ifilterfalse, bien sûr, mais c'est en C, et beaucoup plus vite.)

Est-ce vraiment plus rapide que f7? Cela dépend de vos données, vous devrez donc les tester et les voir. Si vous voulez une liste à la fin, f7 utilise un listcomp, et il n'y a aucun moyen de le faire ici. (Vous pouvez directement append au lieu de yieldou vous pouvez alimenter le générateur dans le list fonction, mais aucune ne peut être aussi rapide que LIST_APPEND dans un listcomp.) Quoi qu'il en soit, généralement, écourter quelques microsecondes ne sera pas aussi important que d'avoir une fonction facilement compréhensible, réutilisable, déjà écrite qui ne fonctionne pas. N'exige pas de DSU quand tu veux décorer.

Comme avec toutes les recettes, il est également disponible en more-iterools.

Si vous voulez juste lekey cas, vous pouvez le simplifier en tant que:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

11
2018-01-10 19:55