Two methods of composing functions, how do they differ in efficiency?
Let f convert one value to another, then I write a function that repeats the conversion n times.
I came up with two different ways:
- One is the obvious way to literally apply the function n times, so repeat (f, 4) means x -> e (e (e (e (x))))
- Another way is inspired by the fast way of eating, which means dividing the problem into two problems in half when n is even. So repeat (f, 4) means x -> g (g (x)) where g (x) = e (e (x))
At first I thought the second method would not improve efficiency. After all, we still have to use fn times, right? In the example above, g will still be translated to fof without any further simplification, right?
However, when I tried out the methods, the last 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 effective than the first? Reusing the same functional object saves storage and reduces the time it takes to create new objects?
After all, the application needs to be repeated n times, or say it differently, x → ((x + 1) +1) cannot automatically reduce to x → (x + 2) , right?
I am working on DrScheme 4.2.1.
Many thanks.
source to share
You are correct that both versions have the same number of calls on inc
- but there is more overhead than there is in your code. Specifically, the first version creates N closures, while the second only creates log (N) closures - and if creating a closure is most of the work, then you will see a big difference in performance.
There are three things you can use to see this in more detail:
-
Use the special DrScheme form
time
to measure speed. In addition to the time it took to do some calculations, it will also tell you how much time was spent on GC. You will see that the first version does some GC work, while the second does not. (Well, it does, but it's so small that it probably won't show up.) -
Your function
inc
does so little that you only measure the overhead. For example, when I use this bad version:(define (slow-inc x) (define (plus1 x) (/ (if (< (random 10) 5) (* (+ x 1) 2) (+ (* x 2) 2)) 2)) (- (plus1 (plus1 (plus1 x))) 2))
the difference between these two applications falls from a factor of ~ 11 to 1.6.
-
Finally, try this version:
(define (repeat3 f n) (lambda (x) (define (iter n x) (if (zero? n) x (iter (sub1 n) (f x)))) (iter n x)))
It doesn't have any compositions and it runs at about the same speed as the second version.
source to share
The first method essentially applies the function n times, so O (n). But the second method doesn't actually apply the function n times. Every time repeat2 is called, it splits n by 2 whenever n is even. This way, most of the time, the problem is halved, rather than just decreasing by 1. This gives a total runtime of O (log (n)).
As Martinjo Fernandez suggested, the wikipedia article on elevation by square explains this very clearly.
source to share