_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;
}
到目前为止,败露最好的/唯一的主要的优化是JS类型数组。 使用类型数组的正常基数排序的影子阵取得了最好的结果。我还可以使用内置的压栈/流行JS挤一点点额外的出到位快速排序。
So far, the best/only major optimization brought to light is JS typed arrays. Using a typed array for the normal radix sort's shadow array has yielded the best results. I was also able to squeeze a little extra out of the in place quick sort using JS built in stack push/pop.
最新的jsfiddle基准
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
看样子标准基数排序确实是国王对这项工作流。如果有人有时间来试验循环展开或其他修改它我就AP preciate吧。
我有一个具体的使用情况下,我想在JavaScript中最快的排序执行。将有大(50,000 - 2密耳),未分类(基本上是随机的),整数(32位有符号),客户端脚本将访问阵列,它则需要进行排序和present此数据。
I have a specific use case where I'd like the fastest possible sorting implementation in JavaScript. There will be large (50,000 - 2mil), unsorted (essentially random), integer (32bit signed) arrays that the client script will access, it then needs to sort and present this data.
我已经到位基数排序,并在地方快速排序的jsfiddle基准执行速度相当的快,但我的上限数组的长度他们仍然相当缓慢。快速排序执行我的上限数组的大小更好,而基数排序执行我的下限更好。
I've implemented a fairly fast in place radix sort and in place quick sort jsfiddle benchmark but for my upper bound array length they are still fairly slow. The quick sort performs better on my upper bound array size while the radix sort performs better on my lower bound.
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
我测试过的 类型数组 ,在QSIP版本似乎是在现代浏览器好:
I've tested typed arrays, the QSIP version seems to be good in modern browsers:
2 000 000 的元素
QSIP_TYPED | RDXIP_TYPED | QSIP_STD | RDXIP_STD
----------------------------------------------------------
Chrome | 300 1000 600 1300
Firefox | 550 1500 800 1600
http://jsfiddle.net/u8t2a/35/
支持(来源:的 http://caniuse.com/typedarrays ):
IE 10+ | FF 4+ | Chrome 7+ | Safari 5.1+ | Opera 11.6+