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

Question

Existe-t-il une fonction intégrée 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 le mien comme ceci:

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

(Merci à décompresser de cette exemple de code .)

Mais je souhaiterais utiliser un idiome intégré ou plus pythonique si possible.

Question associée: 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 solutions: http://www.peterbe.com/plog/uniqifiers- référence

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 d'appeler simplement seen.add()? Python est un langage dynamique, et la résolution de None chaque itération est plus coûteuse que la résolution d’une variable locale. or aurait pu changer entre les itérations, et le moteur d'exécution n'est pas assez intelligent pour l'exclure. Pour être prudent, il doit vérifier l'objet à chaque fois.

Si vous envisagez d’utiliser beaucoup cette fonction sur le même jeu de données, il serait peut-être préférable de choisir un jeu ordonné: http://code.activestate.com/recipes/528878/

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

(Petite remarque supplémentaire: <=> retourne toujours <=>, le <=> ci-dessus n'est donc qu'un moyen de tenter une mise à jour d'un ensemble, et non en tant que partie intégrante du test logique.)

Answer 2

Éditer 2016

Comme l'a souligné Raymond , dans Python 3.5+, où OrderedDict est implémenté en C, l'approche de la compréhension par liste être plus lent que more_itertools (sauf si vous avez réellement besoin de la liste à la fin - et même alors, uniquement si l'entrée est très courte). Donc, la meilleure solution pour 3.5+ est pip install more_itertools.

Important Modifier 2015

Comme le note @abarnert , le unique_everseen (not seen.add) contient une 2.7+ est une fonction conçue pour résoudre ce problème sans aucune mutation illisible (collections.OrderedDict) dans les interprétations de liste. 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 pas de piratage. Cela provient d'une implémentation de la recette itertools set.add , 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 None, acceptait l'idiome commun (qui fonctionne mais n'est pas optimisé pour la vitesse, j'utiliserais maintenant not None ) utilise pour cela True :

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]

Cela semble beaucoup mieux que:

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

et n'utilise pas le hack laid :

not seen.add(x)

qui repose sur le fait que <=> est une méthode sur place qui renvoie toujours <=> pour que <=> soit évalué à <=>.

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

Answer 3

Dans Python 2.7 , la nouvelle méthode permettant de supprimer les doublons d'un élément itérable tout en les maintenant dans l'ordre d'origine est la suivante:

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

Dans Python 3.5 , OrderedDict a une implémentation en C. Mon timing montre que c’est maintenant à la fois la plus rapide et la plus courte des différentes approches de Python 3.5.

Dans Python 3.6 , le dict normal est devenu à la fois ordonné et compact. (Cette fonctionnalité est valable pour CPython et PyPy mais peut ne pas être présente dans d'autres implémentations). Cela nous donne un nouveau moyen plus rapide de déduplication tout en conservant l’ordre:

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

Dans Python 3.7 , le dict normal est garanti pour les deux ordres, quelle que soit leur implémentation. La solution la plus rapide et la plus rapide est donc:

<*>

Réponse à @max: une fois que vous passez à 3.6 ou 3.7 et utilisez le dict normal à la place de OrderedDict , vous ne pouvez vraiment pas surpasser les performances. Le dictionnaire est dense et se transforme facilement en une liste presque sans surcoût. La liste cible est pré-dimensionnée à len (d), ce qui enregistre tous les redimensionnements qui surviennent lors de la compréhension d'une liste. De plus, comme la liste de clés internes est dense, la copie des pointeurs est presque aussi rapide qu’une copie de liste.

Answer 4

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

unique & # 8594; ['1', '2', '3', '6', '4', '5']

Answer 5

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

La liste n'a même pas besoin d'être triée , 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 effectivement ordonnée. Si ce n'est pas le cas, la solution de MizardX est la bonne.

Community Edit: C’est toutefois le moyen le plus élégant de & "; compresser des éléments consécutifs en double en un seul élément &";

.

Answer 6

Ne pas taper dans le pied (cette question est très ancienne et contient déjà beaucoup de bonnes réponses), mais voici une solution utilisant des pandas qui est assez rapide dans de nombreuses circonstances et qui est extrêmement simple à utiliser.

import pandas as pd

my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]

>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]

Answer 7

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 le faire:

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

Vous pouvez également 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 

Answer 8

Juste pour ajouter une autre implémentation (très performante) d'une telle fonctionnalité à partir d'un module externe ¹ : iteration_utilities.unique_everseen :

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

Horaires

J’ai fait quelques timings (Python 3.6) et ceux-ci montrent que c’est plus rapide que toutes les autres alternatives que j'ai testées, y compris OrderedDict.fromkeys, f7 et more_itertools.unique_everseen:

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

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

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

Et juste pour être sûr d'avoir également fait un test avec plus de doublons, juste pour vérifier si cela fait une différence:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

Et une contenant une seule valeur:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

Dans tous ces cas, la O(n*n) fonction est la plus rapide (sur mon ordinateur).

Cette O(n) fonction peut également gérer les valeurs inutiles de l'entrée (toutefois avec une performance <=> au lieu de la performance <=> lorsque les valeurs sont hashable).

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

¹ Avertissement: je suis l'auteur de ce paquet.

Answer 9

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

Les itertools recettes ont une fonction qui permet de le faire, en utilisant le < => définir la technique, mais:

• Gère une fonction seen standard.
• N'utilise aucun piratage indésirable.
• Optimise la boucle en liant à l'avance key au lieu de la rechercher N fois. (seen.add le fait aussi, mais pas certaines versions.)
• Optimise la boucle en utilisant f7. Vous ne devez donc parcourir que les éléments uniques de Python, et non tous. (Vous les parcourez toujours à l'intérieur de ifilterfalse, bien sûr, mais c'est en C et beaucoup plus rapidement.)

Est-ce réellement plus rapide que append? Cela dépend de vos données, vous devrez donc le tester et voir. Si vous voulez une liste à la fin, yield utilise un listcomp, et il n’ya aucun moyen de le faire ici. (Vous pouvez directement list au lieu de more-iterools ing, ou vous pouvez insérer le générateur dans la fonction <=>, mais aucun des deux ne peut être aussi rapide que LIST_APPEND dans une liste de composition.) En tout état de cause, généralement quelques microsecondes ne seront pas aussi importantes que d'avoir une fonction déjà écrite, facilement compréhensible, réutilisable, qui n'exige pas de DSU lorsque vous souhaitez décorer.

Comme pour toutes les recettes, il est également disponible dans <=> .

Si vous voulez seulement le cas no - <=>, vous pouvez le simplifier comme suit:

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

Answer 10

Dans Python 3.7 et les versions ultérieures, les dictionnaires sont a garanti de se souvenir de leur ordre d'insertion de clé. La réponse à la question résume la situation actuelle.

La OrderedDict solution devient alors obsolète et sans déclaration d'importation, nous pouvons simplement émettre:

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]

Answer 11

Pour les types ne pouvant pas être hachés (liste de listes, par exemple), basé sur MizardX:

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

Answer 12

Reprenant l'idée récursive utilisée dans la définition de la fonction nub de Haskell pour les listes, il s'agirait d'une approche récursive:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

exemple:

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

Je l'ai essayé pour des tailles de données croissantes et j'ai vu une complexité temporelle sub-linéaire (non définitive, mais suggère que cela devrait convenir pour des données normales).

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

Je pense également qu'il est intéressant de noter que cela pourrait facilement être généralisé à l'unicité par d'autres opérations. Comme ceci:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

Par exemple, vous pouvez transmettre une fonction qui utilise la notion d'arrondi au même nombre entier que s'il s'agissait de & "; égalité &"; à des fins d'unicité, comme ceci:

def test_round(x,y):
    return round(x) != round(y)

then unique (some_list, test_round) fournirait les éléments uniques de la liste où l'unicité ne signifierait plus l'égalité traditionnelle (ce qui est implicite en utilisant une sorte d'approche de ce problème basée sur un ensemble ou une clé dict-key), mais plutôt destiné à ne prendre que le premier élément arrondissant à K pour chaque entier possible K auquel les éléments pourraient arrondir, par exemple:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]

Answer 13

5 x plus rapide réduire variante mais plus sophistiqué

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]

Explication:

default = (list(), set())
# use list to keep order
# use set to make lookup faster

def reducer(result, item):
    if item not in result[1]:
        result[0].append(item)
        result[1].add(item)
    return result

>>> reduce(reducer, l, default)[0]
[5, 6, 1, 2, 3, 4]

Answer 14

La réponse de MizardX donne une bonne collection d'approches multiples.

C’est ce que j’ai trouvé en pensant tout haut:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

Answer 15

Vous pouvez référencer une liste de compréhension telle qu'elle est construite avec le symbole '_ [1]'.
Par exemple, la fonction suivante unique-ifie une liste d’éléments sans en modifier l’ordre en faisant référence à sa compréhension de liste.

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

Démo:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

Sortie:

[1, 2, 3, 4, 5]

Answer 16

Vous pourriez faire une sorte de bidouillage de compréhension de liste moche.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

Answer 17

Approche relativement efficace avec _sorted_ un numpy tableau:

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

Sorties:

array([ 1,  3,  8, 12])

Answer 18

l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

Expression génératrice utilisant la recherche O (1) d'un ensemble pour déterminer s'il convient ou non d'inclure un élément dans la nouvelle liste.

Answer 19

Une solution récursive simple:

def uniquefy_list(a):
    return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

Answer 20

Si vous avez besoin d'une doublure, cela pourrait peut-être vous aider:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

... devrait fonctionner, mais corrigez-moi si je me trompe

Answer 21

Si vous utilisez systématiquement pandas , et que l'esthétique est préférée aux performances, considérez alors la fonction intégrée fonction pandas.Series.drop_duplicates:

    import pandas as pd
    import numpy as np

    uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()

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

    alist = np.random.randint(low=0, high=1000, size=10000).tolist()

    print uniquifier(alist) == f7(alist)  # True

Calendrier:

    In [104]: %timeit f7(alist)
    1000 loops, best of 3: 1.3 ms per loop
    In [110]: %timeit uniquifier(alist)
    100 loops, best of 3: 4.39 ms per loop

Answer 22

Ceci préservera l'ordre et s'exécutera dans le temps O (n). En gros, l’idée est de créer un trou chaque fois qu’un duplicata est trouvé et de le couler au fond. utilise un pointeur lire et écrire. chaque fois qu'un doublon est trouvé, seul le pointeur de lecture avance et le pointeur d'écriture reste sur l'entrée de duplicata pour l'écraser.

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]

Answer 23

Une solution sans utiliser les modules ou ensembles importés:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

Donne la sortie:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

Answer 24

Une méthode sur place

Cette méthode est quadratique, car nous avons une recherche linéaire dans la liste pour chaque élément de la liste (à cela, nous devons ajouter le coût de la réorganisation de la liste à cause des del s).

Cela dit, il est possible de fonctionner sur place si nous partons de la fin de la liste pour aller vers l'origine en supprimant chaque terme présent dans la sous-liste à sa gauche

Cette idée dans le code est tout simplement

for i in range(len(l)-1,0,-1): 
    if l[i] in l[:i]: del l[i] 

Un test simple de la mise en oeuvre

In [91]: from random import randint, seed                                                                                            
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics                                                                 
In [93]: for i in range(len(l)-1,0,-1): 
    ...:     print(l) 
    ...:     print(i, l[i], l[:i], end='') 
    ...:     if l[i] in l[:i]: 
    ...:          print( ': remove', l[i]) 
    ...:          del l[i] 
    ...:     else: 
    ...:          print() 
    ...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]

In [94]:                                                                                                                             

Answer 25

Éliminer les doublons dans une séquence, mais en conservant l'ordre des éléments restants. Utilisation de la fonction de générateur à usage général.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]

Answer 26

L’approche de zmk utilise une compréhension de liste qui est très rapide, tout en maintenant l’ordre naturellement. Pour appliquer aux chaînes sensibles à la casse, il peut être facilement modifié. Cela préserve également le boîtier d'origine.

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Les fonctions étroitement associées sont:

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))