이 C ++ 기능은 어떻게 메모리를 사용합니까?
-
02-07-2019 - |
문제
#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)
. 기본적으로 int
S는 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으로 초기화됩니다.