;;; BENCHMARK SETS
; AVL
(require (planet "sets.scm" ("oesterholt" "datastructs.plt" 1 0)))
;;; DATA CONSTRUCTION (to prepare for the benchmark)
; Create a list of overlapping intervals
; (0 2 ... 2N-1) (N ... 3N-1) ... ((K-1)N ... (K+1)N-1)
(define N 300)
(define K 300)
(require (lib "42.ss" "srfi"))
(define intervals (list-ec (: k K)
(list-ec (: n (* k N) (* (+ k 2) N))
n)))
; The same intervals, but now as sets.
(define (list->set xs)
(let loop ([s (set = <)]
[xs xs])
(if (null? xs)
s
(loop (set+ s (car xs)) (cdr xs)))))
(define sets
(map (lambda (xs) (list->set xs))
intervals))
;;; LIST -> SET
(define lists-with-duplicates
(map (lambda (l) (append l l))
intervals))
(time
(begin
; conversion from list to set
(map (lambda (xs) (list->set xs))
lists-with-duplicates)
'list->set))
;;; LIST OF SETS -> UNION
(time
(begin
; union of a list of sets
(foldl set-union (set = <) sets)
'union))
;;; LIST OF SETS -> INTERSECTION
; intersection between sets with overlap
(time
(begin
(let loop ([sets sets])
(if (or (null? sets) (null? (cdr sets)))
'intersection
(begin
(set-intersection (car sets) (cadr sets))
(loop (cdr sets)))))))
; N=300, K=300
; cpu time: 1141 real time: 1141 gc time: 0
; list->set
; cpu time: 114781 real time: 115094 gc time: 13824
; union
; cpu time: 672 real time: 672 gc time: 157
; intersection