이번 문제는 알고리즘을 개선시켰을 때

효율이 얼마나 차이나는지 확인하는 문제입니다.

방법은 다음과 같습니다.

find-divisor 프로시저를 보면 약수임을 확인하는 방법으로 1씩 더하고 있습니다.

find-divisor 프로시저(SICP 64쪽)

하지만 2를 확인하면 그 후의 짝수들(4, 6, 8, 10 등...)은 검사할 필요가 없습니다.

따라서 2를 확인 후 3을 확인하고 그 다음부터는 홀수만 검사하면 됩니다.

그 방법에 따라 프로시저를 수정하였습니다.

2가 들어오면 3을 내놓고, 그 외의 수가 들어오면 2를 더하여 홀수를 내놓는

next라는 프로시저를 만들었습니다.

그리고 문제를 연습문제 1.22를 그대로 하여 돌렸습니다.

왼쪽의 것이 고치기 전의 결과, 오른쪽의 것이 고친 후의 결과입니다.

대충 1/2가량 시간이 감소하였습니다.

평균을 내어보니 약 1.84배의 성능 차이를 보였습니다.

그래서 성능향상이 되었다는 생각을 하였는데 문제에 이런 글이 적혀있습니다.

'검사 횟수가 반으로 줄었으니 계산도 두 배는 빨라지리라 예상할 것이다.

참말 바람대로 그런 결과가 나오는가?

그렇지 않다면, 두 알고리즘의 빠르기를 견줄 때 그 진짜 비율은 어림잡아 얼마인가?

왜 그 비율이 2가 되지 않는지 설명할 수 있는가?'

- SICP 70쪽

문제에서는 왜 틀렸는지를 물어볼까요?

그렇다면 결과값이 2가 나오지 말아야 한다는 뜻입니다.

물론 제가 구한 값은 1.84로 2는 아닙니다만 근접합니다.

설마 0.16의 차이를 설명하라는 뜻인가요??

어떤 이유인지 확실하지 않으나 이렇게 생각합니다.

후의 것은 전의 것에 비해 next라는 프로시저를 실행시켜야 하고

그 안에 cond문을 작동시켜야 합니다.

그 차이에서 정확하게 2가 아닌 0.16의 차이가 나온 것이라 생각합니다.

Lisp라 C언어와의 차이점을 정확하게 모르겠지만,

최적화 하는 기법 중 하나로 Loop Unswitching이라는 것을 보았습니다.

(관련글 : 'Loop Unswitching, 저전력화를 위한 기법.')

여기서 루프 안에 분기(if)가 들어가면 성능에 나쁘다고 합니다.

새롭게 만든 프로시저 역시 cond라는 분기를 매번 반복하기에

그 차이에서 2가 아닌 1.84가 나온 듯싶습니다.

참조

Structure and Interpretation of Computer Programs 2/E - Page 69

http://monac.egloos.com/1694723

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.