J'aimerais obtenir les 100 plus gros éléments à partir d'une liste d'au moins 100000000 numéros.
Je pourrais trier toute la liste et prendre les 100 derniers éléments de la liste triée, mais cela coûterait très cher En termes de mémoire et de temps.
existe-t-il une façon existante facile et pythonique de faire cela?
Ce que je veux, c'est la fonction suivante au lieu d'un type pur. En fait, je ne veux pas perdre de temps pour trier les éléments que je m'en fiche.
Par exemple, c'est la fonction que je voudrais avoir: note que cette exigence est uniquement à la perspective de performance.
6 Réponses :
Algorithmes de sélection devrait aider ici.
Une solution très facile consiste à trouver le 100e plus gros élément, puis à parcourir les éléments de sélection de la liste plus grande 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 mieux possible.
Il y a des algorithmes plus sophistiqués. Un Heap , par exemple, est très agréable à ce problème. L'algorithme basé sur le tas est Il y a une discussion sur cette Problème sur la page Wikipedia pour les algorithmes de sélection. < / p>
Edit: Une autre affiche a souligné que Python a une solution intégrée à ce problème. De toute évidence, c'est beaucoup plus facile que de rouler le vôtre, mais je vais garder cet article au cas où vous voudriez savoir comment ces algorithmes fonctionnent. n log k où n est la longueur de la liste et k est le nombre d'éléments les plus importants que vous souhaitez sélectionner .
Dans la solution que vous avez décrite, pour "trouver le 100e plus gros élément", n'est-ce pas que par nécessité signifie que vous avez déjà trouvé une liste des 100 plus grands éléments?
Vous pouvez utiliser une structure de données de tas. Un tas ne sera pas nécessairement commandé, mais c'est un moyen assez rapide de conserver des données semi-commandées, et il bénéficie du bénéfice du plus petit article toujours étant le premier élément du tas.
Un tas a deux opérations de base qui vous aideront: ajouter et remplacer.
Fondamentalement, ce que vous faites, c'est ajouter des éléments à ce que vous atteignez une centaine d'articles (votre nombre supérieur n par votre question). Ensuite, après cela, vous remplacez le premier élément avec chaque nouvel élément, tant que le nouvel élément est plus grand que le premier élément.
Chaque fois que vous remplacez le premier élément avec quelque chose de plus grand, le code interne dans le tas puisse régler le contenu du tas de manière à ce que le nouvel élément ne soit pas le plus petit, il bulle dans le tas et le plus petit article sera "bulle" bas "au premier élément, prêt à être remplacé en cours de route.
Le module HEPQ dans la bibliothèque standard propose la fonction NLARGEST () pour le faire:
top100 = heapq.nlargest(100, iterable [,key])
Voilà. J'étais sur le point de suggérer qu'une file d'attente prioritaire serait un bon moyen de gérer cela en conjonction avec l'algorithme que j'ai suggéré. Ne pas être un programmeur Python, je n'ai pas réalisé que c'était déjà disponible.
La meilleure façon de le faire est de maintenir une file d'attente prioritaire triée de tas une fois qu'elle dispose de 100 entrées.
Bien que vous ne vous souciez pas si les résultats sont triés, il est intuitivement évident que vous obtiendrez cela gratuitement. Afin de savoir que vous avez le plus 100 top 100, vous devez commander votre liste actuelle de chiffres supérieurs dans l'ordre via une structure de données efficace. Cette structure saura le minimum, le maximum et la position relative de chaque élément de manière naturelle que vous pouvez affirmer sa position à côté de ses voisins.
Comme cela a été mentionné dans Python, vous utiliseriez HeaPQ. À Java PriorityQueue: http://java.sun.com/javase/ 6 / Docs / API / Java / UTIL / PriorityQueue.html
Voici une solution que j'ai utilisée qui est indépendante des bibliothèques et que Travaillera dans n'importe quel langage de programmation qui contient des matrices:
Initialisation: P>
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!>
Pour les algorithmes Weenies dans le public: vous pouvez le faire avec une variation simple sur l'algorithme de Tony Hoare trouver : Cet algorithme met le plus grand topn dans le premier topn Éléments du tableau A , sans les trier. Bien sûr, si vous le souhaitez trier, ou pour une simplicité pure, un tas est préférable et appeler la fonction de la bibliothèque est mieux encore. Mais c'est un algorithme cool.