J'ai un conteneur Supposons que je souhaite trouver un élément en double si cela existe (juste n'importe quel élément de double arbitraire). Y a-t-il un moyen propre et efficace d'écrire cela?
[python 3] cont . Si je veux savoir s'il a des duplicats, je vais simplement vérifier len (suite) == len (ensemble (suite) .
9 Réponses :
Vous pouvez commencer à les ajouter à l'ensemble et dès que vous essayez d'ajouter l'élément qui est déjà dans l'ensemble que vous avez trouvé un duplicata.
Vous devez numériser tous les éléments des doublons car ils ne peuvent être que les derniers que vous vérifiez, vous ne pouvez donc pas être plus efficace que le pire des cas O (n), comme la recherche linéaire. Mais une simple recherche linéaire pour trouver un duplicate utilisera une mémoire O (n), car vous devez suivre ce que vous avez vu jusqu'à présent.
Si le tableau est trié, vous pouvez trouver des doublons dans O (n) heure sans utiliser de mémoire supplémentaire car les paires en double seront à côté de l'autre.
Essayez ceci:
def getFirstDup(cont):
for i in xrange(0, len(cont)):
if cont[i] in cont[:i]:
return cont[i]
return None
Sympa, mais serait peut-être mieux comme un générateur
@fmark: S'il avait besoin de plus d'un duplicata, alors oui, mais sa question me conduit à croire qu'il veut juste le premier duplicata.
Pas si agréable .. ne fonctionne que avec des conteneurs commandés et qui sait quel montant de choses devra se produire afin de couper la collection autant.
@Claudiu: J'ai vérifié que cela fonctionne également avec des conteneurs non ordonnés. S'il vous plaît vérifier mon code avant de basculer!
@Claudiu +1, a toujours la tête autour des contrats impliqués dans les types de conteneurs de Python.
-1 C'est une opération O (n ** 2) juste pour trouver 1 duplicata et même avoir une idée de ce que c'est un duplicata de ??? Sheesh, l'algorithme naïf 2 à boucles qui compare chaque paire possible ne prend que NC2, c'est-à-dire. N * (N-1) / 2 comparaisons
@John: c'est o (n ^ 2) le pire des cas, mais cela cessera de calculer la première duplicata; Si vous vous attendez à ce que la séquence soit dense avec des duplicats, elle peut fonctionner mieux que certaines autres solutions. Cela dit, ce n'est pas du tout python idiomatique.
@Zeke: >>> B = Set ("ABCDEF") >>> B [: 4] Traceback (appel le plus récent): Fichier "
@Claudiu: Cette fonction est conçue pour prendre des listes, pas des ensembles. Je suppose que "conteneur" est un descripteur assez large; J'ai écrit cette fonction pour gérer les listes sans vérifier d'autres types de conteneurs.
@Zeke: Alors, que vouliez-vous dire lorsque vous avez dit que cela fonctionne également avec des conteneurs non ordonnés, si vous ne l'avez testé que avec des listes? Vouliez-vous dire trié? trié! = ordonné. Ah aussi la question pose des questions sur les conteneurs en général, d'où mon bowvote, car cela ne fonctionne que sur des listes ou d'autres conteneurs commandés (ou d'être encore plus spécifiques, des conteneurs de support de tranche).
@Claudiu: Assez juste, merci pour la clarification sur le bowvote. J'utilisais de manière incorrecte comme un synonyme de commande.
Ce n'est pas évident, quel est le point de trouver un élément arbitraire qui est un double ou 1 ou plusieurs autres éléments de la collection ... Voulez-vous le supprimer? fusionner ses attributs avec ceux de ses jumeaux / tripléts / ... / n-tuples? Dans tous les cas, c'est une opération O (n), qui, si elle est répétée jusqu'à ce que plus de doublons ne soit détectée soit une opération O (n ** 2).
Cependant, vous pouvez obtenir une offre en vrac à l'entrepôt d'algorithme: trier la collection - O (n * journal (n)) - puis utiliser itheroTools.groupby pour grouper les duplicats et Croisière à travers les grappes, ignorant les grappes de la taille 1 et faire ce que vous voulez avec les grappes de taille> 1 - tout cela n'est que sur O (n).
Bon point. Dans mon cas, il s'agissait simplement de signaler un duplicata (puisqu'il est censé soulever une exception). Difficile à penser quand on pourrait vouloir faire cela autrement.
from collections import Counter
cont = [1, 2, 3]
c = Counter(cont)
x = someItem
if c[x] == 0:
print("Not in cont")
elif c[x] == 1:
print("Unique")
else:
print("Duplicate")
compteur est uniquement implémenté à partir de 2.7 en cours si je me rappelle correctement, avec 2,5 ou 2,6, vous pouvez utiliser par défaut (int) dans une boucle et incrémenter manuellement, bien que ce soit évidemment moins efficace. .
OK, ma première réponse est devenue un peu flack, alors je pensais que j'essayais de différentes façons de le faire et de signaler les différences. Voici mon code.
time python ./test.py 1
C'est un très mauvais moyen de tester. Vous devez les mettre chacun dans leur propre fonction et utiliser le TIMEIT Module. Cela découpera des trucs comme le temps de démarrage.
@AaronsTerling: Ce n'était pas censé être particulièrement élégant. Je suis plus intéressé par les tendances générales plutôt que des moments spécifiques, plus j'étais malade de ma première tentative de descendre par des personnes qui devinaient que c'était un mauvais algorithme, mais n'avait aucune donnée pour le sauvegarder. Ce n'est pas une bonne donnée, mais ce sont des données; La prochaine fois, je vais utiliser le module TimeiT.
+1 pour mettre dans l'effort. Ne prenez pas les bowvotes personnellement, pensez-y comme une expérience d'apprentissage!
Pour la méthode 2, vous n'avez pas besoin de copier l'ensemble complet, rappelez-vous que sa longueur suffit. La méthode 6 est destinée à résoudre un problème plus difficile (trouver tous les doublons). Le fait de faire la foire du test, ne mettez aucun élément en double, et voyez combien de temps il faudrait pour retourner Aucun . Il est clair que les méthodes 2, 3 et 4 sont les seules méthodes de temps linéaire, alors rien d'autre ne doit être testé. À la fin, sur Python 3, je reçois 2: 5.18s, 3: 2.22s, 4: 2,63. Étonnamment, set (qui semble la solution naturelle) est de 20% plus lent que la dicte.
@max: bonne prise sur la méthode 2. Après avoir examiné ma méthodologie, j'aurais vraiment dû essayer une liste sans doublons, puis un au milieu, et une à la fin pour obtenir des résultats plus réalistes. Eh bien, peut-être la prochaine fois.
Votre test ne fonctionne qu'avec l'élément dupliqué situé à proximité du début de la très grande liste ... Si vous avez également testé avec l'itérateur à différents endroits, il est éclairant: pour emplacement dans (50 5000 50000 5000000): c = plage (0.10000000) C [Emplacement] = 0
Si votre conteneur est une liste, vous pouvez simplement transmettre la valeur que vous recherchez à sa méthode de compte () et vérifiez le résultat:
>>> l = [1,1,2,3] >>> l.count(1) 2 >>>
Selon http://wiki.python.org/moin/timecomplexity la plupart des Les opérations de liste sont terriblement inefficaces (il suffit de confirmer que La méthode donnée par l'affiche originale Il existe une optimisation majeure qui est possible, ce qui consiste à accumuler itérativement l'ensemble. Cela reviendrait rapidement sur certains types de listes, par exemple. Vous pouvez également renvoyer le premier duplicaté, mais vous ne pouvez pas retourner Sidenote: Il existe des moyens d'améliorer l'efficacité spatiale pour un coup mineur à l'efficacité (par exemple Filtres de fleurs). x dans myList semble être o (n) dans python3). x dans la myiste sont O (n) ). [0,1,1,2,3,4,5, ...] . Cependant, vous supposez implicitement un peu de la distribution de vos listes (par exemple, optimisez-vous pour ce cas ou optimiser les doublons à la fin, ou les deux?). La bonne chose à propos de cette optimisation est qu'elle n'affecte pas la vitesse asymptotique. Voici comment je voudrais le coder avec élégance: Aucun ; Vous devriez soulever une exception car le démonteur peut contenir Aucun .
Autres suggestions, semblables à la réponse de Jonesy. Au moins en Python3 (n'a pas été testé dans Python 2.7), lorsque c [-5000] = 0, cela devient plus rapide que la solution 3 et 4 de la réponse originale. Sinon, il n'est que légèrement plus rapide que la solution 1 et 2 ...
Votre méthode est efficace! =) Il est
o (n) temps et espace (meilleur que vous pouvez faire depuisx dans myList esto (n) , voir wiki.python.org/moin/timecomplexity ). Il existe des moyens d'améliorer l'efficacité spatiale pour un appui mineur à l'efficacité du temps (par exemple, des filtres de floraison). L'autre sens, vous pouvez améliorer considérablement, c'est de retourner instantanément sur certains types de listes, par exemple. [0,1,1,2,4,5, ...]. Cela supposait un peu de la distribution de vos listes (par exemple, optimisez-vous pour cette affaire ou dupliquée à la fin, ou les deux?), Mais peut être une optimisation intéressante car elle n'affecte pas la vitesse asymptotique.