在JavaScript中对大型（ish）数字数组进行排序的最快方法是什么？ [英] What is the fastest way to sort a large(ish) array of numbers in JavaScript

问题描述

在我的应用程序中，我需要对大型数组（100,000到1,000,000之间）的随机数进行排序。

In my application, I need to sort large arrays (between 100,000 and 1,000,000) of random numbers.

我一直在使用内置的 array.sort（comparisonFunction）其中comparisonFunction如下所示：

I've been using the built in array.sort(comparisonFunction) where comparisonFunction looks like this:

function comparisonFunction(a,b) {
    return a-b;
}

这很好用，但我读过（例如，原生JavaScript排序执行速度低于已实施的mergesort和quicksort ）有更快的选择，特别是如果您的要求符合某些条件：

This works just fine, but I've read (e.g., Native JavaScript sort performing slower than implemented mergesort and quicksort) that there are faster options, especially if your requirements meet certain conditions:

1. 我只需要对数字进行排序（例如，而不是对象或字母数字数据）


2. 数据是随机的（没有机会已经订购）


3. 排序不需要稳定

1. I only need to sort numbers (e.g., not objects, or alphanumeric data)
2. The data is random (no chance that it's already ordered)
3. The sort doesn't need to be stable

那么 - 在这种情况下可用的最快（或足够接近）排序算法是什么？

So - what is the fastest (or close enough) sort algorithm available under those circumstances?

并且，是否有规范（或者至少是一个相对理想的JavaScript实现？

And, is there a canonical (or at least a relatively ideal) JavaScript implementation?

[更新]

Yikes ...两次投票同在30秒的发布！因此，快速澄清 - 在相关问题中，OP需要稳定的排序。因为我没有 - 我想知道这是否会改变答案（也就是说，如果您事先知道您的数据不会被预先排序，那么可能会有更快的排序选项 不需要稳定的排序 ）。

Yikes... two down votes within 30 seconds of posting! So, a quick clarification - in the linked question, the OP required a stable sort. Since I don't - I'm wondering if that would change the answer (i.e., perhaps there's a faster sort option available if you know in advance that your data will not be pre-sorted, and you don't need a stable sort).

也许答案是不，但这就是我要问的原因。

Perhaps the answer is "no", but that's why I'm asking.

[更新＃2]

这是quicksort的一个实现，除非我犯了错误，否则打败本机轻松排序函数：

Here's an implementation of quicksort that, unless I've made a mistake - beats the native sort function handily:

function comparisonFunction(a, b) {
  return a - b;
}

function quickSort(arr, leftPos, rightPos, arrLength) {
  let initialLeftPos = leftPos;
  let initialRightPos = rightPos;
  let direction = true;
  let pivot = rightPos;
  while ((leftPos - rightPos) < 0) {
    if (direction) {
      if (arr[pivot] < arr[leftPos]) {
        quickSort.swap(arr, pivot, leftPos);
        pivot = leftPos;
        rightPos--;
        direction = !direction;
      } else
        leftPos++;
    } else {
      if (arr[pivot] <= arr[rightPos]) {
        rightPos--;
      } else {
        quickSort.swap(arr, pivot, rightPos);
        leftPos++;
        pivot = rightPos;
        direction = !direction;
      }
    }
  }
  if (pivot - 1 > initialLeftPos) {
    quickSort(arr, initialLeftPos, pivot - 1, arrLength);
  }
  if (pivot + 1 < initialRightPos) {
    quickSort(arr, pivot + 1, initialRightPos, arrLength);
  }
}
quickSort.swap = (arr, el1, el2) => {
  let swapedElem = arr[el1];
  arr[el1] = arr[el2];
  arr[el2] = swapedElem;
}

var
  i,
  arr1, arr2,
  length;

length = 1000000;


arr1 = [];
arr2 = [];
for (i = 0; i < length; i++) {
  arr1.push(Math.random());
  arr2.push(Math.random());
}

console.time("nativeSort");
arr1.sort(comparisonFunction);
console.timeEnd("nativeSort");


console.time("quickSort");
quickSort(arr2, 0, length - 1, length);
console.timeEnd("quickSort");

推荐答案

有一些排序实现始终超过股票 .sort （至少V8）， node-timsort 就是其中之一。示例：

There are sort implementations that consistently beat the stock .sort (V8 at least), node-timsort being one of them. Example:

var SIZE = 1 << 20;

var a = [], b = [];

for(var i = 0; i < SIZE; i++) {
    var r = (Math.random() * 10000) >>> 0;
    a.push(r);
    b.push(r);
}

console.log(navigator.userAgent);

console.time("timsort");
timsort.sort(a, (x, y) => x - y);
console.timeEnd("timsort");

console.time("Array#sort");
b.sort((x, y) => x - y);
console.timeEnd("Array#sort");

<script src="https://rawgithub.com/mziccard/node-timsort/master/build/timsort.js"></script>

以下是我所拥有的不同浏览器的一些时间（Chakra任何人？）：

Here are some timings from different browsers I have around (Chakra anyone?):

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/53.0.2785.113 Safari/537.36
timsort: 256.120ms
Array#sort: 341.595ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/602.2.14 (KHTML, like Gecko) Version/10.0.1 Safari/602.2.14
timsort: 189.795ms
Array#sort: 245.725ms

Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:51.0) Gecko/20100101 Firefox/51.0
timsort: 402.230ms
Array#sort: 187.900ms

所以，FF引擎与Chrome / Safari非常不同。

So, the FF engine is very different from Chrome/Safari.

这篇关于在JavaScript中对大型（ish）数字数组进行排序的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！