Algorithme de tri le plus efficace pour un grand nombre de nombres

Question

Je travaille sur un grand projet, je ne vais pas le faire ici, mais cette partie du projet consiste à prendre un très gros document de texte (minimum de environ 50 000 mots (pas unique)), et sortie chaque mot unique dans l'ordre du plus utilisé au moins utilisé (probablement les trois premiers seront "un" "un" et "le").

Ma question est bien sûr, quel serait le meilleur algorithme de tri à utiliser? Je lisais le tri par dénombrement, et je l'aime bien, mais je crains que la fourchette de valeurs ne soit trop grande par rapport au nombre de mots uniques.

Des suggestions?

Answer 1

D'abord, vous aurez besoin d'une carte de mot -> compte. 50 000 mots, ce n'est pas grand-chose - ça rentrera facilement dans la mémoire, donc il n'y a rien à craindre. En C++, vous pouvez utiliser le standard STL std :: map. Puis, une fois que vous avez la carte, vous pouvez copier toutes les clés de la carte dans un vecteur. Ensuite, triez ce vecteur en utilisant un opérateur de comparaison personnalisé: au lieu de comparer les mots, comparez les chiffres de la carte. (Ne vous inquiétez pas de l'algorithme de tri spécifique - votre tableau n'est pas très grand, donc n'importe quel type de bibliothèque standard fonctionnera pour vous.)

Answer 2

Je commencerais avec un quicksort et partirais de là.

Consultez le wiki page on sorting algorithms, cependant, pour apprendre les différences.

Answer 3

Jetez un coup d'œil au lien. Une représentation picturale sur comment fonctionne un algorithme différent. Cela vous donnera un indice!

Sorting Algorithms

Answer 4

Vous devriez essayer une sorte MSD radix. Il va trier vos entrées dans lexicographical order. Voici un google code project qui pourrait vous intéresser.

Answer 5

Ceci est un peu difficile parce que vous voulez une carte de mots -> fréquence, et vous voulez trier par la valeur plutôt que la clé (ce qui est commun). Il y a un exemple Java here qui montre comment le faire en utilisant un comparateur personnalisé.

L'algorithme que vous utilisez ne va pas avoir beaucoup d'effet, donc je m'en tiendrai à votre implémentation de bibliothèque standard.

Answer 6

Vous pouvez obtenir de meilleures performances que le tri rapide avec ce problème particulier, en supposant que si deux mots se produisent le même nombre de fois, l'ordre dans lequel vous les publiez n'a pas d'importance.

Première étape: Créez une carte de hachage avec les mots en tant que valeurs de clé et fréquence en tant que valeurs associées. Vous remplirez cette carte de hachage lorsque vous analyserez le fichier. Pendant que vous faites cela, assurez-vous de garder une trace de la plus haute fréquence rencontrée. Cette étape est la complexité O (n).

Deuxième étape: Créez une liste avec le nombre d'entrées égal à la fréquence la plus élevée de la première étape. L'index de chaque emplacement dans cette liste contiendra une liste de mots avec le nombre de fréquence égal à l'index. Donc les mots qui apparaissent 3 fois dans le document vont dans la liste [3] par exemple. Itérer à travers la carte de hachage et insérer les mots dans les endroits appropriés dans la liste. Cette étape est la complexité O (n).

Troisième étape: Effectue l'itération de la liste à l'envers et affiche tous les mots. Cette étape est la complexité O (n).

Dans l'ensemble, cet algorithme accomplira votre tâche en O (n) time plutôt que O (nlogn) requis par quicksort.

Answer 7

Je pense que vous voulez faire quelque chose comme cela est expliqué dans le post ci-dessous:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Langues qui soutiennent la fermeture font la solution beaucoup plus facile, comme LINQ comme Eric mentionné.

Answer 8

Dans presque tous les cas que j'ai testés, Quicksort a fonctionné le mieux pour moi. Cependant, j'ai eu deux cas où Combsort était le meilleur. Peut-être que combsort était meilleur dans ces cas-là parce que le code était si petit, ou en raison d'une certaine bizarrerie dans la façon dont les données étaient ordonnées.

Chaque fois que le tri apparaît dans mon profil, j'essaie les tris majeurs. Je n'ai jamais eu quoi que ce soit qui a dominé à la fois Quicksort et Combsort.

Answer 9

Pour les grands ensembles que vous pouvez utiliser ce qui est connu comme la « indexation basée genre » dans la recherche d'information, mais pour 50.000 mots que vous pouvez utiliser les éléments suivants:

• lire le fichier entier dans un tampon.
• analyser le tampon et générer un vecteur de jeton avec struct token {char * term, int termlen; } term est un pointeur sur le mot dans le tampon.
• trier le tableau par terme (ordre lexicographique).
• Définissez entrynum = 0, parcourez le terme vector, lorsque le terme est nouveau, stockez-le dans un vecteur: struct {char * term; int fréquence; } à l'index d'entrée, mettre la fréquence à 1 et incrémenter le numéro d'entrée, sinon augmenter la fréquence.
• trier le vecteur par fréquence dans l'ordre décroissant.

Answer 10

Vous pouvez également essayer d'implémenter des arbres numériques également connus sous le nom de Trie. Voici la link