Erlang에서 많은 꼬리 추방을 사용하면 속도가 느려 집니까?

StackOverflow https://stackoverflow.com/questions/1105669

  •  12-09-2019
  •  | 
  •  

문제

나는 최근에 Erlang과 반복 루프를 사용하기가 어렵 기 때문에 Tail Recursion이 얼마나 많이 사용되는지에 대해 읽었습니다.

재귀의 높은 사용이 느려지지 않으며, 모든 기능 호출과 스택에 미치는 영향은 무엇입니까? 아니면 꼬리 재귀가 이것의 대부분을 부정합니까?

도움이 되었습니까?

해결책

반복적 인 꼬리 재귀는 일반적으로 사용하여 구현됩니다 꼬리 통화. 이것은 기본적으로 재귀적인 호출을 간단한 루프로 변환 한 것입니다.

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을 늦추지 않으며 스택 오버플로의 위험이 없습니다.

꼬리 통화 최적화를 사용하면 간단한 꼬리 재귀뿐만 아니라 여러 기능의 상호 꼬리 재귀를 사용할 수 있습니다 (꼬리는 꼬리 통화 C가있는 꼬리 통로 B). 이것은 때때로 좋은 계산 모델이 될 수 있습니다.

대부분의 경우 성능에 영향을 미치지 않아야합니다. 당신이 찾고있는 것은 꼬리 통화뿐만 아니라 꼬리 통화 최적화 (또는 꼬리 통화 제거)입니다. 테일 콜 최적화는 컴파일러 또는 런타임 기술로, 함수에 대한 호출이 단지 반환하는 대신 적절한 함수로 돌아 가기 위해 '스택을 팝업'하는 것과 동일합니다. 일반적으로 재귀 호출이 함수의 마지막 작업 일 때만 테일 호출 최적화가 수행 될 수 있으므로 조심해야합니다.

테일 추방과 관련된 문제가 있지만 성능과 관련이 없습니다. Erlang Tail Recursion 최적화에는 디버깅을위한 스택 추적을 제거하는 것도 포함됩니다.

예를 들어, 지점 9.13을 참조하십시오 Erlang FAQ:

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.

충돌을 일으킬 때 이것은 약간의 고통 일 수 있습니다 (그러나 기능적 프로그래밍 영역과 함께 간다 ...)

프로그램 텍스트 기능 호출을 구현 함수 호출에서 분리하는 유사한 최적화는 '인라인'입니다. 현대/사려 깊은 언어에서 기능 호출은 기계 수준 기능 호출과 거의 관련이 없습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top