Je voudrais ajouter un élément à une liste qui préserve l'ordre de la liste.est-il possible d'ajouter un élément à une liste et de conserver la commande?
Supposons que la liste d'objets est [a, b, c, d] j'ai une fonction cmp qui compare deux éléments de la liste. si j'ajoute f objet qui est le plus grand je voudrais qu'il soit à la dernière position.
peut-être il est préférable de trier la liste complète ...
bisect.insort est un peu plus rapide, le cas échéant, que append-then-tri (sauf si vous avez quelques éléments à ajouter avant d'avoir besoin de la liste à trier à nouveau) - mesure comme d'habitude sur mon ordinateur portable (une machine plus rapide bien sûr être plus rapide dans tous les domaines, mais le rapport devrait rester à peu près constant):
$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); bisect.insort(y, 22*random.random())'
1000000 loops, best of 3: 1.99 usec per loop
vs
$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); y.append(22*random.random()); y.sort()'
100000 loops, best of 3: 2.78 usec per loop
combien vous vous inquiétez à ce sujet la différence, bien sûr, dépend du degré de goulot d'étranglement de cette opération pour votre application - il y a bien sûr une situation où même cette fraction de microseconde fait toute la différence, bien qu'ils soient l'exception, pas la règle.
Le module bisect n'est pas aussi flexible et configurable - vous pouvez facilement passer votre propre comparateur personnalisé pour trier (bien que si vous pouvez le mettre sous la forme d'une clé = argument que vous êtes fortement conseillé de le faire que, dans Python 3, seule la touche = reste, cmp = est parti, car la performance ne peut tout simplement pas être réparée), alors que bisect utilise de manière rigide des comparaisons intégrées (donc vous devrez envelopper vos objets dans des wrappers implémentant __cmp__ ou __le__ à votre goût, ce qui a également des implications de performance importantes). À votre place, je commencerais par l'approche «append-then-sort», et je passerais à l'approche «bisect», moins pratique, uniquement si le profilage montrait que la performance était matérielle. Rappelez-vous Knuth's (et Hoare) citation célèbre, et Kent Beck's presque aussi célèbre! -)
Oui, voici ce bisect.insort est pour, mais il ne prend pas une fonction de comparaison. Si les objets sont des objets personnalisés, vous pouvez remplacer un ou plusieurs rich comparison methods pour définir l'ordre de tri souhaité. Ou vous pouvez stocker un 2-tuple avec la clé de tri comme premier élément, et le trier à la place.
L.insert(index, object) -- insert object before index