[plt-scheme] Efficiency: Chaining locals (using only when needed) OR "all in one local"

 From: Albert Neumüller (albert.neu at gmail.com) Date: Thu Sep 21 17:05:52 EDT 2006 Previous message: [plt-scheme] Scheme MUD? Next message: [plt-scheme] Efficiency: Chaining locals (using only when needed) OR "all in one local" Messages sorted by: [date] [thread] [subject] [author]

```Hello!

Which construct below gives you better performance?
The first one, calculates all the "temp stuff" inside one single local.
The second one, calculates uses multiple locals, and does *not* calc
"temp stuff" that is not needed?

It problably depends on:
1. how heavy "temp stuff" is to evaluate
2. the max. number of locals that could be chained one-after-the-other

Are multiple locals more expensive than a single local, if "temp
stuff" is very fast (negligible)??

;==CONSTRUCT A=======================================
(local ((define a ...)
(define b ...)
(define c ...)
(define d ...)
(define e ...))
(cond
[(= a b) ...]
[(= b c) ...]
[(= c d) ...]
[(= d e) ...]
[else ...]))

;==CONSTRUCT B=======================================
(local ((define a ...)
(define b ...))
(cond
[(= a b) ...]
[else (local ((define c ...))
(cond
[(= b c) ...]
[else (local ((define d ...))
(cond
[(= c d) ...]
[else (local ((define e ...))
(cond
[(= d e) ...]
[else ...]))]))]))]))

Kind regards,
Albert Neumüller

Here are 2 examples:

;;HTDP twenty-nine.three.nine
;(just to keep students from finding this answer)

;;b-c? : (vectorof number) number -> N
;;if key is in vec, return vector index; else return false
(define (b-c? vec key)
(local ((define len-sub1 (sub1 (vector-length vec)))
(define left-ref (vector-ref vec 0))
(define right-ref (vector-ref vec len-sub1))
(define (contains? left-i right-i len)
(cond
[(<= len 1) false]
[else (local ((define len2 (quotient len 2))
(define mid-i (+ left-i len2))
(define mid-ref (vector-ref vec mid-i)))
(cond
[(= key mid-ref) mid-i]
[(< key mid-ref) (contains? left-i mid-i len2)]
[else (contains? mid-i right-i (- right-i mid-i))]
;here len2 has to be re-calculated
;e.g. it could be that: left-i = 0
;                       right-i = 5
;                       mid-i = 2
;                       len2 = 2
;Of course (= mid-i (+ left-i len2)) since
that's how we calc mid-i above
;But if we continue the search on the right half, then
;"new len2" = (- right-i mid-i) = 3 (which is not 2)
))])))
(cond
[(= key left-ref) 0]
[(= key right-ref) len-sub1]
[(< key left-ref) false] ;this line and the next are optional
and not strictly needed
[(> key right-ref) false]
[else (contains? 0 len-sub1 len-sub1)])))

;;b-c?2 : (vectorof number) number -> N
;;if key is in vec, return vector index; else return false
(define (b-c?2 vec key)
(local ((define left-ref (vector-ref vec 0)))
(cond
[(= key left-ref) 0]
[(< key left-ref) false] ;this line is optional and not strictly needed
[else (local ((define len-sub1 (sub1 (vector-length vec)))
(define right-ref (vector-ref vec len-sub1)))
(cond
[(= key right-ref) len-sub1]
[(> key right-ref) false] ;this line is optional and
not strictly needed
[else (local ((define (contains? left-i right-i len)
(cond
[(<= len 1) false]
[else (local ((define len2 (quotient len 2))
(define mid-i (+ left-i len2))
(define mid-ref
(vector-ref vec mid-i)))
(cond
[(= key mid-ref) mid-i]
[(< key mid-ref)
(contains? left-i mid-i len2)]
[else (contains? mid-i
right-i (- right-i mid-i))]
;here len2 has to be re-calculated
;e.g. it could be that: left-i = 0
;                       right-i = 5
;                       mid-i = 2
;                       len2 = 2
;Of course (= mid-i (+
left-i len2)) since that's how we calc mid-i above
;But if we continue the
search on the right half, then
;"new len2" = (- right-i
mid-i) = 3 (which is not 2)
))])))
(contains? 0 len-sub1 len-sub1))]))])))

(define vec1 (vector 1 2 4 5))
(define vec2 (vector 1 2 4 5 6))

(define go1
(local ((define (f i)
(b-c? vec1 i)))
f))

(define go2
(local ((define (f i)
(b-c? vec2 i)))
f))

;tests:
(equal? (build-list 7 go1)
(list false 0 1 false 2 3 false))
(equal? (build-list 8 go2)
(list false 0 1 false 2 3 4 false))

```

 Posted on the users mailing list. Previous message: [plt-scheme] Scheme MUD? Next message: [plt-scheme] Efficiency: Chaining locals (using only when needed) OR "all in one local" Messages sorted by: [date] [thread] [subject] [author]