两种编写函数的方法，效率有何不同？
让 f 将一个值转换为另一个值，然后我编写一个重复转换 n 次的函数。
我想出了两种不同的方法：
- 一种是显而易见的方法 从字面上应用函数 n 次，所以 repeat(f, 4) 意味着 x → f(f(f(f(x))))
- 另一种方式的灵感来自 快速供电方法，这意味着 将问题一分为二 问题只有一半大 每当 n 是偶数时。所以重复(f, 4) 表示x → g(g(x))，其中g(x) = f(f(x))
起初我认为第二种方法不会提高太多效率。到最后，我们仍然需要申请 fn 次，不是吗？在上面的例子中，g仍然会被翻译成fo f，而不需要任何进一步的简化，对吧？
然而，当我尝试这些方法时，后一种方法明显更快。
;; computes the composite of two functions
(define (compose f g)
(lambda (x) (f (g x))))
;; identify function
(define (id x) x)
;; repeats the application of a function, naive way
(define (repeat1 f n)
(define (iter k acc)
(if (= k 0)
acc
(iter (- k 1) (compose f acc))))
(iter n id))
;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
(define (iter f k acc)
(cond ((= k 0) acc)
((even? k) (iter (compose f f) (/ k 2) acc))
(else (iter f (- k 1) (compose f acc)))))
(iter f n id))
;; increment function used for testing
(define (inc x) (+ x 1))
事实上，((repeat2 inc 1000000) 0) 比 ((repeat1 inc 1000000) 0) 快得多。我的问题是第二种方法在哪些方面比第一种方法更有效？重复使用相同的函数对象是否可以保留存储空间并减少创建新对象所花费的时间？
毕竟，应用程序必须重复n次，或者换句话说，x→((x+1)+1)不能自动减少到x→(x+2 ），对吗？
我正在 DrScheme 4.2.1 上运行。
非常感谢。
Let f transform one value to another, then I'm writing a function that repeats the transformation n times.
I have come up with two different ways:
- One is the obvious way that
literally applies the function n
times, so repeat(f, 4) means x →
f(f(f(f(x)))) - The other way is inspired from the
fast method for powering, which means
dividing the problem into two
problems that are half as large
whenever n is even. So repeat(f, 4)
means x → g(g(x)) where g(x) =
f(f(x))
At first I thought the second method wouldn't improve efficiency that much. At the end of the day, we would still need to apply f n times, wouldn't we? In the above example, g would still be translated into f o f without any further simplification, right?
However, when I tried out the methods, the latter method was noticeable faster.
;; computes the composite of two functions
(define (compose f g)
(lambda (x) (f (g x))))
;; identify function
(define (id x) x)
;; repeats the application of a function, naive way
(define (repeat1 f n)
(define (iter k acc)
(if (= k 0)
acc
(iter (- k 1) (compose f acc))))
(iter n id))
;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
(define (iter f k acc)
(cond ((= k 0) acc)
((even? k) (iter (compose f f) (/ k 2) acc))
(else (iter f (- k 1) (compose f acc)))))
(iter f n id))
;; increment function used for testing
(define (inc x) (+ x 1))
In fact, ((repeat2 inc 1000000) 0) was much faster than ((repeat1 inc 1000000) 0). My question is in what aspect was the second method more efficient than the first? Did re-using the same function object preserves storage and reduces the time spent for creating new objects?
After all, the application has to be repeated n times, or saying it another way, x→((x+1)+1) cannot be automatically reduced to x→(x+2), right?
I'm running on DrScheme 4.2.1.
Thank you very much.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你是对的，两个版本对
inc的调用次数相同 - 但还有更多开销比您的代码中的开销要大。具体来说，第一个版本创建了 N 个闭包，而
第二个仅创建 log(N) 个闭包——如果闭包创建是大部分工作
然后你会看到性能上的巨大差异。
您可以使用三件事来更详细地了解这一点：
使用 DrScheme 的
time特殊形式来测量速度。除了它的时间之外执行一些计算所花费的时间，它还会告诉您 GC 花费了多少时间。
您将看到第一个版本正在执行一些 GC 工作，而第二个版本则没有。
（嗯，确实如此，但是太小了，可能不会显示。）
您的
inc函数做得很少，您只测量循环开销。例如，当我使用这个糟糕的版本时：
两种用途之间的差异从约 11 倍下降到 1.6。
最后，尝试一下这个版本：
<前><代码>（定义（repeat3 fn）
（拉姆达 (x)
（定义（iter nx）
（如果（零？n）x（iter（sub1 n）（fx））））
（iter nx）））
它不做任何合成，它的工作原理大致如下
与第二个版本的速度相同。
You're right that both versions do the same number of calls to
inc-- but there's moreoverhead than that in your code. Specifically, the first version creates N closures, whereas
the second one creates only log(N) closures -- and if the closure creation is most of the work
then you'll see a big difference in performance.
There are three things that you can use to see this in more details:
Use DrScheme's
timespecial form to measure the speed. In addition to the time that ittook to perform some computation, it will also tell you how much time was spent in GC.
You will see that the first version is doing some GC work, while the second doesn't.
(Well, it does, but it's so little, that it will probably not show.)
Your
incfunction is doing so little, that you're measuring only the looping overhead.For example, when I use this bad version:
the difference between the two uses drops from a factor of ~11 to 1.6.
Finally, try this version out:
It doesn't do any compositions, and it works in roughly
the same speed as your second version.
第一种方法本质上应用该函数 n 次，因此它的复杂度为 O(n)。但第二种方法实际上并没有应用该函数n次。每次调用repeat2时，只要n是偶数，它就会将n除以2。因此，大多数时候问题的大小会减半，而不仅仅是减少 1。这给出了 O(log(n)) 的总体运行时间。
正如Martinho Fernandez建议的，维基百科文章通过平方求幂解释得非常清楚。
The first method essentially applies the function n times, thus it is O(n). But the second method is not actually applying the function n times. Every time repeat2 is called it splits n by 2 whenever n is even. Thus much of the time the size of the problem is halved rather than merely decreasing by 1. This gives an overall runtime of O(log(n)).
As Martinho Fernandez suggested, the wikipedia article on exponentiation by squaring explains it very clearly.