La suppression des doublons dans une liste de listes

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> import itertools
>>> k.sort()
>>> list(k for k,_ in itertools.groupby(k))
[[1, 2], [3], [4], [5, 6, 2]]

itertools offre souvent la manière la plus rapide et la plus puissante des solutions à ce genre de problèmes, et est bien vaut la peine de s'intimement familier avec!-)

Modifier: comme je le mentionne dans un commentaire, normal optimisation des efforts se sont concentrés sur les grandes entrées (le big-O approche) parce que c'est tellement plus facile qu'il offre de bons rendements sur les efforts. Mais parfois (essentiellement pour "tragiquement crucial goulets d'étranglement" dans intérieure, profonde de boucles de code qui pousse les limites de la performance des limites), on peut avoir besoin d'aller dans beaucoup plus de détails, fournissant des distributions de probabilité, décider qui des mesures de rendement pour optimiser (peut-être la limite supérieure ou la 90e centile est plus important que la moyenne ou la médiane, selon les applications), en procédant éventuellement-heuristique vérifie au début pour choisir les différents algorithmes en fonction des données d'entrée caractéristiques, et ainsi de suite.

Des mesures précises de "point" de la performance (code vs code B pour une entrée spécifique) sont une partie de cette très coûteux, et de la bibliothèque standard du module de timeit aide ici. Cependant, il est plus facile de l'utiliser à l'invite du shell. Pour exemple, voici un court module de présenter l'approche générale de ce problème, enregistrez-le au nodup.py:

import itertools
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
def doset(k, map=map, list=list, set=set, tuple=tuple):
return map(list, set(map(tuple, k)))
def dosort(k, sorted=sorted, xrange=xrange, len=len):
ks = sorted(k)
return [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]
def dogroupby(k, sorted=sorted, groupby=itertools.groupby, list=list):
ks = sorted(k)
return [i for i, _ in itertools.groupby(ks)]
def donewk(k):
newk = []
for i in k:
if i not in newk:
newk.append(i)
return newk
# sanity check that all functions compute the same result and don't alter k
if __name__ == '__main__':
savek = list(k)
for f in doset, dosort, dogroupby, donewk:
resk = f(k)
assert k == savek
print '%10s %s' % (f.__name__, sorted(resk))

Remarque le test de cohérence (effectuée lorsque vous venez de le faire python nodup.py) et la base technique de levage (faire de la constante globale de noms local pour chaque fonction de la vitesse), de mettre les choses sur un pied d'égalité.

Maintenant, nous pouvons exécuter des vérifications sur le petit exemple de liste:

$ python -mtimeit -s'import nodup' 'nodup.doset(nodup.k)'
100000 loops, best of 3: 11.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort(nodup.k)'
100000 loops, best of 3: 9.68 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby(nodup.k)'
100000 loops, best of 3: 8.74 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.donewk(nodup.k)'
100000 loops, best of 3: 4.44 usec per loop

confirmant que l'équation du second degré approche a petit-assez constantes pour le rendre attrayant pour les petites listes avec quelques valeurs dupliquées. Avec une courte liste sans doublons:

$ python -mtimeit -s'import nodup' 'nodup.donewk([[i] for i in range(12)])'
10000 loops, best of 3: 25.4 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dogroupby([[i] for i in range(12)])'
10000 loops, best of 3: 23.7 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.doset([[i] for i in range(12)])'
10000 loops, best of 3: 31.3 usec per loop
$ python -mtimeit -s'import nodup' 'nodup.dosort([[i] for i in range(12)])'
10000 loops, best of 3: 25 usec per loop

quadratiques approche n'est pas mauvaise, mais les trier et grouper sont les meilleures. Etc, etc.

Si (comme l'obsession de la performance suggère) cette opération est à un noyau boucle intérieure de votre repousser les limites de l'application, il vaut la peine d'essayer la même série de tests sur d'autres représentant des échantillons d'entrée, éventuellement détecter une simple mesure de manière heuristique vous permettent de choisir l'une ou l'autre approche (mais la mesure doit être rapide, bien sûr).

Il est également bien la peine d'envisager de garder une représentation différente pour k -- pourquoi a-t-elle à être une liste de listes plutôt que d'un ensemble de n-uplets en premier lieu? Si la double tâche de suppression est fréquent, et le profilage montre le programme du goulot d'étranglement des performances, la tenue d'un ensemble de n-uplets tout le temps et d'obtenir une liste de listes de si et, le cas échéant, pourrait être plus rapide dans l'ensemble, par exemple.

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
>>> k = sorted(k)
>>> k
[[1, 2], [1, 2], [3], [4], [4], [5, 6, 2]]
>>> dedup = [k[i] for i in range(len(k)) if i == 0 or k[i] != k[i-1]]
>>> dedup
[[1, 2], [3], [4], [5, 6, 2]]

Je ne sais pas si c'est forcément plus rapide, mais vous n'avez pas à utiliser pour les tuples et les décors.

Liste de tuple et {} peut être utilisé pour supprimer les doublons

>>> [list(tupl) for tupl in {tuple(item) for item in k }]
[[1, 2], [5, 6, 2], [3], [4]]
>>> 

Créer un dictionnaire avec un tuple comme les clés, et d'imprimer les touches.

• créer le dictionnaire avec un tuple comme clé et de l'indice de valeur
• imprimer la liste de clés de dictionnaire

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
dict_tuple = {tuple(item): index for index, item in enumerate(k)}
print [list(itm) for itm in dict_tuple.keys()]
# prints [[1, 2], [5, 6, 2], [3], [4]]

Étrangement, les réponses ci-dessus supprime les "doublons" mais que si je veux enlever le double de la valeur aussi??
Les éléments suivants doivent être utiles et de ne pas créer un nouvel objet dans la mémoire!

def dictRemoveDuplicates(self):
a=[[1,'somevalue1'],[1,'somevalue2'],[2,'somevalue1'],[3,'somevalue4'],[5,'somevalue5'],[5,'somevalue1'],[5,'somevalue1'],[5,'somevalue8'],[6,'somevalue9'],[6,'somevalue0'],[6,'somevalue1'],[7,'somevalue7']]
print(a)
temp = 0
position = -1
for pageNo, item in a:
position+=1
if pageNo != temp:
temp = pageNo
continue
else:
a[position] = 0
a[position - 1] = 0
a = [x for x in a if x != 0]         
print(a)

et l'o/p est:

[[1, 'somevalue1'], [1, 'somevalue2'], [2, 'somevalue1'], [3, 'somevalue4'], [5, 'somevalue5'], [5, 'somevalue1'], [5, 'somevalue1'], [5, 'somevalue8'], [6, 'somevalue9'], [6, 'somevalue0'], [6, 'somevalue1'], [7, 'somevalue7']]
[[2, 'somevalue1'], [3, 'somevalue4'], [7, 'somevalue7']]