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

Question

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

javascriptperformancealgorithmoptimizationsorting

36

_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;
}

编辑：

迄今为止，揭示出来的最佳/唯一主要优化是JavaScript类型数组。使用类型数组作为正常基数排序的阴影数组产生了最佳结果。我还能够通过使用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 - 2百万）、未排序（基本上是随机的）、整数（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

问题

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

目标

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

澄清/注释

"定义快速" 我希望它在所有现代浏览器上都能良好运行，但如果有特定于浏览器的优化可以显著改善，那可能是可以接受的。
排序可以在服务器端完成，但我希望避免这样做，因为JS应用程序可能成为一个独立的应用程序（与某些现成的专有应用程序配对，该应用程序将传感器数据流式传输到文件中）。
JavaScript可能不是最适合这个问题的语言，但这是一个要求。
我已经在https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript上提出了这个问题，但一个错误的答案被投票，并且该问题被关闭。
我尝试使用多个浏览器窗口实例作为临时多线程; 但它并没有成功。我会对有关生成多个窗口以进行并发的有用信息感兴趣。

- Louis Ricci

1

很有趣的是基数排序比快速排序慢。你确定实现正确了吗？创建数组花费了多少时间？ - James

1

在你的分区中采用中位数法可能会使你的快速排序实现速度提高10％，并且可以避免大多数快速排序在部分有序子集上出现的问题。更好的方法是采用中位数法，这可以避免不常见的中位数杀手。 - Jim Mischel

@harold - 你有展示Int32Array能够优于[]的示例/测试吗？我对这种方法很感兴趣，可用的浏览器兼容性是什么水平？ - Louis Ricci

1

也许可以创建一个 http://jsperf.com/ 页面，以反映尝试的解决方案？ - zatatatata

2

只是我的个人看法... 对于大多数现代处理器，每个4字节的200k项可能适合于芯片上的CPU缓存，而200万则可能不适合。基数排序的随机访问性质一旦我们必须使用DRAM将会影响性能。快速排序通常需要顺序内存访问。 - Jason

显示剩余21条评论

5个回答

2

您是否考虑过使用多种算法来最大化缓存的利用？我在基准测试中看到，当子数组变小时，您正在切换到插入排序。一个有趣的方法是改为切换到堆排序。与快速排序一起使用，可以将最坏情况下的时间复杂度降至O(nlog(n))，而不是O(n^2)。请参考Introsort。

- Tudor

我正在使用的原地快速排序（目前具有最佳性能）通过堆栈避免递归。使用堆将会添加另一个ADT。如果您可以实现introsort并且它更快，那将是一个很大的帮助，但我没有看到任何强制要求去尝试它。 - Louis Ricci

好的，我会尝试实现它并让您知道。不幸的是，我不是很擅长JavaScript，但我会尽力而为... - Tudor

@LastCoder：我在某人的Github上找到了它。如果不太难的话，也许你可以想办法将其包含在你的基准测试中。https://github.com/fatshotty/IntroSort.js/blob/master/introsort.js - Tudor

1

我调整了你的基准测试，并添加了自己的排序函数。它的表现与基数排序相同，但其思想（和实现）更简单，就像二进制的基数排序，所以你只需要两个桶并且可以原地操作。看看http://jsfiddle.net/KaRV9/7/。

我把我的代码放在“原地快速排序”的位置（因为它与快速排序非常相似，只是选择了其他方式的枢轴）。在我的Chrome 15中运行它们几次，它们的性能非常接近，无法区分它们。

- user1046334

非常有趣，特别是速度方面的声明，在FF8中，标准基数排序的速度慢了约6倍，973毫秒对于172毫秒。Chrome的JS引擎一定有很大的不同。 - Louis Ricci

第一次运行时，这里的差异相似，但第二次、第三次和随后的运行与基数排序相当。别问我为什么 :-) - user1046334

1

我不会对你的排序算法发表评论，你比我更了解它们。

但一个好主意是使用Web Workers。这允许你的排序在后台运行在它自己的线程中，从而不会阻塞界面。无论如何，这都是一个好的实践。它在Chrome和Firefox上得到了很好的支持。Opera有一个非线程版本。不确定IE的支持情况，但可以轻松地解决这个问题。当然，使用多个线程会涉及一些开销。

归并排序可以很容易地制作成多线程版本，这将为您提供一些性能提升。当然，消息传递会带来时间成本，因此它是否运行更快将取决于您的具体情况。请记住，非阻塞的特性可能会让最终用户感觉应用程序运行得更快。

- Laurent Zuijdwijk

0

编辑：我看到您已经在使用插入排序来处理较小的子数组了。我错过了这个。

快速排序的好的真实世界方法是检查子数组的大小，如果够小，则使用一种快速低开销排序，该排序对于更大的数组来说速度太慢，比如插入排序。

伪代码大致如下：

quicksort(array, start, end):
  if ( (end-start) < THRESHOLD ) {
    insertion_sort(array, start, end);
    return;
  }
  // regular quicksort here
  // ...

为确定 THRESHOLD，您需要在您关心的平台上计时，在您的情况下可能是不同的浏览器。测量具有不同阈值的随机数组的时间，以找到接近最佳的阈值。如果发现显着差异，您还可以为不同的浏览器选择不同的阈值。

现在，如果您的输入实际上不是随机的（这是非常常见的），则可以看到更好的枢轴选择是否会提高性能。一个常见的方法是三数中值。

- orip

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gblazex · Accepted Answer

我测试过类型化数组，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+