좋아하는 언어는 어떻게 깊은 재귀를 처리합니까? [닫은
https://stackoverflow.com/questions/233013
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 최근에 Python을 배우기 시작했고 기본적으로 1000 개의 깊은 재귀 제한을 발견 한 것에 놀랐습니다. 약 30000 정도를 충분히 높이면 C와 같은 세그먼트 화 결함으로 충돌합니다.
(파이썬 사람들은 항상 재귀 기능을 반복적 인 기능으로 변환 할 수 있고 항상 더 빠른 기능을 신속하게 지적합니다. 그것은 100% 사실입니다. 실제로 내 질문에 관한 것이 아닙니다.)
나는 Perl에서 동일한 실험을 시도했고 약 1 천만 개의 재귀를 시도했습니다. 그것은 4 개의 RAM을 모두 소비했으며 ^C를 사용하여 시도를 중단했습니다. 분명히 PERL은 C 스택을 사용하지 않지만 재발 할 때 말도 안되는 양의 메모리를 사용합니다.
나는 파이크에서 시도했고 약 2 초 안에 10 만,000,000 개의 재귀를 얻는 것에 완전히 놀랐습니다. 나는 그것이 어떻게 그렇게했는지 전혀 모른다. 그러나 나는 그것이 반복적 인 과정으로 재귀를 평평하게했다고 생각한다. [참고 : Pike는 사소한 사례를 평평하게하지만 더 복잡한 사례에 대한 segfaults를 수행합니다.
나는이 그렇지 않으면 쓸모없는 기능을 사용했습니다.
int f(int i, int l) { if(i<l) return f(i+1,l); return i; }
sub f { return f($_[0]+1, $_[1]) if $_[0]<$_[1]; return $_[0] };
def f(i,l):
if i<l:
return f(i+1,l)
return i
다른 언어 (예 : PHP, Ruby, Java, Lua, Ocaml, Haskell)가 재귀를 처리하고 왜 그런 식으로 처리하는지 매우 궁금합니다. 또한 함수가 "테일 리퍼 셔티"인 경우 차이가 있는지 여부를 확인하십시오 (주석 참조).
해결책
"파이썬 사람들은 항상 재귀 기능을 반복적 인 기능으로 변환 할 수 있으며 항상 더 빠른 기능을 빠르게 지적합니다."
이것은 사실이지만, 실제로 모든 것이 쉽다면 왜 Python이 저를 위해 그것을하지 않기 때문에 내 코드가 가능한 한 간단하게 보일 수 있습니까? (나는 이것을 파이썬 구현자를 슬램하지 않고 답이 문제를 설명하기 때문에 말한다).
재귀 최적화는 14 세기 또는 그 이후로 기능적 언어로 존재했습니다. Haskell, CAML, LISP 구현은 일반적으로 적어도 적어도 꼬리 재귀 함수를 반복으로 변환합니다. 기본적으로 가능하다는 것을 발견함으로써이를 수행합니다. 즉, 재귀 호출 후에 반환 값 이외의 다른 변수가 사용되지 않도록 함수가 재 배열 될 수 있음을 발견합니다. . 리턴 전에 재귀 반환 값에 대한 작업이 완료된 경우 가능하게하는 한 가지 트릭은 추가 "Accumulator"매개 변수를 소개하는 것입니다. 간단한 관점에서 이것은 "UP"의 방식 대신 "다운"으로 효과적으로 작업을 수행 할 수 있음을 의미합니다. 자세한 내용은 '기능 테일 리커 셔티브를 만드는 방법'을 검색합니다.
꼬리 재귀 함수를 루프로 바꾸는 실제 세부 사항은 기본적으로 호출 컨벤션을 사용하여 매개 변수를 설정하고 기능의 시작 부분으로 다시 점프하여 모든 것을 저장하지 않으면 서 "호출을 수행"할 수 있습니다. 당신이 아는 것을 알고있는 범위의 물건. 어셈블러 용어로, 데이터 흐름 분석이 통화를 넘어서 사용되지 않는다고 말하면 발신자 -Seaves 레지스터를 보존 할 필요가 없습니다. 다음 재귀/반복에 의해 "당신의"스택을 맹세하지 않는 경우 전화로.
Python 사람들을 역설하는 방법과는 달리 일반적인 재귀 기능을 반복으로 변환하는 것은 사소한 일이 아닙니다. 예를 들어 간단한 접근 방식에서는 곱하기를 곱한 경우 여전히 스택이 필요합니다.
그러나 회고록은 임의로 재귀 함수에 유용한 기술로, 가능한 접근 방식에 관심이 있다면 찾아 볼 수 있습니다. 의미는 함수를 평가할 때마다 결과를 캐시로 고정 시킨다는 것입니다. 이를 사용하여 재귀를 최적화하기 위해, 기본적으로 재귀 함수가 "다운"으로 계산되고 메모 화되면, 당신은 당신이 도달 할 때까지 차례로 함수의 각 값을 계산하는 루프를 추가하여 반복적으로 평가할 수 있습니다. 표적. 이것은 메모 캐시가 필요한 모든 값을 유지하기에 충분히 큰 경우 스택 공간을 거의 사용하지 않습니다. 예를 들어 F (n)이 f (n-1), f (n-2) 및 f (n)에 의존하는 경우 -3) 캐시에서 3 값에 대한 공간 만 필요합니다. 올라갈 때 사다리를 걷어차 수 있습니다. F (n)이 F (N-1) 및 F (N/2)에 의존하는 경우 캐시에 많은 공간이 필요하지만 최적화되지 않은 재귀에서 스택에 사용하는 것보다 여전히 적습니다.
다른 팁
이것은 언어 질문보다 구현 질문입니다. 일부 (STOOPID) C 컴파일러 구현자가 호출 스택을 1000으로 제한하는 것을 막는 것은 없습니다. 그에 대한 스택 공간이없는 작은 프로세서가 많이 있습니다.
(파이썬 사람들은 항상 재귀 기능을 반복적 인 기능으로 변환 할 수 있고 항상 더 빠른 기능을 신속하게 지적합니다. 그것은 100% 사실입니다. 실제로 내 질문에 관한 것이 아닙니다.)
아마도 그들은 그렇게 말하지만 이것은 옳지 않습니다. 재귀는 항상 반복으로 변환 될 수 있지만 때로는 수동으로 사용해야합니다. 스택 도. 그러한 상황에서, 나는 재귀 버전이 더 빠른 것을 볼 수있었습니다 (재귀적인 루틴 밖에서 불필요한 선언을 끌어 당기는 것과 같은 간단한 최적화를 만들기에 충분히 똑똑하다고 가정합니다). 결국, 스택 주변 절차 호출을 푸시하는 스택은 컴파일러가 잘 최적화하는 방법을 알아야하는 잘 제한된 문제입니다. 반면에 수동 스택 작업은 컴파일러에 특수 최적화 코드를 갖지 않을 것이며 추가주기를 차지할 모든 종류의 사용자 인터페이스 세력 검사를 가질 수 있습니다.
반복/스택 솔루션이 항상 더 빠른 경우 일 수도 있습니다. 파이썬에서. 그렇다면 그것은 재귀가 아니라 파이썬의 실패입니다.
PHP는 사망하기 전에 기본 제한이 100입니다.
Fatal error: Maximum function nesting level of '100' reached, aborting!
편집 : 한도를 변경할 수 있습니다 ini_set('xdebug.max_nesting_level', 100000);, 그러나 약 1150 개의 반복을 넘어서면 PHP 충돌이 발생합니다.
[Fri Oct 24 11:39:41 2008] [notice] Parent: child process exited with status 3221225477 -- Restarting.
C#/. Net은 특정 상황에서 꼬리 재귀를 사용합니다. (C# 컴파일러는 TailCall Opcode를 방출하지 않지만 JIT는 경우에 따라 꼬리 재귀를 구현합니다.
Shri Borde 이 주제에 대한 게시물도 있습니다. 물론 CLR은 지속적으로 변화하고 있으며 .NET 3.5 및 3.5SP1을 사용하면 꼬리 통화와 관련하여 다시 변경되었을 수 있습니다.
F# 대화식 콘솔에서 다음을 사용하여 1 초 이내에 실행되었습니다.
let rec f i l =
match i with
| i when i < l -> f (i+1) l
| _ -> l
f 0 100000000;;
그런 다음 직선 번역을 시도했습니다
let rec g i l = if i < l then g (i+1) l else l
g 0 100000000;;
같은 결과이지만 다른 편집.
이것이 무엇입니다 에프 C#로 번역 된 것 같습니다.
int f(int i, int l)
{
while(true)
{
int num = i;
if(num >= l)
return l;
int i = num;
l = l;
i = i + 1;
}
}
g, 그러나 이것으로 번역됩니다.
int g(int i, int l)
{
while(i < l)
{
l = l;
i++;
}
return l;
}
기본적으로 동일한 두 기능이 F# 컴파일러에 의해 다르게 렌더링된다는 것이 흥미 롭습니다. 또한 F# 컴파일러에는 테일 리커 셔티 최적화가 있음을 보여줍니다. 따라서 이것은 32 비트 정수의 한계에 도달 할 때까지 루프해야합니다.
이 스레드에 따르면 약 5,000,000 Java, 1GB RAM. (그리고 핫스팟의 '클라이언트'버전으로)
그것은 함께 있었다 스택 (-xss) 300mo.
a -서버 옵션, 그것은 증가 할 수 있습니다.
또한 컴파일러를 최적화하려고 시도 할 수 있습니다 (제트기와 함께 예를 들어) 각 레이어에서 스택 오버 헤드를 줄입니다.
일부 비 병리학 적 경우 (예 :) (최신) LUA는 사용할 것입니다. 테일 호출 재귀, 즉. 스택에서 데이터를 푸시하지 않고 점프합니다. 따라서 재귀 루프의 수는 거의 무제한이 될 수 있습니다.
테스트 : :
function f(i, l)
if i < l then
return f(i+1, l)
end
return i
end
local val1 = arg[1] or 1
local val2 = arg[2] or 100000000
print(f(val1 + 0, val2 + 0))
또한 :
function g(i, l)
if i >= l then
return i
end
return g(i+1, l)
end
심지어 심지어 교차 추방을 시도했습니다 (F 호출 및 G 호출 f ...).
Windows에서 LUA 5.1은 약 1.1MB (일정한)를 사용하여이를 실행하고 몇 초 안에 마무리됩니다.
Ruby 1.9.2dev (2010-07-11 개정 28618) [x86_64-darwin10.0.0] 구형 흰색 MacBook :
def f
@i += 1
f
end
@i = 0
begin
f
rescue SystemStackError
puts @i
end
저를 위해 9353을 출력합니다. 즉, 루비는 스택에 10,000 호의 호출이 미만으로 쓰러져 있습니다.
다음과 같은 교차 추방과 함께
def f
@i += 1
g
end
def g
f
end
4677 (~ = 9353 / 2)에서 반 시간 안에 튀어 나옵니다.
Proc에 재귀 통화를 감싸서 몇 가지 반복을 더 짜낼 수 있습니다.
def f
@i += 1
yield
end
@i = 0
@block = lambda { f(&@block) }
begin
f(&@block)
rescue SystemStackError
puts @i
end
오류가 발생하기 전에 최대 4850까지 올라갑니다.
Visual DataFlex는 오버플로를 쌓을 것입니다.
저는 기능 프로그래밍의 팬이며, 대부분의 Langauges는 테일 콜 최적화를 구현하기 때문에 원하는만큼 재발 할 수 있습니다.
그러나 실제로, 나는 많은 Java를 사용하고 Python을 많이 사용해야합니다. Java가 무엇을 가지고 있는지는 알지 못하지만 파이썬의 경우 테일 호출을 시작하여 장식 된 기능을 최적화하는 데코레이터를 구현하기 위해 실제로 계획했지만 아직 수행하지 않았습니다. 나는 재귀를 최적화하지 않기 위해 이것을 계획하고 있었지만 주로 Python 바이트 코드를 동적으로 패치하고 Pythons 내부에 대해 더 많이 배우는 운동으로서 이것을 계획하고있었습니다. 그녀는 일부 itesting 링크를 제공합니다. http://lambda-the-ultimate.org/node/1331 그리고 http://www.rowehl.com/blog/?p=626
개선 할 수있는 방법이 있습니다 Perl 코드, 일정한 크기 스택을 사용하도록합니다. 당신은 특별한 형태의 특별한 형태를 사용하여 이것을합니다 goto.
sub f{
if( $_[0] < $_[1] ){
# return f( $_[0]+1, $_[1] );
@_ = ( $_[0]+1, $_[1] );
goto &f;
} else {
return $_[0]
}
}
처음 전화했을 때 스택에 공간을 할당합니다. 그런 다음 스택에 더 많은 것을 추가하지 않고도 인수를 변경하고 서브 루틴을 다시 시작합니다. 그러므로 그것은 결코 자신을 불러 일으키지 않고 반복적 인 과정으로 바꾸는 척 할 것입니다.
당신은 또한 사용할 수 있습니다 Sub :: Call :: recur 기준 치수. 코드를 이해하기 쉽고 짧게 할 수 있습니다.
use Sub::Call::Recur;
sub f{
recur( $_[0]+1, $_[1] ) if $_[0] < $_[1];
return $_[0];
}
Clojure 꼬리 재귀 "recur"에 대한 특별한 형태를 제공합니다. 이것은 AST의 꼬리 장소에서만 사용할 수 있습니다. 그렇지 않으면 Java처럼 작동하며 stackverflowexception을 던질 것입니다.
