무작위로 재귀 적 메서드 인 Math.Random의 StackOverflowError

Question

이것은 내 프로그램의 컨텍스트입니다.

함수에는 아무 것도하지 않을 확률이 50 %, 자체를 두 번 호출하기 위해 50 %가 있습니다. 프로그램이 끝날 확률은 얼마입니까?

나는이 코드를 썼다. 그리고 그것은 명백하게 훌륭하게 작동한다. 모든 사람에게 분명하지 않을 수있는 대답은이 프로그램이 100 % 완료 할 수 있다는 것입니다. 하지만 거기 StackOverflowError (얼마나 편리;)) 내가 Math.Random()에서 발생,이 프로그램을 실행할 때. 어떤 사람이 내게 어디서 왔는지 지적 할 수 있었고 내 코드가 잘못되었을 때 알려주시겠습니까?

static int bestDepth =0; 
static int numberOfPrograms =0; 
@Test 
public void testProba(){ 
    for(int i = 0; i <1000; i++){ 
     long time = System.currentTimeMillis(); 
     bestDepth = 0; 
     numberOfPrograms = 0; 
     loop(0); 
     LOGGER.info("Best depth:"+ bestDepth +" in "+(System.currentTimeMillis()-time)+"ms"); 
    } 
} 

public boolean loop(int depth){ 
    numberOfPrograms++; 
    if(depth> bestDepth){ 
     bestDepth = depth; 
    } 
    if(proba()){ 
     return true; 
    } 
    else{ 
     return loop(depth + 1) && loop(depth + 1); 
    } 
} 

public boolean proba(){ 
    return Math.random()>0.5; 
} 

.

java.lang.StackOverflowError 
at java.util.Random.nextDouble(Random.java:394) 
at java.lang.Math.random(Math.java:695) 

. 스택이 의심스럽고 기능이 제한되어 있지만 여기에는 문제가 실제로 표시되지 않습니다.

모든 조언이나 단서를 환영합니다.

파비앙

편집 : 감사합니다 귀하의 답변을, 나는 자바 -Xss4m 그것을 실행하고 큰했다.

Answer 1

, 스택 : 당신이 테스트는 다음과 유래 스레드에 주어진 답변을 사용하여 스택 크기를 증가시킬 수 종료되도록하려면 그것을 배치하고 공간을 확보하기 위해 사용됩니다.

이제는 loop 함수를 재귀 적으로 호출하는 것으로 보입니다. 그러면 코드 세그먼트와 반환 주소와 함께 인수가 스택에 배치됩니다. 이것은 많은 정보가 스택에 놓여 있음을 의미합니다.

그러나 스택은 제한적입니다. CPU에는 데이터가 스택에 푸시되고 최종적으로 코드 자체가 재정의되는 문제를 방지하는 메커니즘이 내장되어 있습니다 (스택이 커짐에 따라). 이를 General Protection Fault이라고합니다. 일반 보호 오류가 발생하면 OS는 현재 실행중인 작업을 알립니다. 따라서 Stackoverflow을 기원으로합니다.

이것은 Math.random()에서 발생하는 것으로 보입니다.

문제를 해결하려면 -Xss 옵션 Java을 사용하여 스택 크기를 늘리는 것이 좋습니다.

Answer 2

재귀의 단점은 재귀가 너무 깊어지면 결국 스택 오버플로가 발생할 스택을 채우기 시작한다는 것입니다.

함수가 호출 또는 비 정적 변수가 생성 될 때마다

How to increase to Java stack size?

Answer 3

앞서 말씀 드린대로 loop 함수는 재귀 적으로 자체를 호출합니다. 이제 tail recursive calls은 컴파일러에서 루프로 다시 작성할 수 있으며 스택 공간을 차지하지 않습니다 (이를 테일 호 최적화, TCO라고 함). 불행히도, 자바 컴파일러는 그렇게하지 않습니다. 또한 loop은 꼬리 재귀가 아닙니다. 여기에 옵션이 있습니다 :

1. 다른 답변에서 제안하는 것과 같이 스택 크기를 늘리십시오. 이렇게하면 시간이 지남에 따라 문제가 더 지연 될 것입니다. 스택의 크기에 관계없이 크기는 여전히 유한합니다.공간 제한을 벗어나기 위해 긴 호출의 재귀 호출이 필요합니다.
는
2. 당신은 여전히 ​​꼬리 재귀
3. 로 기능을 재 작성 또는 trampolines으로 재 작성해야합니다 TCO
   1. 수행하는 컴파일러가있는 language를 사용하여 루프의 관점에서 함수를 다시 작성
   2. (사소한 변경 만 필요함). 트램폴린을 설명하고 더 일반화 된 좋은 종이를 "Stackless Scala with Free Monads"이라고합니다.

      def loop(depth: Int): Trampoline[Boolean] = { 
          numberOfPrograms = numberOfPrograms + 1 
          if(depth > bestDepth) { 
          bestDepth = depth 
          } 
          if(proba()) done(true) 
          else for { 
          r1 <- loop(depth + 1) 
          r2 <- loop(depth + 1) 
          } yield r1 && r2 
      } 
      

      그리고 초기 호출 loop(0).run를 다음과 같습니다

여기처럼 다시 함수가 보일 것이다 방법, 3.2 점을 설명합니다.

Answer 4

스택 크기를 늘리는 것은 좋은 임시 수정 방법입니다. 그러나 this post에 의해 입증 된 바와 같이, loop() 함수는 을 결국으로 반환하도록 보장되지만, loop()에 의해 요구되는 평균 스택 깊이는 무한한입니다. 따라서 스택을 얼마나 많이 증가 시키더라도 결국 프로그램의 메모리가 부족해져 충돌이 발생합니다.

확실하게 방지 할 수있는 방법은 없습니다. 우리는 항상 메모리에 스택을 인코딩해야합니다 어떻게 든, 그리고 우리는 결코 무한한 메모리를 가지지 않을 것입니다. 그러나 사용중인 메모리 양을 약 2 배 정도 줄이는 방법이 있습니다. 이렇게하면 프로그램에 이 상당히 흐트러지지 않고 돌아올 확률이 높아집니다 ().

스택의 각 레이어에서 실제로 프로그램을 실행하는 데 필요한 정보가 하나만 있다는 것을 알면이 작업을 수행 할 수 있습니다. 반환 후 loop()에 다시 전화해야하는지 알려주는 부분입니다. 따라서 비트 스택을 사용하여 재귀를 에뮬레이트 할 수 있습니다. 각 에뮬레이트 된 스택 프레임은 메모리가 인 비트 (현재 32 비트인지 64 비트인지에 따라 64-96 배 필요)입니다.

(내가 지금 자바 컴파일러가없는 그래서 그것을 테스트 할 수 있지만)이 처럼 보일 것입니다 코드 :

이 아마 약간 느려집니다

static int bestDepth = 0; 
static int numLoopCalls = 0; 

public void emulateLoop() { 
    //Our fake stack. We'll push a 1 when this point on the stack needs a second call to loop() made yet, a 0 if it doesn't 
    BitSet fakeStack = new BitSet(); 
    long currentDepth = 0; 
    numLoopCalls = 0; 

    while(currentDepth >= 0) 
    { 
     numLoopCalls++; 

     if(proba()) { 
      //"return" from the current function, going up the callstack until we hit a point that we need to "call loop()"" a second time 
      fakeStack.clear(currentDepth); 
      while(!fakeStack.get(currentDepth)) 
      { 
       currentDepth--; 
       if(currentDepth < 0) 
       { 
        return; 
       } 
      } 

      //At this point, we've hit a point where loop() needs to be called a second time. 
      //Mark it as called, and call it 
      fakeStack.clear(currentDepth); 
      currentDepth++; 
     } 
     else { 
      //Need to call loop() twice, so we push a 1 and continue the while-loop 
      fakeStack.set(currentDepth); 
      currentDepth++; 
      if(currentDepth > bestDepth) 
      { 
       bestDepth = currentDepth; 
      } 
     } 
    } 
} 

하지만, 약 1/100의 메모리를 사용합니다.BitSet은 힙에 저장되므로 더 이상 스택 크기를 늘릴 필요가 없습니다. 무엇이든간에, 당신은 increase the heap-size을 원할 것입니다.