最快的方法来sorting在JavaScript中的32位有符号整数数组?

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

编辑:

到目前为止,最好的/唯一的主要优化是JStypes的数组。 对正常基数sorting的阴影数组使用types化数组已经产生了最好的结果。 我也能够挤出一点额外的地方快速sorting使用JS内置的堆栈推/popup。


最新的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 

看起来标准的基数sorting确实是这个工作stream程的王者。 如果有人有时间尝试循环展开或其他修改,我将不胜感激。

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

我已经实现了一个相当快的基数sorting和适当的地方快速sortingjsfiddle基准,但对于我的上限数组长度,他们仍然相当缓慢。 快速sorting在我的上限数组大小上执行得更好,而基数sorting在我的下限上执行得更好。

 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 

问题

  • 是否有更好的实现任何sortingalgorithm,可以满足我的用例/需求?
  • 是否有任何优化,可以在我的地方基数/快速sorting实现来提高性能?
    • 有没有一种有效的方法来将我的基数从recursion转换为迭代函数? 内存和执行速度。

目标

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

澄清/注意事项

  • “DEFINE FAST”我更喜欢在所有现代浏览器上运行良好的一般情况,但是如果有一个浏览器特定的优化,使得可以接受的显着改进。
  • sorting可能是服务器端,但我宁愿避免这个,因为JS应用程序可能会成为一个独立的(配对一些现成的专有应用程序,将传感器数据stream到一个文件)。
  • JavaScript可能不是最好的语言,但这是一个要求。
  • 我已经问过这个问题https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript不正确的答案是投了票,问题被closures。
  • 我试图使用多个浏览器窗口实例作为临时multithreading; 它没有泛滥。 我会有兴趣在产生多个窗口的并发性有用的信息。

我testing过types化数组 ,QSIP版本在现代浏览器中似乎很好:

200万个元素

  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+ 

您是否考虑过使用最大化caching的algorithm组合? 我在基准testing中看到,当子arrays变小时,您将切换到插入sorting。 一个有趣的方法是改为heapsort。 与quicksort结合使用,可以将最坏的情况归结为O(nlog(n))而不是O(n ^ 2)。 看看Introsort 。

我摆弄你的基准,并添加我自己的sortingfunction。 它和radixsort一样,但它的思想(和实现)更简单,就像一个基数,但是在二进制中,所以你只有两个存储桶,可以在原地进行。 看看http://jsfiddle.net/KaRV9/7/

我把我的代码放在“Quicksort in place”(因为它与quicksort非常相似,只是透过其他方式select了pivot)。 运行他们几次,在我的Chrome 15他们执行如此接近,无法区分他们。

我不打算评论你的sortingalgorithm。 你比我更了解这些。

但一个好主意是使用networking工作者。 这允许你的sorting在它自己的线程中运行在后台,因此不会阻塞这个接口。 不pipe怎样,这都是好的做法。 Chrome和Firefox支持得很好。 Opera有一个非线程版本。 不确定在IE中的支持,但很容易解决这个问题。 当然,使用multithreading会涉及很多开销。

合并sorting可以很容易地变成一个multithreading版本,这会给你一些性能提升。 消息传递带来了时间上的损失,所以如果运行速度更快的话,它将取决于你的具体情况。 请记住,非阻塞性​​质可能会让应用程序对于最终用户来说运行得更快。

编辑:我看到你已经使用插入sorting较小的子arrays。 我错过了。

使用quicksort的现实世界方法是检查子数组的大小,如果足够短,则使用快速低开销sorting,对于较大的数组(如插入sorting)来说太慢。

伪代码是沿着以下方向的东西:

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

要确定THRESHOLD,你需要在你关心的平台上计算它,在你的情况下 – 可能是不同的浏览器。 测量具有不同阈值的随机arrays的时间以find接近最佳的一个。 如果您发现显着差异,您也可以为不同的浏览器select不同的阈值。

现在,如果您的input不是真正的随机(这是很常见的),你可以看到更好的枢轴select提高性能。 常用的方法是三位的中位数 。