;;; 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