_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
*/
function radixSort(intArr) {
var cpy = new Int32Array(intArr.length);
var c4 = [].concat(_radixSort_0);
var c3 = [].concat(_radixSort_0);
var c2 = [].concat(_radixSort_0);
var c1 = [].concat(_radixSort_0);
var o4 = 0; var t4;
var o3 = 0; var t3;
var o2 = 0; var t2;
var o1 = 0; var t1;
var x;
for(x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
t3 = (intArr[x] >> 8) & 0xFF;
t2 = (intArr[x] >> 16) & 0xFF;
t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
c4[t4]++;
c3[t3]++;
c2[t2]++;
c1[t1]++;
}
for (x=0; x<256; x++) {
t4 = o4 + c4[x];
t3 = o3 + c3[x];
t2 = o2 + c2[x];
t1 = o1 + c1[x];
c4[x] = o4;
c3[x] = o3;
c2[x] = o2;
c1[x] = o1;
o4 = t4;
o3 = t3;
o2 = t2;
o1 = t1;
}
for(x=0; x<intArr.length; x++) {
t4 = intArr[x] & 0xFF;
cpy[c4[t4]] = intArr[x];
c4[t4]++;
}
for(x=0; x<intArr.length; x++) {
t3 = (cpy[x] >> 8) & 0xFF;
intArr[c3[t3]] = cpy[x];
c3[t3]++;
}
for(x=0; x<intArr.length; x++) {
t2 = (intArr[x] >> 16) & 0xFF;
cpy[c2[t2]] = intArr[x];
c2[t2]++;
}
for(x=0; x<intArr.length; x++) {
t1 = (cpy[x] >> 24) & 0xFF ^ 0x80;
intArr[c1[t1]] = cpy[x];
c1[t1]++;
}
return intArr;
}
EDIT:
Jusqu'à présent, le meilleur/seule grande optimisation de la mise au jour est JS tableaux typés. À l'aide d'un tableau typé pour la normale de la base de tri de l'ombre du tableau a donné les meilleurs résultats. J'ai aussi été en mesure de serrer un peu plus de la en place rapide de tri à l'aide de JS construit dans la pile push/pop.
dernière jsfiddle de référence
Intel i7 870, 4GB, FireFox 8.0
2mil
radixSort(intArr): 172 ms
radixSortIP(intArr): 1738 ms
quickSortIP(arr): 661 ms
200k
radixSort(intArr): 18 ms
radixSortIP(intArr): 26 ms
quickSortIP(arr): 58 ms
Il apparaît standard de tri radix est en effet le roi pour ce flux de travail. Si quelqu'un a le temps d'expérimenter avec boucle-de dérouler ou d'autres modifications pour cela que je l'apprécierais.
J'ai un cas d'utilisation spécifiques où je voudrais la manière la plus rapide possible de tri implémentation en JavaScript. Il sera grand (de 50 000 2mil), triée (essentiellement aléatoire), entier (32 bits signés) des tableaux que le script client aura accès, il est alors nécessaire de trier et de présenter ces données.
J'ai mis en place assez rapide en place de tri radix et mise en place de tri rapide jsfiddle de référence , mais pour ma limite supérieure de la matrice de longueur, elles sont encore assez lent. Le tri rapide fonctionne mieux sur ma borne supérieure sur la taille du tableau, tandis que la base de tri de meilleures performances sur le bas de mon lié.
defaultSort is the built-in JavaScript array.sort with an integer compare function
Intel C2Q 9650, 4GB, FireFox 3.6
2mil
radixSortIP(intArr): 5554 ms
quickSortIP(arr): 1796 ms
200k
radixSortIP(intArr): 139 ms
quickSortIP(arr): 190 ms
defaultSort(intArr): 354 ms
Intel i7 870, 4GB, FireFox 8.0
2mil
radixSortIP(intArr): 990 ms
quickSortIP(arr): 882 ms
defaultSort(intArr): 3632 ms
200k
radixSortIP(intArr): 28 ms
quickSortIP(arr): 68 ms
defaultSort(intArr): 306 ms
Questions
- Est-il une meilleure mise en œuvre de tout algorithme de tri qui pourrait répondre à mon cas d'utilisation et des besoins?
- Existe-il des optimisations qui peuvent être faites à ma place radix/tri rapide implémentations pour améliorer les performances?
- Est-il un moyen efficace pour convertir mes en place radix tri à partir d'un récursif pour itératif de la fonction? La mémoire et la vitesse d'exécution.
Objectif
- Je suis en espérant que ces réponses vous m'aider à ~20% à 30% d'amélioration de la performance dans mon test de référence.
Clarifications/Notes
- "DÉFINIR un RAPIDE" je préfère un cas général où il fonctionne bien sur tous les navigateurs modernes, mais si il y a un navigateur spécifique d'optimisation qui permet une amélioration notable, qui peut être acceptable.
- Le tri PEUT être fait côté serveur, mais je préfère éviter ce parce que le JS application peut devenir autonome (jumelés, au large du plateau, propriétaire de l'application qui vont capteur de flux de données dans un fichier).
- JavaScript peut-être pas le meilleur langage pour cela, mais c'est une exigence.
- J'ai déjà posé cette question la façon la plus Rapide pour trier entier tableaux en JavaScript une réponse incorrecte a été voté et la question a été fermé.
- J'ai tenté à l'aide de plusieurs fenêtre du navigateur instances comme une fortune multi-threading; il n'a pas concrétisées. Je serais intéressé par l'information utile concernant la ponte plusieurs fenêtres à la simultanéité.
