[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

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.