Вопрос по статье оптимизации хвостового вызова

У меня есть вопрос относительно этой статьи.

Между этим кодом

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

и этот код

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) Я смущен тем, насколько это помогает. Есть ли у второго фрагмента просто хвостовой вызов, который создает меньше накладных расходов, потому что он вычисляет то, что ему нужно, прежде чем он снова вызовет себя, или есть что-то еще, что я упускаю?

Насколько я понимаю, хвостовой вызов все еще не устранен, а только оптимизирован.

2) И почему вообще должны быть odds и odds1? Мне тоже до сих пор непонятно.


javascript optimization article tail-recursion
person JustcallmeDrago    schedule 16.01.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

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

Насколько я понимаю, хвостовой вызов все еще не устранен, а только оптимизирован.

Если конец процедуры выглядит так:

push args
call foo
return

Затем компилятор может оптимизировать это, чтобы просто

jump startOfFoo

Полностью исключить вызов процедуры.

И почему вообще должны быть шансы и шансы1? Мне тоже до сих пор непонятно.

Контракт odds указывает только два аргумента — третий аргумент — это просто деталь реализации. Таким образом, вы прячете это во внутреннем методе и представляете оболочку в качестве внешнего API.

Вы могли бы назвать odds1 как-то вроде oddsImpl, и, я думаю, это прояснит ситуацию.

person Anon.    schedule 16.01.2011
comment
Но верно ли это для javascript? AFAIK, оптимизация/устранение хвостового вызова не входит в определение javascript, поэтому это нужно делать вручную. Так действительно ли это будет оптимизировано?? - person JustcallmeDrago; 16.01.2011
comment
@JustcallmeDrago: не увидел тег Javascript, извините. Если вы прочитаете сообщение в блоге дальше по странице (grep для Начиная с JavaScript), вы заметите, что автор комментирует отсутствие в JS исключения хвостовых вызовов и объясняет, как это работает в языках, которые обрабатывают это должным образом. Кроме того, похоже, что исключение хвостового вызова возможно, если указано use strict, поэтому, даже если это не обязательно в стандарте, вероятно, некоторые механизмы Javascript оптимизируют его. - person Anon.; 17.01.2011
comment
Ах, так это определенно лучше, но все же не идеально (бесконечно рекурсивно). Спасибо. - person JustcallmeDrago; 17.01.2011
comment
О, это также означает, что создание как можно меньшего количества переменных поможет, или нет? Не будет ли память оставаться там до тех пор, пока функция не вернется, что означает, что любые созданные переменные будут увеличивать накладные расходы? - person JustcallmeDrago; 17.01.2011
comment
@JustcallmeDrago: память, используемая отдельными переменными, довольно несущественна. Если вы объявляете достаточно переменных в одной функции, чтобы это стало проблемой, у вас есть проблемы посерьезнее, чем беспокойство о памяти. - person Anon.; 17.01.2011

arrow_upward
1
arrow_downward

Первая версия не является хвостовой рекурсией, потому что после получения значения odds(n - 1, p - 1) оно должно затем умножить его на (n / p) вторая версия перемещает это в вычисление параметров для функции odds1, чтобы сделать ее правильно рекурсивной.

Если вы посмотрите на стек вызовов, то первый будет выглядеть так:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

тогда как второй будет:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

поскольку вы просто возвращаете значение рекурсивного вызова, компилятор может легко оптимизировать это:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

Причина наличия odds и odds1 заключается в том, чтобы просто предоставить начальное значение аккумулятора, когда другой код вызывает эту функцию.

person Nemo157    schedule 16.01.2011

arrow_upward
1
arrow_downward

Оптимизация хвостовой рекурсии выглядит следующим образом: в первом примере, поскольку вы не можете вычислить результат умножения return (n / p) * odds(n - 1, p - 1), пока не вызовете шансы (n-1), интерператор должен удерживать нашу текущую позицию в памяти (в стеке) , и открыть новый вызов шансов.

Рекурсивно это произойдет и при следующем вызове, и после него, и так далее. Таким образом, к тому времени, когда мы достигнем конца нашей рекурсии и начнем возвращать значения и вычислять продукты, у нас будет n незавершенных операций.

Во втором примере, поскольку выполняемый оператор return просто return odds1(n - 1, p - 1, (n / p) * acc), мы можем вычислить аргументы функции и просто вызвать коэффициент 1(n-1) без сохранения текущей позиции. вот где оптимизация, потому что теперь мне не нужно помнить, где я нахожусь каждый раз, когда я открываю новый кадр в стеке.

Думайте об этом как о ссылках на книги. представьте, что вы открываете поваренную книгу и переходите к определенному рецепту, а ингредиенты перечислены следующим образом:

  1. соль
  2. ингредиенты на следующей странице

на следующей странице есть

  1. перец
  2. ингредиенты на следующей странице

и т.д. как узнать все ингредиенты? вы должны помнить, что вы видели на каждой странице!

хотя второй пример больше похож на следующий список ингредиентов:

  1. соль
  2. забудьте об этом, просто используйте то, что вы видите на следующей странице

на следующей странице есть:

  1. соль
  2. перец
  3. забудьте об этом, просто используйте то, что вы видите на следующей странице

и т. д. к тому времени, когда вы дойдете до последней страницы (обратите внимание, что аналогия точна в том, что обе функции вызывают одинаковое количество вызовов), у вас есть все ингредиенты, и вам не нужно «хранить в памяти» то, что вы видели на каждой странице, потому что все это есть на последней странице!

person davin    schedule 16.01.2011