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 de vous détendre pour cet exemple de code .)

Mais je voudrais me prévaloir d'un idiome intégré ou plus Pythonic 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 ?

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

Si vous prévoyez d'utiliser cette fonction beaucoup sur le même ensemble de données, vous feriez peut-être mieux avec 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()revient toujours None, donc ce qui orprécède n'est là que pour tenter une mise à jour définie, et non comme partie intégrante du test logique.)

Modifier 2016

Comme l'a souligné Raymond , en python 3.5+ où OrderedDictest 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). La meilleure solution pour 3.5+ est donc OrderedDict.

Édition importante 2015

Comme le note @abarnert , la more_itertoolsbibliothèque ( pip install more_itertools) contient une unique_everseenfonction conçue pour résoudre ce problème sans aucune mutation illisible ( not seen.add) dans les compréhensions 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]

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

Durée: O (N)

>>> 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 hack laid :

not seen.add(x)

qui s'appuie sur le fait qu'il set.adds'agit d'une méthode sur place qui renvoie toujours Nonedonc est not Noneévaluée True.

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).

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

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

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

En Python 3.6 , le dict régulier 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 de déduplication le plus rapide tout en conservant l'ordre:

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

Dans Python 3.7 , le dict régulier est garanti à la fois ordonné dans toutes les implémentations. Ainsi, 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 le dict normal au lieu de OrderedDict , vous ne pouvez pas vraiment battre les performances d'une autre manière. Le dictionnaire est dense et se convertit facilement en une liste avec presque aucun frais généraux. La liste cible est prédimensionnée à len (d), ce qui enregistre tous les redimensionnements qui se produisent dans une compréhension de liste. De plus, comme la liste des clés internes est dense, la copie des pointeurs est à peu près rapide comme copie de liste.

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

Ne pas donner un coup de pied à un cheval mort (cette question est très ancienne et a 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 morte 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]

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

Modification de la communauté: c'est cependant la façon la plus élégante de "compresser les éléments consécutifs en double en un seul élément".

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

Il peut également s'é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 

Dans Python 3.7 et supérieur, les dictionnaires sont garantis pour se souvenir de leur ordre d'insertion de clé. La réponse à cette question résume la situation actuelle.

La OrderedDictsolution devient ainsi obsolète et sans aucune déclaration d'importation, nous pouvons simplement émettre:

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

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

Les itertoolsrecettes ont une fonction qui le fait, en utilisant la seentechnique définie, mais:

• Gère une norme key fonction .
• N'utilise pas de hacks inconvenants.
• Optimise la boucle en pré-liant seen.addau lieu de la rechercher N fois. (f7 également cela, mais certaines versions ne le font pas.)
• Optimise la boucle en utilisant ifilterfalse, vous n'avez donc qu'à parcourir les éléments uniques en Python, au lieu de tous. (Vous parcourez toujours chacun d'eux à l'intérieur ifilterfalse, bien sûr, mais c'est en C, et beaucoup plus rapidement.)

Est-ce réellement plus rapide que f7? Cela dépend de vos données, vous devrez donc les tester et voir. Si vous voulez une liste à la fin, f7utilisez un listcomp, et il n'y a aucun moyen de le faire ici. (Vous pouvez directement appendau lieu de yielding, ou vous pouvez alimenter le générateur dans la listfonction, mais ni l'un ni l'autre ne peut être aussi rapide que le LIST_APPEND dans un listcomp.) important comme ayant une fonction facilement compréhensible, réutilisable et déjà écrite qui ne nécessite pas de DSU lorsque vous souhaitez décorer.

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

Si vous voulez juste le non- keycas, vous pouvez le simplifier comme:

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

Juste pour ajouter un autre (très performant) la mise en œuvre de la fonctionnalité d' un tel 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]

Timings

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, f7et 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 m'assurer que j'ai é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 un 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 iteration_utilities.unique_everseenfonction est la plus rapide (sur mon ordinateur).

Cette iteration_utilities.unique_everseenfonction peut également gérer des valeurs non partageables dans l'entrée (mais avec une O(n*n)performance au lieu de la O(n)performance lorsque les valeurs sont hachables).

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

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

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

Pour les types non hachables (par exemple liste de listes), 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 ) )]

Emprunter l'idée récursive utilisée pour définir la nubfonction de Haskell pour les listes, ce serait une approche récursive:

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

par exemple:

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

Je l'ai essayé pour augmenter la taille des données et j'ai vu une complexité temporelle sub-linéaire (non définitive, mais suggère que cela devrait être bien 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 que cela puisse être facilement généralisé à l'unicité par d'autres opérations. Comme ça:

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 passer une fonction qui utilise la notion d'arrondi au même entier comme s'il s'agissait "d'égalité" à des fins d'unicité, comme ceci:

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

alors unique (some_list, test_round) fournirait les éléments uniques de la liste où l'unicité ne signifiait plus l'égalité traditionnelle (ce qui est implicite en utilisant toute sorte d'approche basée sur un ensemble ou une clé dictée pour ce problème) mais plutôt destinée à prendre seul le premier élément qui arrondit à K pour chaque entier K possible que 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]

Variante 5 fois plus rapide mais plus sophistiquée

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

Vous pouvez référencer une compréhension de liste telle qu'elle est construite par le symbole '_ [1]'.
Par exemple, la fonction suivante unique-ifie une liste d'éléments sans changer leur ordre en référençant 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

Production:

[1, 2, 3, 4, 5]

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

Voici ce que j'ai trouvé en réfléchissant à haute voix:

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

voici un moyen simple de le faire:

list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=lambda x:list1.index(x))

qui donne la sortie:

["hello", " ", "w", "o", "r", "l", "d"]

Vous pourriez faire une sorte de hack de compréhension de liste laid.

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

Approche relativement efficace avec _sorted_un numpytableau:

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

Les sorties:

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

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

Expression de générateur qui utilise la recherche O (1) d'un ensemble pour déterminer s'il faut ou non inclure un élément dans la nouvelle liste.

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

Éliminer les valeurs en double dans une séquence, mais conserver l'ordre des éléments restants. Utilisation de la fonction génératrice à 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}]

les utilisateurs de pandas devraient vérifier pandas.unique.

>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])

La fonction renvoie un tableau NumPy. Si nécessaire, vous pouvez le convertir en liste avec la tolistméthode.

Si vous avez besoin d'une doublure, cela pourrait peut-être 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

Si vous utilisez régulièrement pandaset que l'esthétique est préférée aux performances, envisagez la fonction intégrée 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

Horaire:

    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

cela préservera l'ordre et fonctionnera en temps O (n). en gros, l'idée est de créer un trou partout où un doublon est trouvé et de le couler vers le bas. utilise un pointeur de lecture et d'écriture. chaque fois qu'un doublon est trouvé, seul le pointeur de lecture avance et le pointeur d'écriture reste sur l'entrée en double 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]

Une solution sans utiliser de modules ou d'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']

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 réorganisation de la liste en raison de la del s).

Cela dit, il est possible de fonctionner en place si nous partons de la fin de la liste et continuons vers l'origine en supprimant chaque terme qui est 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 l'implémentation

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

L'approche de zmk utilise une compréhension de liste qui est très rapide, tout en gardant 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())))

Compréhension d'une liste de lignes:

values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]

Ajoutez simplement une condition pour vérifier que la valeur ne se trouve pas sur une position précédente