Python: prenez max N éléments d'une liste
Y a-t-il une fonction qui me retournerait les N éléments les plus élevés d'une liste?
C'est-à-dire si max(l) renvoie l'élément le plus élevé, sth. comme max(l, count=10) me retournerait une liste des 10 nombres les plus élevés (ou moins si l est plus petit).
Ou quel serait un moyen efficace et facile d'obtenir ces? (Sauf l'implémentation canonique évidente; aussi, pas de telles choses qui impliquent de trier toute la liste en premier parce que ce serait inefficace par rapport à la canonique solution.)
4 réponses
>>> import heapq, random
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100)))
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254]
La fonction de la bibliothèque standard, qui ne c'est heapq.nlargest
Commencez par les 10 premiers de L, appelez ce X. notez la valeur minimale de X.
Boucle sur L[i] pour i sur le reste de L.
Si L [i] est supérieur à min (X), supprimer min (X) de X et insérer L [i]. Vous devrez peut-être garder X comme une liste chaînée triée et faire une insertion. Mise à jour de min(X).
À la fin, vous avez les 10 plus grandes valeurs dans X.
Je soupçonne que ce sera O (kN) (où k est 10 ici) puisque le tri d'insertion est linéaire. Peut-être ce que GSL utilise, donc si vous pouvez lire certains C code:
Http://www.gnu.org/software/gsl/manual/html_node/Selecting-the-k-smallest-or-largest-elements.html
Probablement quelque chose dans numpy qui fait cela.
Une solution assez efficace est une variante de quicksort où la récursivité est limitée à la partie droite du pivot jusqu'à ce que la position du point de pivot soit supérieure au nombre d'éléments requis (avec quelques conditions supplémentaires pour traiter les cas de Frontière bien sûr).
La bibliothèque standard a heapq.nlargest, comme souligné par d'autres ici.