sicp 练习 1.22
再见,胡子大叔

sicp 练习 1.23

args posted @ 2011年10月04日 22:12 in 未分类 with tags sicp scheme , 1485 阅读

10000000改进函数

(define (find-devisor n test-devisor)
  (cond ((> (square test-devisor) n) n)
	((divides? test-devisor n) test-devisor)
	(else (find-devisor n (next test-devisor)))))

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))


10000000 times 1000
---------------------
10000019 0.341
10000079 0.343
10000103 0.342

100000000 times 1000
---------------------
100000007 1.079
100000037 1.048
100000039 1.035

1000000000 times 500
---------------------
1000000007 3.708
1000000009 3.692
1000000021 3.81

10000000000 times 250
---------------------
10000000019 12.088
10000000033 11.94
10000000061 11.956


100000000000 times 100
---------------------
100000000003 37.91
100000000019 38.44
100000000057 38.14

1000000000000 times 30
---------------------
1000000000039 118.967
1000000000061 121.333
1000000000063 118.9

10000000000000 times 10
----------------------
10000000000037 386.7
10000000000051 384.5
10000000000099 385.8

用上面的结果列表:

num avg-1 avg-2 ratio-1 ratio-2 avg-1/avg-2
10000000 0.5523 0.345    /    / 1.601
100000000 1.741 1.054 3.152 3.055 1.652
1000000000 6.14 3.737 3.527 3.546 1.643
10000000000 20.453 11.995 3.331 3.210 1.705
100000000000 65.4 38.163 3.198 3.182 1.714
1000000000000 208.3 119.733 3.180 3.137 1.740
10000000000000 655.167 385.667 3.145 3.221 1.699

可以看到比值并不是2,一个直观的解释是我们定义的next是一个函数,对一个数的检测要调用next√n / 2 次,造成以一定的开销损耗。可以观察到,其实我们找出来的素数都是奇数,也就不需要为2单独判断,于是可以把next函数改为(+ test-divisor 2),再进行一次实验。

 

10000000 times 1000
---------------------
10000019 0.276
10000079 0.275
10000103 0.282

100000000 times 1000
---------------------
100000007 0.866
100000037 0.868
100000039 0.868

1000000000 times 500
---------------------
1000000007 3.054
1000000009 3.084
1000000021 3.058

10000000000 times 250
---------------------
10000000019 9.956
10000000033 10.292
10000000061 10.18


100000000000 times 100
---------------------
100000000003 32.36
100000000019 33.35
100000000057 32.49

1000000000000 times 30
---------------------
1000000000039 101.333
1000000000061 103.4
1000000000063 102.433

10000000000000 times 10
----------------------
10000000000037 319.6
10000000000051 331.1
10000000000099 341.9

 

num avg-1 avg-2* ratio-1 ratio-2* avg-1/avg-2*
10000000 0.5523 0.277    /    / 1.994
100000000 1.741 0.867 3.152 3.130 2.008
1000000000 6.14 3.065 3.527 3.535 2.003
10000000000 20.453 10.143 3.331 3.309 2.016
100000000000 65.4 32.733 3.198 3.227 1.998
1000000000000 208.3 102.389 3.180 3.128 2.034
10000000000000 655.167 330.867 3.145 3.231 1.980

可以看到调整之后的比例基本都在2的附近,所以可以肯定损耗的原因是next函数带来的开销了。

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter