[python] Suppression des doublons dans les listes



Answers

Dans Python 2.7 , la nouvelle façon de supprimer les doublons d'un itérable tout en le conservant dans l'ordre original 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 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']
Question

À peu près, j'ai besoin d'écrire un programme pour vérifier si une liste a des doublons et si c'est le cas, il les supprime et renvoie une nouvelle liste avec les éléments qui ne sont pas dupliqués / supprimés. C'est ce que j'ai mais pour être honnête je ne sais pas quoi faire.

def remove_duplicates():
    t = ['a', 'b', 'c', 'd']
    t2 = ['a', 'c', 'd']
    for t in t2:
        t.append(t.remove())
    return t



J'ai eu un dict dans ma liste, donc je ne pouvais pas utiliser l'approche ci-dessus. J'ai l'erreur:

TypeError: unhashable type:

Donc, si vous vous souciez de la commande et / ou certains articles ne sont pas nettoyables . Alors vous pourriez trouver ceci utile:

def make_unique(original_list):
    unique_list = []
    [unique_list.append(obj) for obj in original_list if obj not in unique_list]
    return unique_list

Certains peuvent considérer la compréhension de la liste avec un effet secondaire pour ne pas être une bonne solution. Voici une alternative:

def make_unique(original_list):
    unique_list = []
    map(lambda x: unique_list.append(x) if (x not in unique_list) else False, original_list)
    return unique_list



Faire une nouvelle liste en conservant l'ordre des premiers éléments de doublons en L

newlist=[ii for n,ii in enumerate(L) if ii not in L[:n]]

par exemple if L=[1, 2, 2, 3, 4, 2, 4, 3, 5] alors la nouvelle liste sera [1,2,3,4,5]

Cela vérifie que chaque nouvel élément n'apparaît pas dans la liste avant de l'ajouter. En outre, il n'a pas besoin d'importations.




La meilleure approche pour supprimer les doublons d'une liste est l'utilisation de la fonction set () , disponible en python, convertissant à nouveau cet ensemble en liste

In [2]: some_list = ['a','a','v','v','v','c','c','d']
In [3]: list(set(some_list))
Out[3]: ['a', 'c', 'd', 'v']



Cochez cette case si vous souhaitez supprimer les doublons (modification sur place plutôt que renvoyer une nouvelle liste) sans utiliser d'ensemble intégré, dict.keys, uniqify, counter

>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> for i in t:
...     if i in t[t.index(i)+1:]:
...         t.remove(i)
... 
>>> t
[3, 1, 2, 5, 6, 7, 8]



Celui-ci se soucie de la commande sans trop de tracas (OrderdDict & autres). Probablement pas le moyen le plus pythonien, ni le plus court, mais fait l'affaire:

def remove_duplicates(list):
    ''' Removes duplicate items from a list '''
    singles_list = []
    for element in list:
        if element not in singles_list:
            singles_list.append(element)
    return singles_list



Il y a beaucoup d'autres réponses suggérant différentes manières de le faire, mais ce sont toutes des opérations par lots, et certaines d'entre elles rejettent l'ordre original. Cela peut être correct selon ce dont vous avez besoin, mais si vous voulez parcourir les valeurs dans l'ordre de la première instance de chaque valeur, et que vous voulez supprimer les doublons à la volée par rapport à tous en même temps, vous pouvez utiliser ce générateur:

def uniqify(iterable):
    seen = set()
    for item in iterable:
        if item not in seen:
            seen.add(item)
            yield item

Cela retourne un générateur / itérateur, donc vous pouvez l'utiliser n'importe où que vous pouvez utiliser un itérateur.

for unique_item in uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]):
    print(unique_item, end=' ')

print()

Sortie:

1 2 3 4 5 6 7 8

Si vous voulez une list , vous pouvez le faire:

unique_list = list(uniqify([1, 2, 3, 4, 3, 2, 4, 5, 6, 7, 6, 8, 8]))

print(unique_list)

Sortie:

[1, 2, 3, 4, 5, 6, 7, 8]



Un collègue m'a envoyé la réponse acceptée dans le cadre de son code pour une codereview aujourd'hui. Bien que j'admire certainement l'élégance de la réponse en question, je ne suis pas satisfait de la performance. J'ai essayé cette solution (j'utilise set pour réduire le temps de recherche)

def ordered_set(in_list):
    out_list = []
    added = set()
    for val in in_list:
        if not val in added:
            out_list.append(val)
            added.add(val)
    return out_list

Pour comparer l'efficacité, j'ai utilisé un échantillon aléatoire de 100 entiers - 62 étaient uniques

from random import randint
x = [randint(0,100) for _ in xrange(100)]

In [131]: len(set(x))
Out[131]: 62

Voici les résultats des mesures

In [129]: %timeit list(OrderedDict.fromkeys(x))
10000 loops, best of 3: 86.4 us per loop

In [130]: %timeit ordered_set(x)
100000 loops, best of 3: 15.1 us per loop

Eh bien, que se passe-t-il si l'ensemble est retiré de la solution?

def ordered_set(inlist):
    out_list = []
    for val in inlist:
        if not val in out_list:
            out_list.append(val)
    return out_list

Le résultat n'est pas aussi mauvais qu'avec OrderedDict , mais toujours plus de 3 fois de la solution originale

In [136]: %timeit ordered_set(x)
10000 loops, best of 3: 52.6 us per loop



>>> t = [1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> t
[1, 2, 3, 1, 2, 5, 6, 7, 8]
>>> s = []
>>> for i in t:
       if i not in s:
          s.append(i)
>>> s
[1, 2, 3, 5, 6, 7, 8]



Essayez d'utiliser des ensembles:

import sets
t = sets.Set(['a', 'b', 'c', 'd'])
t1 = sets.Set(['a', 'b', 'c'])

print t | t1
print t - t1



Vous pouvez le faire simplement en utilisant des ensembles.

Etape 1: Obtenir différents éléments de listes
Step2 Obtenir des éléments communs de listes
Step3 Combinez-les

In [1]: a = ["apples", "bananas", "cucumbers"]

In [2]: b = ["pears", "apples", "watermelons"]

In [3]: set(a).symmetric_difference(b).union(set(a).intersection(b))
Out[3]: {'apples', 'bananas', 'cucumbers', 'pears', 'watermelons'}



En utilisant set :

a = [0,1,2,3,4,3,3,4]
a = list(set(a))
print a

En utilisant unique :

import numpy as np
a = [0,1,2,3,4,3,3,4]
a = np.unique(a).tolist()
print a



De nos jours, vous pouvez utiliser la classe Counter:

>>> import collections
>>> c = collections.Counter([1, 2, 3, 4, 5, 6, 1, 1, 1, 1])
>>> c.keys()
dict_keys([1, 2, 3, 4, 5, 6])



le code ci-dessous est simple pour supprimer les doublons dans la liste

def remove_duplicates(x):
    a = []
    for i in x:
        if i not in a:
            a.append(i)
    return a

print remove_duplicates([1,2,2,3,3,4])

il renvoie [1,2,3,4]




Si vous ne vous souciez pas de l'ordre et que vous voulez quelque chose de différent des méthodes pythoniques suggérées ci-dessus (c'est-à-dire, il peut être utilisé dans les interviews) alors:

def remove_dup(arr):
    size = len(arr)
    j = 0    # To store index of next unique element
    for i in range(0, size-1):
        # If current element is not equal
        # to next element then store that
        # current element
        if(arr[i] != arr[i+1]):
            arr[j] = arr[i]
            j+=1

    arr[j] = arr[size-1] # Store the last element as whether it is unique or repeated, it hasn't stored previously

    return arr[0:j+1]

if __name__ == '__main__':
    arr = [10, 10, 1, 1, 1, 3, 3, 4, 5, 6, 7, 8, 8, 9]
    print(remove_dup(sorted(arr)))

Complexité du temps: O (n)

Espace auxiliaire: O (n)

Référence: http://www.geeksforgeeks.org/remove-duplicates-sorted-array/




Related