以下函数作为本练习的介绍,说明了用加法定义的乘法。这是最简单的“容易写下来”的递归定义。
(define (star a b)
(if (= b 0)
0
(+ a (star a (- b 1)))))
当我看到这一点时,我做的第一件事就是按照之前的练习,编写一个不会破坏堆栈的迭代形式:
(define (star a b)
(star-iter a b 0))
(define (star-iter a counter sum)
(if (= counter 0)
sum
(star-iter a (- counter 1) (+ a sum))))
练习 1.17 鼓励我们找到一个不变量,以减小问题规模,其想法是从 O(n) 到 O(logn) 步数(当执行该特定步骤时,无需执行任何更新结果的事情 - 我们在该步骤中所做的就是减少/转换问题定义 - 这就是“找到不变量”的含义)(参见下面第一个代码块的第 3 行 - 没有添加任何内容导致该步骤)。
对于快速版本,问题说我们应该使用函数halve
和double
,并且似乎暗示这些函数可以作为机器操作使用(恒定时间?)。我已经实现了“快速”版本,只是欺骗了这些函数,如下所示:
(define (fast-star a b)
(cond ((or (= b 0) (= a 0)) 0)
((even? a) (fast-star (/ a 2) (* 2 b)))
(else (+ a (fast-star a (- b 1))))))
迭代形式的相同内容(即 O(1) 空间):
(请注意上面第 4 行中的 + a
如何移动到下面第 6 行末尾的累加器,以将其置于尾部位置)
(define (fast-star b)
(fast-star-iter a b 0))
(define (fast-star-iter a b sum)
(cond ((or (= a 0) (= b 0)) sum)
((even? a) (fast-star-iter (/ a 2) (* 2 b) sum))
(else (fast-star-iter a (- b 1) (+ a sum)))))
所以这是一个“有什么意义”的问题 - 这些函数比上面给出的前两个函数慢。这四个函数中的第一个会破坏堆栈,因此它没有用。但第二个没有。在我的测试中,这个版本比这两个“快速”版本中的任何一个都更快。
我在这里遗漏了什么吗?很好奇是否有一种方法可以实现减半和双倍,以便它们实际上给出此处建议的 log(n) 结果。一定有,否则这个问题就没有意义。
请注意,如果 a 和 b 的大小不同,则它们的顺序很重要 - 例如乘以 2、100 次或 100、2 次,第一个是 100 步,后一个是 2 步。这将是稍后添加到此功能中的内容。但首先对 half
和 double
感到好奇。
最佳答案
您的代码中有一个微妙的错误,这就是它很慢的原因。对于版本 3 和 4,这应该可以解决这个问题:
(define (fast-star a b)
(cond ((or (= b 0) (= a 0)) 0)
((even? b) (fast-star (* 2 a) (/ b 2.0)))
(else (+ a (fast-star a (- b 1))))))
(define (fast-star-iter a b sum)
(cond ((or (= a 0) (= b 0)) sum)
((even? b) (fast-star-iter (* 2 a) (/ b 2.0) sum))
(else (fast-star-iter a (- b 1) (+ a sum)))))
这个想法是在每次迭代中不断添加a
并减少b
,但根据情况有时您会减少 b
有时你会加倍!另请注意,我将 b
除以 2.0
以消除精确算术,这样速度较慢。
当然,您也可以反过来做:添加 b
并减少 a
- 重要的是要一致它,将一个参数的问题减半,并将另一个参数加倍,加倍的参数就是我们需要添加到最终结果中的参数。
关于scheme - SICP Ex。 1.17 - "fast-multiply"比 "multiply"慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62150288/