JavaScript degradacja wydajności rekurencyjna funkcja

Question

jakie poczyniono następujące pytanie podczas testu umiejętności procesu rekrutacji:

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

dlaczego tak się stopniowo wolniejszy jako oo uzyskać wyższy? zaproponuj lepszą wersję , zachowując jej rekurencję.

I chcę poznać odpowiedź tylko po to, aby się o tym dowiedzieć. Odpowiedziałem, że robi się wolniej, ponieważ wraz z wzrasta liczba wywołań rekursywnych również wzrasta, ale nie mogłem zapewnić lepszej wersji. Ponadto nie wiem, czy istnieje jakikolwiek inny powód, dla którego funkcja staje się wolniejsza, gdy z jest wyższe.

Answer 1

Prawidłowa odpowiedź brzmiałaby: "Powinno to być , a nie postępować wolniej, gdy z jest wyższe". W rzeczywistości nie ma to miejsca w moich prostych testach. Moje testy przepełniają stos zanim jakiekolwiek spowolnienie będzie widoczne.

Nie mogę sobie wyobrazić alternatywnego sposobu napisania funkcji przy zachowaniu jej rekursywności.

Answer 2

Ponieważ JavaScript nie ma prawdziwych połączeń typu tail (jeszcze), to, czego doświadczasz, nie jest spowolnieniem w oparciu o wartość z, ale spowolnieniem opartym na wzroście stosu i niemożności czyszczenia śmieciarki (GC) stos zakresów niezbędnych do zachowania tej funkcji.

Teoretycznie można zmienić to zachowanie, używając polecenia setImmediate i wzorca zwrotnego, aby rozwiązać ten problem. Użycie polecenia setImmediate pozwala, aby zakres bieżącej pętli wykonawczej wypadł z użycia i został zebrany podczas następnego cyklu GC.

Tak, coś takiego:

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

Ale to nie będzie działać, ponieważ oo jest przekazywana do zakresu setImmediate a tym samym poprzedni zakres X nie może być prawidłowo GC'd.

Zamiast tego trzeba użyć Iife (bezpośrednio Wykonano wyrażenie funkcyjne), aby osiągnąć to, czego szukasz w połączeniu z użyciem setImmediate aby umożliwić cykl realizacji, aby mieć czas, aby umożliwić GC:

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

zakazu wszelkich literówki Myślę, że mam powyższe poprawne. Oczywiście, jeśli używasz ES6, możesz to również skrócić.

Drugą stroną tego równania jest efekt buforowania w pliku console.log, a rozmiar bufora zmienia się w zależności od tego, co dzieje się w przeglądarce. W terminalu OS koszty te zostaną zminimalizowane, ponieważ przewijanie bufora wstecznego jest ograniczone, a bufor zwrotny jest wstępnie przydzielany i ponownie wykorzystywany.