JavaScript, l'ordinamento con il secondo parametro è più veloce

Question

Ho fatto un piccolo test e ho scoperto che array.sort(function(a, b) { return a - b; }); è molto più veloce di array.sort(); in JavaScript.

I risultati sono stati piuttosto scioccanti, circa 1,7 volte più veloci in IE9, 1,6 volte in FF7 e 6,7 volte in Chrome.

Inoltre, implementando quicksort da solo in JS, ho scoperto che era ancora più veloce di entrambi i metodi sopra menzionati. (Due diverse implementazioni, una accetta una funzione di confronto come parametro, l'altra no. Entrambe erano più veloci.)

Esiste qualche spiegazione ragionevole?

EDIT: I miei implementazioni:

No di confronto:

function quickSort(array, from, to) { 
    if(typeof from === 'undefined') { 
     from = 0; 
     to = array.length - 1; 
    } 
    else if(typeof to === 'undefined') { 
     to = array.length - 1; 
    } 

    if(to - from < 1) { 
     return; 
    } 

    var i = from, pivot = to, t; 

    while(i < pivot) { 
     if(array[i] > array[pivot]) { 
      t = array[i]; 
      array[i] = array[pivot - 1]; 
      array[pivot - 1] = array[pivot]; 
      array[pivot] = t; 
      pivot--; 
     } 
     else { 
      i++; 
     } 
    } 

    quickSort(array, from, pivot - 1); 
    quickSort(array, pivot + 1, to); 
} 

Con di confronto:

function quickSortFunc(array, sortfunc, from, to) { 
    if(typeof from === 'undefined') { 
     from = 0; 
     to = array.length - 1; 
    } 
    else if(typeof to === 'undefined') { 
     to = array.length - 1; 
    } 

    if(to - from < 1) { 
     return; 
    } 

    var i = from, pivot = to, t; 

    while(i < pivot) { 
     if(sortfunc(array[i], array[pivot]) > 0) { 
      t = array[i]; 
      array[i] = array[pivot - 1]; 
      array[pivot - 1] = array[pivot]; 
      array[pivot] = t; 
      pivot--; 
     } 
     else { 
      i++; 
     } 
    } 

    quickSortFunc(array, sortfunc, from, pivot - 1); 
    quickSortFunc(array, sortfunc, pivot + 1, to); 
} 

Answer 1

Ci sono due fattori che entrano in gioco:

In primo luogo, come Felix Re menzionato nei commenti, il metodo di ordinamento nativo converte ogni membro dell'array in una stringa prima di confrontare. L'utilizzo di function(a, b) { return a - b; } è molto più veloce se tutti i (o più) membri dell'array sono numeri.

In secondo luogo, l'algoritmo di ordinamento è implementation dependent. Come puoi o non potresti sapere, quicksort si comporta davvero male se inserisci un nuovo elemento in una matrice già ordinata. Forse è per questo che WebKit ha deciso di implementare Selection Sort.

Ma non temere, l'aiuto è vicino! Qualcuno già forked WebKit to fix this

Answer 2

Molte ragioni entrano in gioco. Non dover controllare il tipo di variabile è uno di questi e solo uno di essi. E la tua implementazione rende felice l'ottimizzatore. Funziona con array denso, funziona solo con i numeri, le variabili sono ben definite e riutilizzate. No, no, no, nessuna variabile magica, proprietà, funzioni o tipi. Ottimizzerebbe bene.

Tuttavia, se si è tentato di implementare i metodi di tipo ideendent, ordine indipendente come reverse(), è possibile che la propria implementazione sia più veloce. Almeno il mio è.

Perché?

JavaScript è fortemente ottimizzato al giorno d'oggi, in particolare su loop e operazioni ripetute su stesso tipo di materiale: numero, stringa, persino oggetti di stessa forma (è complicato). In casi estremi il runtime allineerebbe le tue funzioni, salverebbe i controlli di tipo variabile e, in caso di Chrome, manterrebbe i tuoi numeri nei registri in modo che il tuo loop possa essere veloce come C.

Wow.

Ma queste ottimizzazioni sono decollate solo negli ultimi anni. Al momento, le funzioni native non sono ancora ottimizzabili come il codice utente. Non subiscono altrettante ottimizzazioni dinamiche come fa il codice utente.

Lì, l'ho detto.

Attualmente, il codice utente può essere eseguito più velocemente dell'implementazione nativa, soprattutto perché il programmatore sa quale flusso di dati in esso.Ma questo può essere temporaneo.

Mi fermo qui e ti faccio decidere se vuoi creare la tua libreria di array. ;)

Answer 3

Questa è un'ipotesi molto approssimativa, ma potrebbe verificarsi il colpo di prestazioni dovuto all'ordinamento nativo, controllando se gli attributi passati sono vuoti o nulli ... Quindi cercare la funzione predefinita su ogni ricerca (invece di una volta) ...

potrebbe essere un problema di ottimizzazione sbagliata, che potrebbe essere risolto se vero ... Speriamo che qualcuno in Firefox dev può rispondere a questa :)