Javascript Деградация рекурсивной функции производительность

Я сделал следующий вопрос во время теста навыков процесса найма:Javascript Деградация рекурсивной функции производительность

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

почему это прогрессивно медленнее, г получить выше? предложите лучшую версию , сохраняя ее рекурсивной.

И я хочу знать ответ, чтобы узнать об этом. Я ответил, что он замедляется, потому что, поскольку z увеличивает количество рекурсивных вызовов, тоже увеличивается, но я не могу предоставить лучшую версию. Кроме того, я не знаю, есть ли еще одна причина, по которой функция становится медленнее, когда z становится выше.

источник

2016-02-16 beni0888

Требуется больше времени, потому что он чаще всего входит в консоль? Трудно представить, что они хотели услышать. Вы спросили их? – Bergi

Нет, я еще не мог их спросить, но я сделаю это, если смогу. – beni0888

Если они действительно означают, что это экспоненциально медленнее для больших чисел 'z', чем для небольших чисел, единственной реальной причиной этого было бы то, что функции на вершине больших стеков вызовов каким-то образом выполнялись бы все медленнее; что стек вызовов каким-то образом накапливается накладные расходы. Это, очевидно, сильно зависит от реализации Javascript. Проводили ли вы какие-либо тесты, чтобы подтвердить, что это фактически замедляется? – deceze

Правильный ответ был бы: «Должно быть, не будет постепенно замедляться по мере роста z». На самом деле, это не в моих простых тестах. Мои тесты переполняют стек до того, как будет замечено замедление.

Я не могу представить альтернативный способ записи функции при сохранении ее рекурсивного характера.

источник

2016-02-16 16:50:29

Я расчесывал [устройство Даффа] (http://eemyop.blogspot.co.uk/2013/05/duffs-device-in-javascript-optimization.html) на посмотрите, может ли это быть разумным ответом, но попытка сделать это рекурсивно выдает ошибку «слишком много рекурсии» с помощью «x (1000)». Я думаю, что это, возможно, и намекал, но я думаю, что ваш ответ верен. –

Поскольку JavaScript не имеет настоящих хвостовых вызовов (пока), то, что вы испытываете, не является замедлением на основе значения z, а замедлением на основе роста стека и невозможностью сбора сборщика мусора (GC) для очистки стек областей, необходимых для сохранения этой функциональности.

В теории вы можете изменить это поведение, используя setImmediate и обратный шаблон, чтобы решить эту проблему. Использование setImmediate позволяет исключить область действия цикла выполнения и собираться в течение следующего цикла GC.

Так, что-то вроде:

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

Но это не будет работать, так как г передается вниз в область для setImmediate и, таким образом, предыдущий объем х не может быть GC'd правильно.

Вместо этого вы должны использовать IIFE (Сразу Вызывается функция Expression), чтобы добиться того, что вы ищете в сочетании с использованием setImmediate, чтобы цикл выполнения, чтобы иметь время, чтобы позволить GC:

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

запрета вызовов любой опечатки, я думаю, что я правильно понял. Конечно, если вы используете ES6, вы также можете сократить это.

Другая сторона этого уравнения - это эффект буферизации console.log, и размер буфера изменяет ваш размер, чтобы сделать это в браузере. В терминале ОС эти затраты будут минимизированы по мере того, как прокрутка буфера будет ограничена, а задний буфер предварительно выделен и повторно использован.

источник

2016-02-17 18:40:51 jdarling

Javascript Деградация рекурсивной функции производительность

ответ

Смежные вопросы