이 C ++ 기능은 어떻게 메모리를 사용합니까?

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

문제 

#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

일부 입력을 기반으로 재귀 공식을 계산하기 위해 Memoization을 사용한 위의 코드 샘플 n. 나는 이것이 동일한 공식을 사용하는 순전히 재귀 함수를 작성했기 때문에 메모 화를 사용한다는 것을 알고 있습니다. n. 나는 전에 벡터를 사용한 적이 없지만 연구를 수행했으며 그 개념을 이해합니다. 메모 화는 계산 된 각 계산 값을 저장해야한다는 것을 이해하므로 동일한 계산을 다시 수행하는 대신 이미 계산 된 계산을 검색 할 수 있습니다.

내 질문은 다음과 같습니다.이 메모리는 어떻습니까? 어떻게 작동합니까? N에 대한 값이 이미 존재하는지 확인하기 위해 코드에서 볼 수없는 것 같습니다. 또한, 나는의 목적을 이해하지 못한다 if(as[n]<=0). 이 공식은 양수와 음수 값을 산출 할 수 있으므로이 점검이 무엇을 찾고 있는지 잘 모르겠습니다.

감사합니다. 저는 이것이 어떻게 작동하는지 이해하는 데 가깝다고 생각합니다. 실제로 생각보다 조금 더 간단합니다.

나는 순서의 값이 0 일 수 있다고 생각하지 않기 때문에 N은 1에서 시작해야한다고 생각하기 때문에 나에게 효과적이어야한다.

그러나 0이 내 시퀀스에서 실행 가능한 숫자라면 해결할 수있는 또 다른 방법은 무엇입니까? 예를 들어, 5 개가 나타날 수 없다면 어떻게해야합니까? 내 벡터를 파이브로 채워야합니까?

편집 : 와우, 코드를 확인 하고이 응답을 입력하는 동안 다른 많은 응답을 얻었습니다. 모두에게 도움을 주셔서 감사합니다. 지금 이해한다고 생각합니다.

도움이 되었습니까?

해결책

if (as[n] <= 0) 수표입니다. 유효한 값이 당신이 말하는 것처럼 부정적 일 수 있다면, 당신은 다른 센티넬을 확인해야합니다. 유효한 값이 0 일 수 있습니까? 그렇지 않다면, 그냥 테스트를하십시오 if (as[n] == 0). 기본적으로 intS는 0으로 가득 차 있습니다.

다른 팁

코드가 잘못 확인되는 것으로 보이며 ([n] <= 0), 함수의 음수 값 (대략 다른 값으로 보임)을 다시 계산합니다. 이것은 재귀 솔루션과 함께 2^n 대신 n으로 작업 스케일을 선형으로 만들어 주므로 훨씬 빠르게 실행됩니다.

그럼에도 불구하고 더 나은 점검은 내 시스템에서 3 배 빠르게 실행되는 것으로 보이는지 ([n] == 0)을 테스트하는 것입니다. 함수가 0을 반환 할 수 있더라도 0 값은 계산하는 데 약간 더 오래 걸린다는 것을 의미합니다 (0이 자주 반환 값이라면 값이 계산되었는지 여부에 관계없이 별도의 벡터를 고려할 수 있습니다. 단일 벡터를 사용하여 함수의 값을 저장하고 계산되었는지 여부)

공식이 양수와 음수 값을 모두 생성 할 수 있다면이 기능에는 심각한 버그가 있습니다. 수표 if(as[n]<=0) ~이다 추정된 이미이 계산 값을 캐시했는지 확인하기 위해. 그러나 공식이 음수 일 수 있다면이 함수는이 캐시 된 값을 많이 다시 계산합니다 ...

아마도 정말로 원했던 것은 vector<pair<bool, unsigned> >, 값이 계산되었는지 여부에 따라 부울이 말하는 곳.

게시 된대로 코드는 시간의 약 40% 만 메모 화합니다 (정확하게 기억 된 값이 양수 일 때). Chris Jester-Young이 지적했듯이 올바른 구현이 대신 확인됩니다. if(as[n]==0). 또는 메모 화 코드 자체를 변경하여 읽을 수 있습니다. as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(심지어 ==0 수표는 메모 화 된 가치가 0 일 때 노력을 소비 할 것입니다. 운 좋게도 당신의 경우에는 결코 일어나지 않습니다!)

이 코드에는 버그가 있습니다. 그것은 [n] <= 0에 대한 [n]의 값을 계속 계산할 것입니다. 재귀가 빠르게 종료되도록 AS []의 양의 긍정적 값이 충분하기 때문에 메모 화없이 코드보다 훨씬 빠르게 작동합니다. 65535보다 큰 값을 보낸 사람으로 사용하여이를 향상시킬 수 있습니다. 벡터의 새로운 값은 벡터가 확장 될 때 0으로 초기화됩니다.

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