Использование большой хвостовой рекурсии в Erlang замедляют его?
СТРУКТУРА является типом Абстрактного типа данных, который делит данный блок памяти согласно спецификации структуры. Структуры особенно полезны в сериализации/десериализации файла, поскольку структура может часто писаться в файл дословно. (т.е. Получите указатель на структуру, используйте макрос РАЗМЕРА для вычисления числа байтов для копирования, затем переместите данные в или из структуры.)
Классы являются другим типом абстрактного типа данных, которые пытаются гарантировать сокрытие информации. Внутренне, может быть множество махинаций, методов, временных переменных, переменных состояния. и т.д. это все используется для представления последовательного API любому коду, который хочет использовать класс.
В действительности, структуры о данных, классы о коде.
Однако действительно необходимо понять, что это просто абстракции. Совершенно возможно создать структуры, которые много походят на классы и классы, которые много походят на структуры. На самом деле самые ранние компиляторы C++ были просто предварительными компиляторами, который переводит код C++ в C. Таким образом эти абстракции являются преимуществом для логического мышления, не обязательно активом к самому компьютеру.
Вне того, что каждый - другой тип абстракции, Классы предоставляют решения загадки именования кода C. Так как у Вас не может быть больше чем одной функции, представленной с тем же именем, разработчики раньше следовали за шаблоном _ (). например, mathlibextreme_max (). Путем группировки API в классы подобные функции (здесь мы называем их "методами") могут группироваться и защищаться от именования методов в других классах. Это позволяет программисту организовывать свой код лучше и повторное использование кода увеличения. В теории, по крайней мере.
5 ответов
Итеративная хвостовая рекурсия обычно реализуется с использованием хвостовых вызовов . По сути, это преобразование рекурсивного вызова в простой цикл.
Пример C #:
uint FactorialAccum(uint n, uint accum) {
if(n < 2) return accum;
return FactorialAccum(n - 1, n * accum);
};
uint Factorial(uint n) {
return FactorialAccum(n, 1);
};
-
uint FactorialAccum(uint n, uint accum) {
start:
if(n < 2) return accum;
accum *= n;
n -= 1;
goto start;
};
uint Factorial(uint n) {
return FactorialAccum(n, 1);
};
или даже лучше:
uint Factorial(uint n) {
uint accum = 1;
start:
if(n < 2) return accum;
accum *= n;
n -= 1;
goto start;
};
C # не настоящая хвостовая рекурсия, это потому, что возвращаемое значение изменено, большинство компиляторы не разбивают это на цикл: от
int Power(int number, uint power) {
if(power == 0) return 1;
if(power == 1) return number;
return number * Power(number, --power);
}
до
int Power(int number, uint power) {
int result = number;
start:
if(power == 0) return 1;
if(power == 1) return number;
result *= number;
power--;
goto start;
}
Аналогичная оптимизация, которая отделяет вызовы текстовых функций программы от вызовов функций реализации, называется «встраиванием». В современных / продуманных языках вызовы функций имеют мало отношения к вызовам функций машинного уровня.
В большинстве случаев это не должно влиять на производительность. Вы ищете не просто хвостовые вызовы, а оптимизацию хвостовых вызовов (или устранение хвостовых вызовов). Оптимизация хвостового вызова - это метод компилятора или времени выполнения, который определяет, когда вызов функции эквивалентен «выталкиванию из стека» для возврата к нужной функции, а не просто возврата. Обычно оптимизацию хвостового вызова можно выполнить только тогда, когда рекурсивный вызов является последней операцией в функции, поэтому будьте осторожны.
Дело в том, что Erlang оптимизирует хвостовые вызовы (не только рекурсию). Оптимизировать хвостовые вызовы довольно просто: если возвращаемое значение вычисляется вызовом другой функции, тогда эта другая функция не просто помещается в стек вызовов функции поверх вызывающей функции, а вместо этого помещается кадр стека текущей функции. заменил одной из вызываемых функций. Это означает, что хвостовые вызовы не увеличивают размер стека.
Итак, нет, использование хвостовой рекурсии не замедляет работу Erlang и не создает риска переполнения стека.
С оптимизацией хвостовых вызовов. , вы можете не только использовать простую хвостовую рекурсию, но и взаимную хвостовую рекурсию нескольких функций (хвостовой вызов b, хвостовой вызов c, хвостовой вызов a ...). Иногда это может быть хорошей моделью вычислений.
Существует проблема, относящаяся к хвостовой рекурсии, но она не связана с производительностью - оптимизация хвостовой рекурсии Эрланга также включает в себя устранение трассировки стека для отладки.
Например, см. Пункт 9.13. из часто задаваемых вопросов по Erlang :
Why doesn't the stack backtrace show the right functions for this code:
-module(erl).
-export([a/0]).
a() -> b().
b() -> c().
c() -> 3 = 4. %% will cause badmatch
The stack backtrace only shows function c(), rather than a(), b() and c().
This is because of last-call-optimisation; the compiler knows it does not need
to generate a stack frame for a() or b() because the last thing it did was
call another function, hence the stack frame does not appear in the stack
backtrace.
Это может быть немного неприятно, когда вы попадаете в аварию (но это вроде как в области функционального программирования ...)