In trying to compare tco vs recur for my own use I came up with
the following:
The two functions 'bstInsertTco', 'bstInsertRecur' (see code at end) are
identical except for tco,tc and recur,recurse.
The repl examples show the degenerate case of inserting an ordered list
into a BST without rebalancing, and also inserting random values (more
balanced)
Speed wise there doesn't seem to be that much difference over recurse. At
least for my use case. The difference in resource usage is significant
though. A nice optimization and the choice of using it is a great feature
in itself.
Thanks!
/Lindsay
# Ordered inserts into BST (the degenerate case)
: (off *Tree) (bench (for N (** 2 15) (bstInsertTco '*Tree N))) T
48.250 sec
: (off *Tree) (bench (for N (** 2 15) (bstInsertRecur '*Tree N))) T
55.248 sec
: (off *Tree) (bench (for N (** 2 16) (bstInsertTco '*Tree N))) T
192.705 sec
: (off *Tree) (bench (for N (** 2 16) (bstInsertRecur '*Tree N))) T
..
Stack overflow
?
Give up: No stack
When building from randomized values, there is not much difference in
performance (although 'tco' is consistently slightly faster).
: (off *Tree) (bench (for N (** 2 14) (bstInsertRecur '*Tree (rand 1 (** 2
32))))) T
0.053 sec
: (let (L (make (bstInOrder link *Tree))) (println (head 3 L) (tail 3 L)
(length L) (apply < L)))
(975009 1096393 1301832) (4294487248 4294754706 4294841759) 16384 T
: (off *Tree) (bench (for N (** 2 14) (bstInsertTco '*Tree (rand 1 (** 2
32))))) T
0.038 sec
: (let (L (make (bstInOrder link *Tree))) (println (head 3 L) (tail 3 L)
(length L) (apply < L)))
(546090 725497 1200269) (4293939971 4294665037 4294749566) 16384 T
# The functions
(de bstInsertRecur (Tree Key)
(let (TreeE (if (sym? Tree) (eval Tree) Tree))
(ifn (and TreeE (lst? TreeE))
(set Tree (list Key NIL NIL))
(recur (TreeE Key)
(when (and (car TreeE) (lst? (car TreeE)))
(setq TreeE (car TreeE)) )
(ifn (car TreeE)
(set TreeE (list Key NIL NIL))
(unless (= (car TreeE) Key)
(if (< (car TreeE) Key)
(recurse (cddr TreeE) Key)
(recurse (cdr TreeE) Key) ) ) ) ) ) ) )
(de bstInsertTco (Tree Key)
(let (TreeE (if (sym? Tree) (eval Tree) Tree))
(ifn (and TreeE (lst? TreeE))
(set Tree (list Key NIL NIL))
(tco
(TreeE Key)
(when (and (car TreeE) (lst? (car TreeE)))
(setq TreeE (car TreeE)) )
(ifn (car TreeE)
(set TreeE (list Key NIL NIL))
(unless (= (car TreeE) Key)
(if (< (car TreeE) Key)
(tc (cddr TreeE) Key)
(tc (cdr TreeE) Key) ) ) ) ) ) ) )
