이 코드를 개선하는 방법은 무엇입니까?

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

  •  12-09-2019
  •  | 
  •  

문제

내 해결책 운동 1.11 SICP는 다음과 같습니다.

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

예상대로 (F 100)과 같은 평가는 오랜 시간이 걸립니다. 이 코드를 개선 할 수있는 방법이 있는지 궁금해하고 (재귀를 앞지르지 않고) 멀티 코어 박스를 활용합니다. 나는 'mit-scheme'을 사용하고 있습니다.

도움이 되었습니까?

해결책

체계에서 어떻게 코딩하는지 잘 모르겠지만 이와 같은 속도를 향상시키는 일반적인 기술은 사용하는 것입니다. 메모 화. 간단히 말해서, 아이디어는 f (p)의 결과를 캐시하는 것입니다 (아마도 P) (또는 마지막 n 값에 대해 또는 마지막 n 값에 대해) 다음에 F (P)를 호출 할 때 저장된 결과는 존재하지 않고 반환됩니다. 재 계산. 일반적으로 캐시는 튜플 (입력 인수를 나타내는)에서 리턴 유형으로 맵입니다.

다른 팁

이 운동은 두 가지 기능을 작성하도록 지시합니다. f "재귀 과정을 통해", 그리고 다른 하나는 f "반복적 인 과정을 통해". 당신은 재귀적인 것을했습니다. 이 기능은 다음과 매우 유사하기 때문입니다 fib 링크 된 섹션의 예에서 제공되는 함수는 fib 기능:

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

이 경우 정의합니다 f-iter 취할 기능 a, b, 그리고 c 논쟁과 a count 논쟁.

여기에 있습니다 f-iter 기능. 유사성을 주목하십시오 fib-iter:

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

그리고 약간의 시행 착오를 통해 나는 a, b, 그리고 c 초기화해야합니다 2, 1, 그리고 0 각각의 패턴을 따릅니다 fib 기능 초기화 a 그리고 b 에게 1 그리고 0. 그래서 f 이렇게 보인다 :

(define (f n)
  (f-iter 2 1 0 n))

메모: f-iter 여전히 재귀 적입니다 기능 그러나 체계가 작동하는 방식으로 인해 반복적으로 실행됩니다. 프로세스 그리고 실행됩니다 O(n) 시간과 O(1) 재귀 기능뿐만 아니라 재귀 프로세스 인 코드와 달리 공간. 나는 이것이 연습 1.1의 저자가 찾고 있던 것이라고 믿는다.

글쎄, 당신이 나에게 물어 보면, 수학자처럼 생각하십시오. 체계를 읽을 수는 없지만 Fibonacci 함수를 코딩하는 경우 재귀 적으로 정의하는 대신 재발을 해결하고 닫힌 형태로 정의하십시오. Fibonacci 시퀀스의 경우 닫힌 형태를 찾을 수 있습니다. 여기 예를 들어. 훨씬 더 빨라질 것입니다.

편집 : 죄송합니다. 재귀를 제거하는 것을 포기했다고 보지 못했습니다. 이 경우 옵션이 훨씬 제한적입니다.

보다 이 기사 기능 프로그래밍을 통해 빠른 피보나치 기능 개발에 대한 좋은 자습서. 그것은 일부 측면에서 체계와 약간 다른 Common LISP를 사용하지만, 당신은 그것을 가지고 갈 수 있어야합니다. 구현은 bogo-fig 파일 상단 근처에서 기능합니다.

다른 방법으로 말하면 :

꼬리 재귀를 얻으려면 재귀 호출은 절차의 마지막 일이어야합니다.

재귀 호출은 * 및 + 표현식에 포함되므로 꼬리 호출이 아닙니다 ( * 및 +가 평가되기 때문에 ~ 후에 재귀 콜.)

제레미 루텐의 버전 f-iter 반복적이기보다는 꼬리 추방 적입니다 (즉, 재귀 절차처럼 보이지만 반복적으로 동등한 것만 큼 효율적입니다.)

그러나 반복을 명시 적으로 만들 수 있습니다.

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

또는

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

이 특정 운동은 꼬리 재귀를 사용하여 해결할 수 있습니다. 각 재귀 호출이 반환되기를 기다리는 대신 (간단한 솔루션의 경우와 같이) 재귀가 동작하는 방식으로 매개 변수로 답을 축적 할 수 있습니다. 소비하는 공간 측면에서 반복과 정확히 동일합니다. 예를 들어:

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top