Javascript 通过将 a.localeCompare(b) 切换为 (a<b?-1:(a>b?1:0))，排序速度提高 400 倍

400x Sorting Speedup by Switching a.localeCompare(b) to (a<b?-1:(a>b?1:0))

提问by Brad Dwyer

By switching a javascript sort function from

通过从 javascript 排序函数切换

myArray.sort(function (a, b) {
  return a.name.localeCompare(b.name);
});

to

到

myArray.sort(function (a, b) {
  return (a.name < b.name ? -1 : (a.name > b.name ? 1 : 0));
});

I was able to cut the time to sort a ~1700 element array in Chrome from 1993 milliseconds to 5 milliseconds. Almost a 400x speedup. Unfortunately this is at the expense of correctly sorting non-english strings.

我能够将 Chrome 中大约 1700 个元素数组的排序时间从 1993 毫秒缩短到 5 毫秒。几乎是 400 倍的加速。不幸的是，这是以正确排序非英语字符串为代价的。

Obviously I can't have my UI blocking for 2 seconds when I try to do a sort. Is there anything I can do to avoid the horribly slow localeCompare but still maintain support for localized strings?

显然，当我尝试进行排序时，我的 UI 无法阻塞 2 秒钟。我能做些什么来避免极其缓慢的 localeCompare 但仍然保持对本地化字符串的支持？

回答by Andy

A great performance improvement can be obtained by declaring the collator object beforehand and using it's compare method. EG:

通过事先声明 collat​​or 对象并使用它的 compare 方法可以获得很大的性能改进。例如：

const collator = new Intl.Collator('en', { numeric: true, sensitivity: 'base' });
arrayOfObjects.sort((a, b) => {
  return collator.compare(a.name, b.name);
});

Here's a benchmark script comparing the 3 methods:

这是比较 3 种方法的基准脚本：

const arr = [];
for (let i = 0; i < 2000; i++) {
  arr.push(`test-${Math.random()}`);
}

const arr1 = arr.slice();
const arr2 = arr.slice();
const arr3 = arr.slice();

console.time('#1 - localeCompare');
arr1.sort((a, b) => a.localeCompare(
  b,
  undefined, {
    numeric: true,
    sensitivity: 'base'
  }
));
console.timeEnd('#1 - localeCompare');

console.time('#2 - collator');
const collator = new Intl.Collator('en', {
  numeric: true,
  sensitivity: 'base'
});
arr2.sort((a, b) => collator.compare(a, b));
console.timeEnd('#2 - collator');

console.time('#3 - non-locale');
arr3.sort((a, b) => (a < b ? -1 : (a > b ? 1 : 0)));
console.timeEnd('#3 - non-locale');

回答by Jamie Pate

An effective Approach that I found when dealing with /mostly/ latin characters is to use the operator whenever both strings match a specific regex. EG: /^[\w-.\s,]*$/

我在处理 /mostly/ 拉丁字符时发现的一种有效方法是在两个字符串都匹配特定正则表达式时使用运算符。例如：/^[\w-.\s,]*$/

It's much faster if both strings match the expression, and at worst it seems to be slightly slower than blindly calling localeCompare.

如果两个字符串都匹配表达式，它会快得多，而且在最坏的情况下，它似乎比盲目调用 localeCompare 稍微慢一些。

Example here: http://jsperf.com/operator-vs-localecompage/11

这里的例子：http: //jsperf.com/operator-vs-localecompage/11

Update: it seems like Intl.Collator is currently the best option for performance across the board: https://jsperf.com/operator-vs-localecompage/22

更新：似乎 Intl.Collat​​or 目前是全面性能的最佳选择：https://jsperf.com/operator-vs-localecompage/22

回答by Kim T

It's difficult to know the fastest sort without seeing the data you are sorting. But jsperf has lots of good tests showing the performance differences between types of sorting: http://jsperf.com/javascript-sort/45http://jsperf.com/sort-algorithms/31

如果不查看您正在排序的数据，就很难知道最快的排序。但是 jsperf 有很多很好的测试显示了排序类型之间的性能差异：http: //jsperf.com/javascript-sort/45 http://jsperf.com/sort-algorithms/31

However none of these account for localised strings, and i'd imagine there is no easy way to sort localised strings and localeCompare is probably the best solution for this.

然而，这些都没有考虑到本地化的字符串，我想没有简单的方法来对本地化的字符串进行排序，localeCompare 可能是最好的解决方案。

Looking at mozilla reference is says: "When comparing large numbers of strings, such as in sorting large arrays, it is better to create an Intl.Collator object and use the function provided by its compare property." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

查看 mozilla 参考资料说：“在比较大量字符串时，例如对大型数组进行排序时，最好创建一个 Intl.Collat​​or 对象并使用其 compare 属性提供的函数。” https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

But going to the Intl.Collator reference it shows that is not support for firefox/safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator

但是转到 Intl.Collat​​or 参考它表明不支持 firefox/safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collat​​or

you could try using some of the options on localCompare to speed up the performance. But I've just done a quick test changing the sensitivity level and it seems like it won't improve the performance:

您可以尝试使用 localCompare 上的一些选项来加快性能。但我刚刚做了一个快速测试，改变了灵敏度水平，看起来它不会提高性能：

list.sort(function(a, b) {
  return a.localeCompare(b, {sensitivity:'base'});
});

http://jsperf.com/sort-locale-strings

http://jsperf.com/sort-locale-strings

回答by jlgrall

Try sorting it in 2 steps:

尝试分两步排序：

1. With the operator: as you said, it will be 400 times faster
2. Then with localCompare(): this has now less comparisons to do because the array is mostly sorted.

1. 与运营商：正如你所说，它会快400倍
2. 然后用localCompare(): 现在比较少了，因为数组主要是排序的。

Note: I think that localCompare()will mostly be called with at least 1 string that is not english. So the number of calls to localCompare()with 2 english strings should be greatly reduced.

注意：我认为这localCompare()将主要用至少 1 个非英语字符串调用。因此，localCompare()应大大减少使用 2 个英文字符串的调用次数。

Here is the code:

这是代码：

myArray.sort(function(a, b) {
  return (a.name < b.name ? -1 : (a.name > b.name ? 1 : 0));
});

myArray.sort(function(a, b) {
  return a.name.localeCompare(b.name);
});

This solution has the advantage of being short and easy to use. It will be efficient if the array contains mostly english strings. The more non-english strings you have, the less useful the first sort will be. But as it is easy to add in your scripts, it is also easy to see if this approach is worthwile.

该解决方案的优点是简短且易于使用。如果数组主要包含英文字符串，这将是有效的。您拥有的非英语字符串越多，第一种排序的用处就越小。但由于很容易添加到您的脚本中，因此也很容易看出这种方法是否值得。

Now if I were you, I would also use an Intl.Collator, as it is said to be much faster than localCompare()when you have many comparisons to do.

现在如果我是你，我也会使用Intl.Collator，因为据说它比localCompare()你有很多比较要快得多。

回答by Joseph

I don't know you still looking for solution to this problem

我不知道你还在寻找这个问题的解决方案

// Defaulted to ascending
// 1 asc | -1 desc
var direction = 1; 
myArray.sort(function (a, b) {
  return a.name.localeCompare(b.name) === 1 ? direction : -1 * direction;
});

i added a === 1check to your code and this improved perf 400x that means both have comparable perf numbers.

我=== 1在你的代码中添加了一个检查，这个改进的 perf 400x 这意味着两者都有可比的 perf 数字。

Perf numbers with localeCompare arr size: 3200 Avg time took in 10 repetitions : 60 ms

Perf 数字与 localeCompare arr 大小：3200 平均 10 次重复时间：60 毫秒

Perf numbers with > approach. avg time took 55 ms

性能数字与 > 方法。平均时间花费 55 毫秒