Algorithme de tri le plus rapide pour une situation spécifique

Question

Quel est l'algorithme de tri le plus rapide pour un grand nombre (dizaines de milliers) de groupes de 9 valeurs de double précision positive, où chaque groupe doit être trié individuellement? Il faut donc trier rapidement un petit nombre de valeurs de double précision éventuellement répétées, plusieurs fois de suite. Les valeurs sont dans l'intervalle [0..1]. Je me fiche de la complexité ou de la stabilité de l'espace, juste de la vitesse.

Answer 1

En triant chaque groupe individuellement, le tri par fusion serait probablement plus facile à implémenter avec de bons résultats.

Un réseau de tri serait probablement la solution la plus rapide: http://en.wikipedia.org/wiki/Sorting_network

Answer 2

Bonne question parce que cela se résume à « moyen le plus rapide pour trier un tableau de 9 éléments », et la plupart des comparaisons entre et l'analyse des méthodes de tri sont sur le point grand N. Je suppose que les «groupes» sont clairement définis et ne jouent pas un rôle réel ici.

Vous devrez probablement comparer quelques candidats car de nombreux facteurs (localité) entrent en jeu ici.

Dans tous les cas, le rendre parallèle semble une bonne idée. Utilisez Parallel.For() si vous pouvez utiliser, NET4.

Answer 3

Je pense que vous aurez besoin d'essayer quelques exemples pour voir ce qui fonctionne le mieux, car vous avez un ensemble inhabituel de conditions. Je pense que la meilleure sera l'un des

• réseau de tri
• tri par insertion
• tri rapide (un niveau - tri par insertion ci-dessous)
• tri par fusion

Étant donné que le double le nombre de précision est relativement long je suspecte que vous ne ferez pas mieux avec un genre de base, mais n'hésitez pas à l'ajouter.

Pour ce que cela vaut, Java utilise le tri rapide sur les doubles jusqu'à ce que le nombre d'éléments à trier tombe en dessous de 7, auquel cas utilise le tri d'insertion. La troisième option imite cette solution.

De plus, votre problème global est , donc vous voulez utiliser le parallélisme lorsque c'est possible. Le problème semble trop petit pour une solution distribuée (plus de temps serait perdu dans le réseau que sauvé), mais si elle est configurée correctement, votre problème peut utiliser très efficacement plusieurs cœurs.

Answer 4

Il semble que vous souhaitiez que la méthode la plus rapide soit de trier 9 valeurs. Comme le nombre de valeurs est limité, je ferais (comme Kathy l'a suggéré) d'abord un tri d'insertion déroulé sur les 4 premiers éléments et les 5 autres éléments. Ensuite, je fusionnerais ces deux groupes.

Voilà une sorte d'insertion déroulée de 4 éléments:

if (u[1] < u[0]) swap(u[0], u[1]); 
if (u[2] < u[0]) swap(u[0], u[2]); 
if (u[3] < u[0]) swap(u[0], u[3]); 

if (u[2] < u[1]) swap(u[1], u[2]); 
if (u[3] < u[1]) swap(u[1], u[3]); 

if (u[3] < u[2]) swap(u[2], u[3]); 

Voilà une boucle de fusion. Le premier ensemble de 4 éléments est en u, et le deuxième ensemble de 5 éléments en v. Le résultat est au r.

i = j = k = 0; 
while(i < 4 && j < 5){ 
    if (u[i] < v[j]) r[k++] = u[i++]; 
    else if (v[j] < u[i]) r[k++] = v[j++]; 
    else { 
    r[k++] = u[i++]; 
    r[k++] = v[j++]; 
    } 
} 
while (i < 4) r[k++] = u[i++]; 
while (j < 5) r[k++] = v[j++];