L'implémentation la plus rapide du tri d'entiers pour des entiers de 200-300 bits ?

Question

Quelle est l'implémentation de triage d'entiers la plus rapide pour des entiers de 200 à 300 bits ? La taille exacte des entiers est fixe ; j'ai jusqu'à 2 gigaoctets avec de tels entiers (tous en RAM).

J'ai entendu dire qu'il est possible de trier un tel ensemble en moyenne à O(n log log M) ou même à O(n sqrt(log log M)) temps, où n est le nombre d'entiers et M est le plus grand entier. L'utilisation de la mémoire est limitée (je peux utiliser jusqu'à 0.5-1 GB en plus). Le tri peut être fait in-place ; il peut être instable (réordonner les dups).

Existe-t-il une implémentation en C/C++ de cette méthode de tri, par exemple celle de Han & Thorup (2002) ?

Answer 1

A Radix Sort peut être utilisé pour trier des données avec des clés de taille fixe. Comme cette condition n'est pas souvent remplie, la technique n'est pas beaucoup discutée, mais elle peut être O(n) lorsque la taille de la clé est prise en compte.

Answer 2

Si l'utilisation de la mémoire est vraiment limitée. Je séparerai chaque octet et les stockerai dans une structure de données en trie, de l'octet le plus significatif au moins significatif. Si vous insérez les octets dans un ordre trié, vous pouvez ensuite itérer la trie et avoir toutes vos données triées.

Answer 3

Le tri par signature est bon pour les mots de grande taille avec une complexité en temps expédié de 'O (n lg lg n)', mais pour les mots de petite taille, vous pouvez obtenir la même complexité avec le tri de von Emde Boas. Récemment, Han et Thorup ont publié un algorithme de tri encore plus rapide avec une complexité temporelle prévue de 'O (n sqrt(lg lg n))'. Je ne suis pas sûr que vous puissiez trouver des implémentations de ces algorithmes en ligne, mais il existe probablement d'excellents articles et conférences sur le MIT et Harvard.

Answer 4

Je pense que la chose la plus raisonnable à faire est de créer un tableau de pointeurs vers les bigints, et de trier le tableau de pointeurs. Je suggère une sorte de quicksort modélisé, avec une fonction de comparaison intelligente.

La fonction de comparaison devrait être capable de décider la plupart du temps en regardant les 4 octets les plus significatifs. S'ils ne correspondent pas, alors la comparaison est décidée. S'ils correspondent, vous regardez les 4 octets suivants jusqu'à la fin de l'int.

Je suppose que la plage de données est probablement assez large pour qu'un tri radix ne soit pas pratique. Le tri rapide est généralement assez rapide si vos données sont aléatoires, et a des performances de cache qui battent la plupart des tris non radix.