javascript - ordenar - sort method

400x Clasificación de aceleración cambiando a.localeCompare(b) a(a<b?-1:(a> b? 1: 0))

Question

Cambiando una función de orden javascript de

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

a

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

Pude reducir el tiempo para ordenar una matriz de ~ 1700 elementos en Chrome de 1993 milisegundos a 5 milisegundos. Casi una aceleración de 400x. Desafortunadamente, esto es a expensas de ordenar correctamente las cadenas no inglesas.

Obviamente no puedo bloquear mi interfaz de usuario durante 2 segundos cuando intento hacer una ordenación. ¿Hay algo que pueda hacer para evitar la comparación locale horriblemente lenta pero aún así mantener el soporte para cadenas localizadas?

Answer 1

Es difícil saber la clasificación más rápida sin ver los datos que está clasificando. Pero jsperf tiene muchas buenas pruebas que muestran las diferencias de rendimiento entre los tipos de clasificación: http://jsperf.com/javascript-sort/45 http://jsperf.com/sort-algorithms/31

Sin embargo, ninguno de estos cuenta para cadenas localizadas, y me imagino que no hay una manera fácil de ordenar cadenas localizadas y localeCompare es probablemente la mejor solución para esto.

Al consultar la referencia de mozilla, se dice: "Al comparar un gran número de cadenas, como en la clasificación de matrices grandes, es mejor crear un objeto Intl.Collator y usar la función proporcionada por su propiedad de comparación". https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

Pero al ir a la referencia de Intl.Collator, se muestra que no es compatible con firefox / safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator

podría intentar usar algunas de las opciones en localCompare para acelerar el rendimiento. Pero acabo de hacer una prueba rápida para cambiar el nivel de sensibilidad y parece que no mejorará el rendimiento:

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

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

Answer 2

Intenta ordenarlo en 2 pasos:

1. Con el operador: como dijiste, será 400 veces más rápido
2. Luego con localCompare() : esto ahora tiene menos comparaciones que hacer porque la matriz está ordenada en su mayoría.

Nota: Creo que a la mayoría de los localCompare() se les llamará localCompare() con al menos 1 cadena que no sea inglés. Por lo tanto, el número de llamadas a localCompare() con 2 cadenas en inglés debería reducirse considerablemente.

Aquí está el código:

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

Esta solución tiene la ventaja de ser corta y fácil de usar. Será eficiente si la matriz contiene principalmente cadenas en inglés. Cuantas más cadenas no inglesas tengas, menos útil será la primera ordenación. Pero como es fácil de agregar en sus scripts, también es fácil ver si este enfoque vale la pena.

Ahora, si fuera tú, también usaría un https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator , ya que se dice que es mucho más rápido que https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare cuando tienes muchas comparaciones que hacer.

Answer 3

No sé si todavía estás buscando una solución a este problema.

// 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 un === 1 cheque a tu código y este rendimiento mejorado 400x significa que ambos tienen números de rendimiento comparables.

Números de rendimiento con localeCompare arr tamaño: 3200 Tiempo promedio en 10 repeticiones: 60 ms

Números de rendimiento con> enfoque. el tiempo promedio tomó 55 ms

Answer 4

Se puede obtener una gran mejora en el rendimiento declarando el objeto del recopilador de antemano y utilizando su método de comparación. P.EJ:

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

Aquí hay un guión de referencia comparando los 3 métodos:

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'');
arr2.sort((a, b) => (a < b ? -1 : (a > b ? 1 : 0)));
console.timeEnd(''#3 - non-locale'');

Answer 5

Un enfoque efectivo que encontré al tratar con la mayoría de los caracteres latinos es usar el operador cuando ambas cadenas coincidan con una expresión regular específica. Por ejemplo: / /^[/w-./s,]*$/

Es mucho más rápido si ambas cadenas coinciden con la expresión, y en el peor de los casos, parece ser un poco más lento que llamar ciegamente localeCompare.

Ejemplo aquí: http://jsperf.com/operator-vs-localecompage/11