通过将a.localeCompare(b)切换为(a <b？-1:(a> b？1:0))进行400x排序加速

Question

通过切换javascript排序函数

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

至

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

我能够缩短在Chrome中对~1700元素阵列进行排序的时间,从1993毫秒到5毫秒.几乎是400倍的加速.不幸的是,这是以正确排序非英语字符串为代价的.

当我尝试进行排序时,显然我无法阻止我的UI阻塞2秒.有什么我可以做的,以避免可怕的缓慢localeCompare但仍然保持对本地化字符串的支持？

Answer 1

通过预先声明collat​​or对象并使用它的比较方法,可以获得很好的性能提升.例如:

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

这是一个比较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');

Answer 2

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

如果两个字符串匹配表达式会快得多,而在最坏的情况下,它似乎比盲目调用localeCompare稍慢.

示例:http://jsperf.com/operator-vs-localecompage/11

Answer 3

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

然而,这些都没有解释本地化字符串,我认为没有简单的方法来排序本地化字符串,localeCompare可能是最好的解决方案.

看一下mozilla的引用说:"在比较大量字符串时,例如在排序大型数组时,最好创建一个Intl.Collat​​or对象并使用其compare属性提供的函数." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

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

您可以尝试使用localCompare上的一些选项来加速性能.但我刚刚做了一个快速测试,改变了灵敏度水平,似乎不会改善性能:

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

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