在JavaScript中对32位有符号整数数组进行排序的最快方法？

Question

_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内置堆栈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

似乎标准基数排序确实是这项工作流程的王者.如果有人有时间尝试循环展开或其他修改,我将不胜感激.

我有一个特定的用例,我希望在JavaScript中尽可能快地实现排序.客户端脚本将访问大型(50,000 - 2mil),未分类(基本上是随机的),整数(32位有符号)数组,然后需要对这些数据进行排序和显示.

我已经实现了相当快速的基数排序和快速排序jsfiddle基准测试,但对于我的上限数组长度,它们仍然相当慢.快速排序在我的上限数组大小上表现更好,而基数排序在我的下限上表现更好.

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

---

问题

• 是否有更好的实现任何满足我的用例/需求的排序算法？
• 是否可以对我的基础radix /快速排序实现进行任何优化以提高性能？
• • 有没有一种有效的方法将我的原位基数排序从递归函数转换为迭代函数？内存和执行速度.

---

目标

• 我希望这些答案能帮助我在基准测试中获得约20-30%的性能提升.

---

澄清/注意事项

• "快速定义"我更喜欢一种在所有现代浏览器上运行良好的一般情况,但是如果有一个特定于浏览器的优化可以实现可接受的重大改进.
• 排序可以在服务器端完成,但我宁愿避免这种情况,因为JS应用程序可能会成为一个独立的(与一些现成的专有应用程序配对,将传感器数据传输到文件).
• JavaScript可能不是最好的语言,但它是一个要求.
• 我已经问过这个问题/sf/ask/497806781/一个错误的答案已经投票,问题已经结束.
• 我尝试使用多个浏览器窗口实例作为临时多线程; 它没有成功.我对有关产生多个并发窗口的有用信息感兴趣.

Answer 1

我测试了类型化数组,QSIP版本似乎在现代浏览器中很好:

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+