하노이 타워 문제의 <strong>haskell</strong>에이 기능을 프로그래밍했습니다. (베트남 하노이 타워)

Question

두 개의 재귀 호출이 완료되지 않았습니다. 이 기능은 소스 스틱에서 하나의 대체 스틱으로 목적지 스틱까지의 단계 수를 제공합니다.

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = numStepsHanoi (n-1) + numStepsHanoi (n-1) + 1 

이 기능은 잘 작동 ... N 때까지, 디스크의 숫자가 너무 높게 가져옵니다. GHCi가 끝나지 않습니다. 나는이 문제의 복잡성을 알고 있으며 더 빨리 달릴 수 없다는 것을 알고있다.

예를 들어 n = 64으로 전화를 걸면 20 분 정도 기다려도 결과가 출력되지 않습니다 (완료되지 않음). n = 20이라도 약 2 초가 걸립니다.

다른 구현 (아래)을 사용하면 시간이 상당히 줄어 듭니다.

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = 2 * numStepsHanoi (n-1) - 1 

이제 n = 64으로 결과가 즉시 나타납니다. 분명히 이것은 단 하나의 순환 호출을 가지지 만 그렇게 큰 영향을 미칩니 까?

GHCi 최적화의 문제 일 수 있습니까?

Answer 1

실제로이 점은 이 인 것으로 의심됩니다. 첫 번째 버전에서는 호출 할 때마다 2 번의 재귀 호출을 수행하며, 복잡도는 O (2^n)입니다. n = 64 인 경우 총 통화 수는 2^65 - 1입니다. 약 37 * 10^18 통화이므로 현재 컴퓨팅 파워로는 평생 동안 결과를 보지 못할 것입니다. 1 마이크로 초당 1 회의 통화로도 1 천만년이 넘습니다.

두 번째 루틴은 반복마다 하나의 호출 만 수행합니다. 그것은 O (n)입니다.

효과를 보려면 n = 19, 20, 21, 22에서 첫 번째 기능을 시도해보십시오. 추가 된 각 디스크에 대해 2 배의 시간 차이를 표시하려면 충분해야합니다.

Answer 2

표준적인 조언은 공통된 하위 표현식 최적화를 적용하는 것이 확실한 것으로 보입니다. https://wiki.haskell.org/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F을 참조하십시오.

numStepsHanoi :: Integer -> Integer 
numStepsHanoi 0 = 0 
numStepsHanoi n = let steps = numStepsHanoi (n-1) 
        in steps + steps + 1