400x ordinamento Speedup commutando a.localeCompare (b) a (un <b?-1:(a> b 1: 0))

Question

Passando una funzione di ordinamento JavaScript dal

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

ho potuto per ridurre il tempo necessario per ordinare un array di elementi ~ 1700 in Chrome dal 1993 in millisecondi a 5 millisecondi. Quasi un aumento di velocità di 400x. Purtroppo questo è a scapito del corretto ordinamento di stringhe non inglesi.

Ovviamente non riesco a bloccare l'interfaccia utente per 2 secondi quando provo a fare un ordinamento. C'è qualcosa che posso fare per evitare il localCompare orribilmente lento ma mantenere ancora il supporto per le stringhe localizzate?

Answer 1

È difficile conoscere l'ordinamento più veloce senza visualizzare i dati che si stanno ordinando. Ma jsperf ha un sacco di buone prove che mostrano le differenze di prestazioni tra i tipi di ordinamento: http://jsperf.com/javascript-sort/45 http://jsperf.com/sort-algorithms/31

Tuttavia nessuno di questi per conto stringhe localizzate, e mi immagino non v'è alcun modo semplice per ordinare le stringhe localizzate e localeCompare è probabilmente la migliore soluzione per questo.

Guardando riferimento Mozilla è dice: "Quando si confrontano un gran numero di stringhe, come ad esempio in grandi array di ordinamento, è meglio creare un oggetto Intl.Collator e utilizzare la funzione fornita dalla sua proprietà confrontare." https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare

Ma andando al Intl.Collator riferimento dimostra che non è il supporto per Firefox/safari https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator

si potrebbe provare a utilizzare alcune delle opzioni su localCompare per accelerare le prestazioni. Ma ho appena fatto un test rapido che cambia il livello di sensibilità e sembra come se non migliorerà le prestazioni:

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

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

Answer 2

io non ti conosco ancora alla ricerca di una soluzione a questo 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; 
}); 

ho aggiunto un controllo === 1 al codice e questo migliorata perf 400x questo significa che entrambi hanno i numeri perf comparabili.

numeri Perf con localeCompare dimensioni arr: 3200 tempo Avg preso a 10 ripetizioni: 60 ms

numeri Perf con approccio>. avg tempo impiegato 55 ms

Answer 3

Un approccio efficace che ho trovato quando si tratta di caratteri/principalmente/latini è quello di utilizzare l'operatore ogni volta che entrambe le stringhe corrispondono a un'espressione regolare specifica. EG: /^[\w-.\s,]*$/

È molto più veloce se entrambe le stringhe corrispondono all'espressione, e nella peggiore delle ipotesi sembra essere leggermente più lento di chiamare ciecamente localeCompare.

Esempio qui: http://jsperf.com/operator-vs-localecompage/11

Answer 4

Prova di smistamento in 2 fasi:

1. Con l'operatore: come lei ha detto, sarà 400 volte più veloce
2. Poi, con localCompare(): questo ha ora meno confronti da fare perché l'array è in gran parte ordinato.

Nota: penso che il numero localCompare() verrà chiamato per lo più con almeno una stringa che non è inglese. Quindi il numero di chiamate a localCompare() con 2 stringhe inglesi dovrebbe essere notevolmente ridotto.

Ecco il codice:

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

Questa soluzione ha il vantaggio di essere breve e facile da usare. Sarà efficiente se l'array contiene stringhe prevalentemente inglesi. Più stringhe non inglesi hai, meno utile sarà il primo tipo. Ma poiché è facile aggiungere gli script, è anche facile vedere se questo approccio è utile.

Ora, se fossi in te, vorrei anche utilizzare un Intl.Collator, come si è detto di essere molto più veloce di localCompare() quando si hanno molti paragoni da fare.