J'ai une liste que j'essaie de supprimer des éléments en double. J'utilise Python 2.7.1 afin que je puisse simplement utiliser la fonction ci-dessous est une fonction que j'ai écrite; qui fait cela. Cependant, je me demande s'il y a une meilleure façon / plus rapide. De plus, tout commentaire serait apprécié. La fonction ci-dessus suppose qu'aucun des éléments ne sera aucun , et que les éléments sont en ordre (c'est-à-dire La fonction ci-dessus renvoie
8 Réponses :
Je pense que c'est parfaitement ok. Vous obtenez O (n) performance qui est le meilleur que vous puissiez espérer.
Si la liste n'était pas ordonnée, vous auriez besoin d'une assistante définir pour contenir les éléments que vous avez déjà visités, mais dans votre cas n'est pas nécessaire.
Pourquoi le bowvote? Je ne vois rien de mal avec Tim Pietzckers Post.
Utilisez un ordre ordonné:
from collections import OrderedDict
l = ['a', 'a', 'a', 'b', 'b', 'c', 'd']
d = OrderedDict()
for x in l:
d[x] = True
# prints a b c d
for x in d:
print x,
print
Cela nécessite que les éléments par haschable; Par exemple, cela ne fonctionnerait pas si les éléments étaient des listes ou des dictionnaires; En outre, cela nécessite une opération O (n) , plutôt qu'un tas de O (1) Opérations (qui peuvent ou non ce que veut que l'OP veuille, juste quelque chose à garder à l'esprit)
Je n'ai jamais vu de boucle pour une boucle décrite comme "un groupe d'opérations O (1)" avant. Hm, n o (1) opérations serait ... O (n)
Je pense que c'est dans les mêmes lignes que de décrire 4 comme 2 + 2.
Mais que si la liste est grande? Économiser ces très tristes serait coûteux de mémoire. Je ne comprends pas vraiment pourquoi Python n'a pas d'ensemble commandé. Quel est le problème avec la commande d'insertion par défaut? C'est juste une belle propriété supplémentaire à avoir!
semble bien pour moi. Si vous voulez vraiment utiliser des ensembles, faites quelque chose comme ceci:
def ordered_set (_list) :
result = set()
lastitem = None
for item in _list :
if item != lastitem :
result.add(item)
lastitem = item
return sorted(tuple(result))
Avez-vous testé votre code? Vous n'abandonnez jamais rien à résultat . En outre, l'ensemble point d'un ensemble est que vous n'avez pas besoin de vérifier s'il contient déjà un élément ou non - vous venez de résultat = définir (_list) . Aucune itération requise. Mais cette méthode (ou la vôtre) échouerait si l'ordre des articles est autre que l'alphabétique ...
Toute personne qui tente d'utiliser cette fonction obtiendra: NameError: Nom global 'NewList' n'est pas défini
Si votre liste n'est pas triée, votre question n'a pas de sens. par exemple. [1,2,1] pourrait devenir [1,2] ou [2,1]
pour la suppression en ligne, voir Supprimer des éléments d'une liste en itérant ou Supprimer des éléments d'une liste en itérant sans utiliser de mémoire supplémentaire dans Python Un astuce que vous pouvez utiliser est que si vous savez que x est trié, et vous savoir x [i] = x [i + j] alors vous n'avez pas besoin de vérifier quoi que ce soit entre x [i] et x [i + j] (et si vous n'avez pas besoin de supprimer ces valeurs J, vous pouvez simplement Copiez les valeurs que vous souhaitez dans une nouvelle liste) Donc, alors que vous ne pouvez pas battre n Opérations si tout dans l'ensemble est unique, c'est-à-dire len (réglage (x)) = len (x)
Il y a probablement un algorithme qui a n des comparaisons que son pire des cas, mais peut avoir des comparaisons N / 2 comme son meilleur cas (ou inférieure à N / 2 comme son meilleur cas si vous savez d'une manière ou d'une autre, sachez à l'avance que Len (X) / Len ( Définir (x))> 2 En raison des données que vous avez générées): L'algorithme optimal utiliserait probablement une recherche binaire pour trouver un J maximal pour chaque minimum I dans une approche de division et de type conquérir. Les divisions initiales seraient probablement de longueur len (x) / approximativement (len (ensemble (x))). Espérons que cela pourrait être effectué de telle sorte que même si len (x) = len (set (x)) il utilise toujours seulement n opérations.
Une autre méthode très rapide avec SET:
def remove_duplicates(lst):
dset = set()
# relies on the fact that dset.add() always returns None.
return [item for item in lst
if item not in dset and not dset.add(item)]
Merci de compléter, Pavel.
En supposant que la séquence d'entrée est non ordonnée, voici la solution O (n) code> (à la fois dans l'espace et le temps).
Il produit une séquence avec des doublons retirés, tout en laissant des éléments uniques dans le même ordre relatif que celui apparu dans la séquence d'entrée. >>> def remove_dups_stable(s):
... seen = set()
... for i in s:
... if i not in seen:
... yield i
... seen.add(i)
>>> list(remove_dups_stable(['q', 'w', 'e', 'r', 'q', 'w', 'y', 'u', 'i', 't', 'e', 'p', 't', 'y', 'e']))
['q', 'w', 'e', 'r', 'y', 'u', 'i', 't', 'p']
[2,1,2,1] pourrait devenir [1,2] ou [2,1], je suis d'accord que [2,1] a plus de sens dans ce cas, mais ce n'est pas implicite dans la question. Si l'ensemble est commandé, votre solution est toujours bonne, donc +1
@ROBERT, pourrait aussi bien uppote @ Zaur's Solution puisque elle fait aussi exactement la même chose en utilisant une compréhension de la liste. En rétrospectivement, j'aime-moi un de plus que cela ressemble à moins de code :)
Oups! @robert, je ne faisais pas attention à la chronologie. Dûment up-noté :)
Merci. Oui @ La solution de Zaur est bonne mais échouera si l'élément ne peut pas être haché. (Nous échouerons tous si la liste n'est pas commandée). Je pense que ma solution est peut-être le plus rapide mais je n'ai pas été bafouée sur de grands tableaux qui utilisent toute ma mémoire =)
Je sais que cela a déjà été répondu, mais voici une doublure (plus importation):
Il y a une solution unique_everseen décrite dans
http://docs.python.org/2/library/itheroTools.html
Il existe une autre question similaire qui donne un lien vers une mise en œuvre, Stackoverflow.com/questions/1653970/...
Serait-il préférable d'avoir la liste de rester automatiquement triée et d'être sans dupliquer? Ou est-ce bien d'avoir à purger périodiquement la liste des doublons?
Vous exemple, le code implique que
_list est une séquence qui n'a que des doublons contigus. Est-ce ce que tu veux dire? Il ne fonctionnera pas pour les entrées comme celles-ci[1, 2, -4, -4, 1] :1 sera toujours dupliqué, tandis que-4 < / code> sera dés-dupliqué.