最快在JavaScript中32位有符号整数数组排序的方式？ [英] Fastest way to sort 32bit signed integer arrays in JavaScript?
问题描述
_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.
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
问题
- 有没有更好的实现任何排序算法能够满足我的使用情况/需求？
- 是否有可以向我的地方基数/快速排序的实现来提高性能的任何优化？
-
- 有没有从递归迭代函数转换我的地方基数排序的有效途径？内存和执行速度。
- Is there a better implementation of any sorting algorithm that would meet my use case/needs?
- Are there any optimizations that can be made to my in place radix/quick sort implementations to improve performance?
- Is there an efficient way to convert my in place radix sort from a recursive to iterative function? Memory and execution speed.
- 我希望这些问题的答案会帮我弄〜20％-30％的性能提升在我的基准测试。
- 在定义FAST我会preFER它运行良好，在所有现代浏览器一般情况下，但如果有一个浏览器特定的优化，使一个显著的改善是可以接受的。
- 的排序可以做服务器端，但我preFER避免这种情况，因为JS的应用程序可能会成为一个独立的（搭配一些现成的专有应用程序，将传感器数据传输到一个文件）。
- 在JavaScript可能不这样做的最好的语言，但它是一个必要条件。
- 我已经问过这个问题，<一个href="http://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript">Fastest办法在JavaScript整数数组排序的不正确的答案被向上表决的问题被关闭。
- 在我使用多个浏览器窗口实例作为一个临时搭建的多线程尝试;它没有做成。我很想在关于并发产卵多个窗口有用的信息。
- "DEFINE FAST" I would prefer a general case where it runs well on all modern browsers, but if there is a browser specific optimization that makes a significant improvement that may be acceptable.
- The sorting COULD be done server side, but I'd prefer to avoid this because the JS app may become a standalone (paired with some off the shelf proprietary app that will stream sensor data to a file).
- JavaScript may not be the best language for this but it's a requirement.
- I've already asked this question Fastest way to sort integer arrays in JavaScript an incorrect answer was up-voted and the question was closed.
- I've attempted using multiple browser window instances as a makeshift multi-threading; it didn't pan out. I'd be interested in useful info regarding spawning multiple windows for concurrency.
推荐答案
我测试过的 类型数组 ，在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://caniuse.com/typedarrays ）：
IE 10+ | FF 4+ | Chrome 7+ | Safari 5.1+ | Opera 11.6+这篇关于最快在JavaScript中32位有符号整数数组排序的方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
Questions
