Python: élimine les éléments N maximum de certaines listes

Question

Y at-il une fonction qui me renvoie les N éléments les plus élevés de certaines listes?

I.e. si max(l) renvoie l'élément le plus élevé, sth. comme max(l, count=10) me renverrait une liste des 10 plus grands nombres (ou moins si l est plus petit).

Ou ce qui serait un moyen facile et efficace d'obtenir ces derniers? (Excepté l'implémentation canonique évidente, aussi, pas de telles choses qui impliquent le tri de la liste entière d'abord parce que ce serait inefficace par rapport à la solution canonique.)

Answer 1

heapq.nlargest:

>>> import heapq, random 
>>> heapq.nlargest(3, (random.gauss(0, 1) for _ in xrange(100))) 
[1.9730767232998481, 1.9326532289091407, 1.7762926716966254] 

Answer 2

Une solution assez efficace est une variation de quicksort où la récursivité est limitée à la 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 indiqué par d'autres ici.

Answer 3

Commencez avec les 10 premiers de L, appeler 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), dépose min (X) à partir de X et insère L [i]. Vous devrez peut-être garder X comme une liste liée triée et faire une insertion. Mettre à jour min (X).

A la fin, vous avez les 10 plus grandes valeurs de X.

Je soupçonne que sera O (kN) (où k est 10 ici), car le tri par insertion est linéaire. Peut-être ce que GSL utilise, donc si vous pouvez lire un code C:

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.

Answer 4

La fonction de la bibliothèque standard qui fait cela est heapq.nlargest