2016-02-16 20 views
9

che è stata resa alla seguente domanda nel corso di una prova di abilità processo di assunzione:Javascript degrado delle prestazioni ricorsiva funzione

var x = function(z) { 
    console.log(z);  
    if (z > 0) { 
     x(z-1); 
    } 
}; 

perché questo è progressivamente più lento come z ottenere più elevati? proporre una versione migliore di , mantenendola ricorsiva.

E voglio sapere la risposta solo per conoscerla. Ho risposto che è più lento perché con z aumenta anche il numero di chiamate ricorsive, ma non ho potuto fornire una versione migliore. Inoltre, non so se ci sia un ulteriore motivo per cui la funzione diventi più lenta man mano che z diventa più alto.

+5

È necessario più tempo perché si registra più spesso sulla console? È davvero difficile immaginare cosa volessero sentire. Glielo hai chiesto? – Bergi

+0

No, non sono ancora riuscito a chiederlo ma lo farò se posso. – beni0888

+1

Se in effetti significano che questo è esponenzialmente più lento per un numero elevato di 'z' rispetto ai numeri piccoli, l'unica vera ragione sarebbe che le funzioni in cima a grandi stack di chiamate sarebbero eseguite in qualche modo sempre più lentamente; che lo stack di chiamate accumulasse in qualche modo un sovraccarico. Questo ovviamente dipende molto dall'implementazione di Javascript. Hai eseguito dei test per confermare che questo in effetti rallenta? – deceze

risposta

11

La risposta corretta sarebbe stata "È necessario che non sia progressivamente più lento quando z diventa più alto". In realtà, non è nei miei semplici test. I test superano lo stack prima che sia visibile qualsiasi rallentamento.

Non riesco a immaginare un modo alternativo di scrivere la funzione pur mantenendo la sua natura ricorsiva.

+0

stavo sfiorando [Duff's Device] (http://eemyop.blogspot.co.uk/2013/05/duffs-device-in-javascript-optimization.html) vedi se questa potrebbe essere una risposta sensata, ma provare a farlo ricorsivamente genera un errore di 'Troppo ricorsione' con' x (1000) '. Penso che questo potrebbe essere stato a cui la domanda stava accennando, ma penso che la tua risposta sia corretta. –

1

Dal momento che JavaScript non ha chiamate tail tail (ancora) ciò che si sta verificando non è un rallentamento basato sul valore di z ma un rallentamento basato sulla crescita dello stack e sull'incapacità del garbage collector (GC) di ripulire la pila di ambiti necessari per conservare questa funzionalità.

In teoria, è possibile modificare questo comportamento utilizzando setImmediate e il pattern di callback da risolvere per questo. L'utilizzo di setImmediate consente di escludere l'ambito del ciclo di esecuzione corrente e di essere raccolto durante il successivo ciclo GC.

Quindi, qualcosa di simile:

var x = function x(z){ 
    console.log(z);  
    if (z > 0) { 
     setImmediate(function(){ 
      x(z-1); 
     }); 
    } 
}; 

Ma questo non funzionerà perché z è tramandata nel campo di applicazione per setImmediate e quindi la portata precedente di x non può essere GC'd correttamente.

Invece si deve usare IIFE (immediatamente Invocato Espressione Funzione) per ottenere ciò che si sta cercando in combinazione con l'utilizzo di setImmediate per consentire il ciclo di esecuzione per avere il tempo per consentire GC:

var x = function x(z){ 
    console.log(z);  
    if (z > 0) { 
     setImmediate((function(newZ){ 
      return function(){ 
      x(newZ); 
      }; 
     })(z-1)); 
    } 
}; 

Escludendo qualsiasi errori di battitura penso di aver capito correttamente. Ovviamente se usi ES6 puoi anche abbreviare molto questo.

L'altro lato di questa equazione è l'effetto di spooling di console.log e il buffer ridimensiona il tuo andare a incorrere per farlo in un browser. In un terminale OS questi costi saranno ridotti al minimo in quanto lo scorrimento del backbuffer è limitato e il back buffer viene pre-allocato e riutilizzato.