Hi all,
I've been pointed to SCHEME very recently by an introductory course in
computer science. We've been told that SCHEME is one of the so-called
functional languages, and recursive definitions (not iterative) are one
of the basic elements of those languages (correct me, if I'm wrong,
perhaps I've been kind of absent while listening to that lecture).
Well, my point of interest is the efficiency of recursive definitions
compared to that of a iterative definition, that yields the same result.
I consider efficiency both in terms of memory usage and time usage (of
the STk-interpreter, of course).
Or in other words: while programming in SCHEME/STk, should I try to avoid
recursive definitions whenever it's possible without making the code a
lot more complicated ? Or, is it just better the opposite way ? Is there
any rule of thumb ? Are there some certain things, that, if used, make
recursion slow and inefficient ?
To illustrate the question, I've provided an example in the appendix of
this mail. The example shows three different implementations of the same
problem: delete all trailing occurrences of a given char in a given
string and return the processed string.
There are two recursive and one iterative variants. One of the recursive
variants uses nearly 1.5-fold more time than the iterative one and more
than 2-fold more "cells". The other recursive variant uses only 80% (!) of
the time of the iterative variant, but nearly 3-fold (!) more cells.
Since I'm not familiar to the internals of STk, I'd appreciate any
comments about the meaning of "cells". I suppose, it's something related
to memory usage.
Finally, I hope I'm not annoying too much SCHEME/STk-experts out there. :-)
Virtually yours
Hilmar
-----------------------------------------------------------------------------
Hilmar Lapp e-mail: hlapp_at_deep-thought.biologie.uni-freiburg.de
Institut f. Biologie II
http://www.biologie.uni-freiburg.de/~hili/hili.html
Universitaet Freiburg phone : +49 761 203 2656
-----------------------------------------------------------------------------
Appendix: three implementations of a function, that deletes all trailing
occurrences of a given char in a given string, and returns the
processed string.
Checks for time and system usage by using (time expr) appended.
System: Linux 1.1.18, CPU 80486 50MHz, STk-2.1.5
;; ----------------------------- begin ----------------------------------
;; deletes all trailing occurrences of c in str and returns the result
;; iterative variant (stolen and slightly modified from unix.stk)
(define (delete-trailing-char-itr str c)
(let ((pos (- (string-length str) 1)))
(while (and (>= pos 0) (char=? (string-ref str pos) c))
(set! pos (- pos 1)))
(if (= pos -1) ""
(substring str 0 (+ pos 1))
)
)
)
;; recursive variant using strings
;; (I know, this one does not check for empty strings)
(define (delete-trailing-char-rec str c)
(if (char=? (string-ref str (- (string-length str) 1)) c)
(delete-trailing-char-rec
(substring str 0 (- (string-length str) 1)) c
)
str
)
)
;; recursive variant using lists
;; (the idea was, that perhaps lists are handled more efficient than
;; strings. Actually, this seems to be the case regarding time usage,
;; but yields opposite behaviour regarding cell (= memory ?) usage)
(define (delete-trailing-char-3rd str c)
(let ((rstrlist (reverse (string->list str))))
(define (del-leading-c l c)
(if (null? l) l
(if (char=? (car l) c)
(del-leading-c (cdr l) c)
l)
))
(list->string (reverse (del-leading-c rstrlist c)))
)
)
;; -------------------- end of definitions --------------------------
;; checking for efficiency:
STk> (define exmplstr "aaa ")
#[undefined]
STk> (time (dotimes (i 1000)
(delete-trailing-char-itr exmplstr #\ )
)
)
;; Time: 9850.00ms
;; GC time: 400.00ms
;; Cells: 117123
#f
STk> (time (dotimes (i 1000)
(delete-trailing-char-rec exmplstr #\ )
)
)
;; Time: 14183.33ms
;; GC time: 916.67ms
;; Cells: 257131
#f
STk> (time (dotimes (i 1000)
(delete-trailing-char-3rd exmplstr #\ )
)
)
;; Time: 7016.67ms
;; GC time: 983.33ms
;; Cells: 333123
#f
STk>
----------------------------- end --------------------------------------
Received on Mon Feb 06 1995 - 19:05:24 CET