MATLAB выполняет оптимизацию хвостового вызова? - PullRequest
Новая
       23

MATLAB выполняет оптимизацию хвостового вызова?

13 голосов
/ 16 марта 2011

Я недавно выучил Haskell и пытаюсь перенести чистый функциональный стиль в мой другой код, когда это возможно. Важным аспектом этого является обработка всех переменных как неизменяемых, то есть констант. Чтобы сделать это, многие вычисления, которые были бы реализованы с использованием циклов в императивном стиле, должны выполняться с использованием рекурсии, что обычно приводит к потере памяти из-за выделения нового стекового кадра для каждого вызова функции. Однако в особом случае хвостового вызова (когда возвращаемое значение вызываемой функции немедленно возвращается вызывающей стороне), это наказание может быть обойдено процессом, называемым оптимизацией хвостового вызова (в одном методе это может быть сделано по существу замена вызова на jmp после правильной настройки стека). MATLAB выполняет TCO по умолчанию или есть способ сообщить об этом?

1 Ответ

11 голосов
/ 16 марта 2011

Если я определю простую хвостовую рекурсивную функцию: 

function tailtest(n)
  if n==0; feature memstats; return; end
  tailtest(n-1);
end

и назовите это так, чтобы оно зашло довольно глубоко: 

set(0,'RecursionLimit',10000);
tailtest(1000);

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

set(0,'RecursionLimit',10000);
tailtest(5000);

тогда (на моей машине, сегодня) MATLAB просто вылетает: процесс бесцеремонно умирает.

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

Итак: Нет, похоже, что MATLAB вообще не выполняет TCO, по крайней мере по умолчанию. Я (пока) не искал варианты, которые могли бы включить его. Я был бы удивлен, если бы были какие-либо.

В тех случаях, когда мы не выбрасываем стек, сколько стоит рекурсия? См. Мой комментарий к ответу Билла Читэма: похоже, что временные затраты нетривиальны, но не безумны.

... За исключением того, что Билл Читам удалил свой ответ после того, как я оставил этот комментарий. ХОРОШО. Итак, я взял простую итеративную реализацию функции Фибоначчи и простую хвостовую рекурсию, выполнив, по сути, одни и те же вычисления в обоих, и рассчитал их обе на fib(60). Рекурсивная реализация работала примерно в 2,5 раза дольше, чем итеративная. Конечно, относительные издержки будут меньше для функций, которые выполняют больше работы, чем одно сложение и одно вычитание за итерацию.

(Я также согласен с мнением Делнана: высокорекурсивный код того типа, который кажется естественным в Хаскеле, в MATLAB, как правило, может быть однотипным.)

...