algorithm тег - Что такое оптимизация хвостового звонка?




пример стоп (8)

Проблема с рекурсивными функциями имеет проблему. Он создает стек вызовов размера O (n), что делает нашу общую стоимость памяти O (n). Это делает его уязвимым для ошибки переполнения стека, где стек вызовов становится слишком большим и заканчивается из пространства. Оптимизация затрат на хвост (TCO). Там, где он может оптимизировать рекурсивные функции, чтобы не создавать высокий стек вызовов и, следовательно, экономить стоимость памяти.

Есть много языков, которые делают TCO как (Javascript, Ruby и несколько C), где Python и Java не делают TCO.

Язык JavaScript подтвердил использование: http://2ality.com/2015/06/tail-call-optimization.html

Очень просто, что такое оптимизация хвостового вызова? В частности, может ли кто-нибудь показать некоторые небольшие фрагменты кода, где он может быть применен, а где нет, с объяснением причины?


  1. Мы должны убедиться, что в самой функции нет операторов goto. Позаботился о том, чтобы вызов функции был последним в функции вызываемого абонента.

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

  3. TCO может вызвать непрерывную работу:

    void eternity()
    {
        eternity();
    }
    

Прежде всего обратите внимание на то, что не все языки поддерживают его.

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

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


Оптимизация Tail-call - это то, где вы можете избежать выделения нового фрейма стека для функции, потому что вызывающая функция просто вернет значение, которое оно получает от вызываемой функции. Чаще всего используется хвостовая рекурсия, где рекурсивная функция, написанная для использования оптимизации хвостового вызова, может использовать постоянное пространство стека.

Схема - один из немногих языков программирования, которые гарантируют в спецификации, что любая реализация должна обеспечить эту оптимизацию (JavaScript также начинается с ES6) , так что вот два примера факториальной функции в Схеме:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

Первая функция не является хвостовой рекурсивной, так как при рекурсивном вызове функция должна отслеживать умножение, которое необходимо выполнить с результатом после возврата вызова. Таким образом, стек выглядит следующим образом:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

Напротив, трассировка стека для хвостового рекурсивного факториала выглядит следующим образом:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Как вы можете видеть, нам нужно всего лишь отслеживать один и тот же объем данных для каждого звонка на хвост факта, потому что мы просто возвращаем значение, которое мы получаем до самого верха. Это означает, что даже если я должен был позвонить (факт 1000000), мне нужно только то же пространство, что и (факт 3). Это не относится к не-хвостовому рекурсивному факту, и поскольку такие большие значения могут привести к переполнению стека.


Смотри сюда:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

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


Давайте рассмотрим простой пример: факториальная функция, реализованная в C.

Начнем с очевидного рекурсивного определения

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Функция заканчивается хвостовым вызовом, если последняя операция перед возвратом функции - это другой вызов функции. Если этот вызов вызывает ту же функцию, он является хвостовым рекурсивным.

Несмотря на то, что fac() выглядит на первый взгляд хвостовым рекурсивным, это не то, что на самом деле происходит

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

т.е. последняя операция - это умножение, а не вызов функции.

Тем не менее, можно переписать fac() как хвост-рекурсивный, передав накопленное значение по цепочке вызовов в качестве дополнительного аргумента и снова передав только конечный результат в качестве возвращаемого значения:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

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

Оптимизация хвостового вызова преобразует наш рекурсивный код в

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Это может быть включено в fac() и мы достигаем

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

что эквивалентно

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

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


Вероятно, лучшее описание высокого уровня, которое я нашел для хвостовых вызовов, рекурсивных хвостовых вызовов и оптимизации хвостового звонка - это сообщение в блоге

«Какая черта: хвост»

Дэн Сугалски. По оптимизации хвостового вызова он пишет:

Рассмотрим на мгновение эту простую функцию:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Итак, что вы, или, скорее, ваш компилятор языка? Ну, что он может сделать, это повернуть код формы return somefunc(); в pop stack frame; goto somefunc(); последовательности нижнего уровня pop stack frame; goto somefunc(); pop stack frame; goto somefunc(); , В нашем примере это означает, что до того, как мы назовем bar , foo очистится, а затем вместо того, чтобы вызывать bar в качестве подпрограммы, мы выполняем операцию goto с низким уровнем в начало bar . Foo уже очистился от стека, поэтому при запуске bar похоже, что тот, кто вызвал foo , действительно вызвал bar , и когда bar возвращает свое значение, он возвращает его непосредственно тому, кто вызвал foo , вместо того, чтобы возвращать его в foo который затем верните его вызывающему абоненту.

А на хвостовой рекурсии:

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

Чтобы это:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

тихо превращается в:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Что мне нравится в этом описании, так это то, насколько кратким и легким оно должно быть понято для тех, кто приходит с императивного языкового фона (C, C ++, Java)


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

В хвостовой рекурсии вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результаты вашего текущего шага на следующий рекурсивный шаг. Это приводит к тому, что последний оператор находится в форме (return (recursive-function params)) . В принципе, возвращаемое значение любого заданного рекурсивного шага совпадает с возвращаемым значением следующего рекурсивного вызова .

Следствием этого является то, что, как только вы готовы выполнить свой следующий рекурсивный шаг, вам больше не нужен текущий стек кадров. Это позволяет оптимизировать. Фактически, с соответствующим образом написанным компилятором, у вас никогда не должно быть сверкающего переполнения стека с хвостовым рекурсивным вызовом. Просто повторите использование текущего кадра стека для следующего рекурсивного шага. Я почти уверен, что Lisp делает это.





algorithm recursion language-agnostic tail-recursion tail-call-optimization