# [plt-scheme] Timings

I am in the process of implementing various data structures.
One is ordinary sets represented by sorted lists.
Here is the straight implementation of union:
(define (union2 s1 s2)
(cond
[(null? s1) s2]
[(null? s2) s1]
[else (let ([x (car s1)]
[y (car s2)])
(cond
[(< x y) (cons x (union2 s2 (cdr s1)))]
[(> x y) (cons y (union2 s1 (cdr s2)))]
[else (cons x (union2 (cdr s1) (cdr s2)))]))]))
Then I noticed that in the cases (< x y) and (> x y) we know
that one of the lists is non-empty, thus it is unncessary to
test for this in the recursive call. This leads to this version:
(define (union s1 s2)
; union1 : set set -> set
; s1 is non-empty
(define (union1 s1 s2)
(cond
[(null? s2) s1]
[else (let ([x (car s1)]
[y (car s2)])
(cond
[(< x y) (cons x (union1 s2 (cdr s1)))]
[(> x y) (cons y (union1 s1 (cdr s2)))]
[else (cons x (union (cdr s1) (cdr s2)))]))]))
(if (null? s1)
s2
(union1 s1 s2)))
To get some timings I use:
(define (interval m n)
(if (> m n)
'()
(cons m (interval (add1 m) n))))
>* (let ([s1 (interval 1 100000)]
* [s2 (interval 50000 150000)])
(collect-garbage)
(time (union2 s1 s2))
(collect-garbage)
(time (union s1 s2))
(void))
cpu time: 3475 real time: 3575 gc time: 0
cpu time: 4176 real time: 4196 gc time: 0
Then I tried:
>* (let ([s1 (interval 1 100000)]
* [s2 (interval 50000 150000)])
(collect-garbage)
(time (union s1 s2))
(collect-garbage)
(time (union2 s1 s2))
(void))
cpu time: 3125 real time: 3125 gc time: 0
cpu time: 4246 real time: 4267 gc time: 0
... and now I'm confused.
Which union is faster?
--
Jens Axel Søgaard