Comment obtenir les plus gros nombres d'une énorme quantité?

Question

Je voudrais obtenir les 100 éléments les plus importants d'une liste d'au moins 100000000 nombres.

Je pourrais trier la liste entière et prendre les 100 derniers éléments de la liste triée, mais cela coûterait très cher en mémoire et en temps.

Existe-t-il un moyen simple et pythonique de le faire?

Ce que je veux, c'est suivre la fonction au lieu d'une sorte pure. En fait, je ne veux pas perdre de temps à trier les éléments qui ne me dérangent pas.

Par exemple, voici la fonction que j'aimerais avoir:

getSortedElements(100, lambda x,y:cmp(x,y))

Notez que cette exigence concerne uniquement les performances.

Answer 1

Le module heapq de la bibliothèque standard propose la fonction nlargest () pour cela:

top100 = heapq.nlargest(100, iterable [,key])

La liste ne sera pas entièrement triée, vous ne perdrez donc pas de temps en éléments inutiles.

Answer 2

Les algorithmes de sélection devraient aider ici.

Une solution très simple consiste à rechercher le centième élément le plus important, puis à parcourir la liste en sélectionnant des éléments plus volumineux que cet élément. Cela vous donnera les 100 plus gros éléments. Ceci est linéaire dans la longueur de la liste; c'est le meilleur possible.

Il existe des algorithmes plus sophistiqués. Un tas , par exemple, est très sensible à ce problème. L'algorithme basé sur le tas est n journal k où n est la longueur de la liste et k est le nombre d'éléments les plus volumineux que vous souhaitez sélectionner. .

Il existe une discussion sur ce problème sur la page Wikipedia pour les algorithmes de sélection.

Edit: Un autre poster a souligné que Python dispose d’une solution intégrée à ce problème. Évidemment, c’est bien plus facile que de rouler le vôtre, mais je vais garder ce post au cas où vous souhaiteriez en savoir plus sur le fonctionnement de tels algorithmes.

Answer 3

Vous pouvez utiliser une structure de données Heap. Un segment de mémoire ne sera pas nécessairement commandé, mais c’est un moyen assez rapide de conserver des données semi-ordonnées. En outre, le plus petit élément est toujours le premier élément du segment.

Un segment de mémoire comporte deux opérations de base qui vous aideront: Ajouter et remplacer.

En gros, vous ajoutez des éléments jusqu'à atteindre 100 éléments (votre nombre N le plus élevé par votre question). Ensuite, vous remplacez le premier élément par chaque nouvel élément, à condition que ce dernier soit plus grand que le premier.

Chaque fois que vous remplacez le premier élément par quelque chose de plus grand, le code interne du segment de mémoire ajustera le contenu du segment de sorte que, si le nouvel élément n'est pas le plus petit, il bouillonne dans le segment de mémoire et le plus petit élément " faire des bulles " au premier élément, prêt à être remplacé en cours de route.

Answer 4

Pour ce faire, la meilleure solution consiste à conserver une file d’attente prioritaire triée par le tas que vous séparez une fois qu’elle contient 100 entrées.

Même si vous ne voulez pas que les résultats soient triés, il est intuitivement évident que vous obtiendrez cela gratuitement. Afin de savoir que vous avez le top 100, vous devez commander votre liste actuelle des premiers chiffres dans l'ordre via une structure de données efficace. Cette structure connaît le minimum, le maximum et la position relative de chaque élément de manière naturelle et permet d'affirmer sa position à côté de ses voisins.

Comme cela a été mentionné en python, vous utiliseriez heapq. En Java PriorityQueue: http://java.sun.com/javase/ 6 / docs / api / java / util / PriorityQueue.html

Answer 5

Voici une solution que j'ai utilisée qui est indépendante des bibliothèques et qui fonctionnera dans n’importe quel langage de programmation comportant des tableaux:

Initialisation:

Make an array of 100 elements and initialise all elements
with a low value (less than any value in your input list).

Initialise an integer variable to 0 (or any value in
[0;99]), say index_minvalue, that will point to the
current lowest value in the array.

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

Pour chaque valeur, par exemple, valeur actuelle, dans la liste des entrées:

if current_value > minvalue

  Replace value in array pointed to by index_minvalue
  with current_value

  Find new lowest value in the array and set index_minvalue to
  its array index. (linear search for this will be OK as the array
  is quickly filled up with large values)

  Set minvalue to current_value

else
  <don't do anything!>

minvalue obtiendra rapidement une valeur élevée et donc la plupart des valeurs dans la liste d'entrée n'aura besoin que d'être comparé à minvalue (le résultat de la comparaison sera généralement faux).

Answer 6

Pour les algorithmes très appréciés du public: vous pouvez le faire avec une simple variation de l'algorithme de Tony Hoare Trouver :

find(topn, a, i, j)
   pick a random element x from a[i..j]
   partition the subarray a[i..j] (just as in Quicksort) 
     into subarrays of elements <x, ==x, >x
   let k be the position of element x
   if k == 0 you're finished
   if k > topn, call find(topn, a, i, k)
   if k < topn, call find(topn-k, k, j)

Cet algorithme place les plus grands éléments topn dans les premiers éléments topn du tableau a , sans que les trie . Bien sûr, si vous voulez les trier, ou pour des raisons de simplicité, un tas est préférable, et appeler la fonction de bibliothèque est encore meilleur. Mais c'est un algorithme sympa.