400-кратное ускорение сортировки путем переключения a.localeCompare(b) на (a<b? -1: (a>b? 1: 0))

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

Мне удалось сократить время сортировки массива ~1700 элементов в Chrome с 1993 до 5 миллисекунд. Почти 400-кратное ускорение. К сожалению, это происходит за счет правильной сортировки неанглийских строк.

Очевидно, я не могу блокировать свой пользовательский интерфейс в течение 2 секунд, когда я пытаюсь сделать сортировку. Могу ли я что-нибудь сделать, чтобы избежать ужасно медленного localeCompare, но при этом поддерживать поддержку локализованных строк?

Answer 1

Значительное улучшение производительности можно получить, предварительно объявив объект-сборщик и используя его метод сравнения. НАПРИМЕР:

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.Collator и использовать функцию, предоставляемую его свойством сравнения". https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

Но если обратиться к справке по Intl.Collator, это показывает, что она не поддерживает firefox / safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator

Вы можете попробовать использовать некоторые опции в localCompare для ускорения работы. Но я только что провел быстрый тест по изменению уровня чувствительности, и похоже, что это не улучшит производительность:

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

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

Answer 4

Попробуйте отсортировать его в 2 этапа:

1. С оператором: как вы сказали, это будет в 400 раз быстрее
2. Затем с localCompare()теперь у этого меньше сравнений, потому что массив в основном отсортирован.

Примечание: я думаю, что localCompare() будет вызываться по крайней мере с 1 строкой, которая не является английской. Так что количество звонков на localCompare() с 2 английскими строками должно быть значительно уменьшено.

Вот код:

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

Преимущество этого решения в том, что оно короткое и простое в использовании. Это будет эффективно, если массив содержит в основном английские строки. Чем больше у вас неанглийских строк, тем менее полезной будет первая сортировка. Но так как это легко добавить в ваши сценарии, также легко увидеть, стоит ли использовать такой подход.

Теперь на вашем месте я бы тоже использовал Intl.Collator, как говорят, намного быстрее, чем localCompare() когда у вас есть много сравнений, чтобы сделать.

Answer 5

Я не знаю, что вы все еще ищете решение этой проблемы

// 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;
});

я добавил === 1 проверьте ваш код, и этот улучшенный perf 400x означает, что оба имеют сравнимые числа perf.

Производственные числа с localeCompare arr size: 3200 Среднее время заняло 10 повторений: 60 мс

Перфоманс с> подходом. среднее время заняло 55 мс