;;; BENCHMARK SETS ; GALORE 2 (require (planet "set.ss" ("soegaard" "galore.plt" 2 0))) (require (lib "42.ss" "srfi") (lib "67.ss" "srfi")) ;;; 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) (define intervals (list-ec (: k K) (list-ec (: n (* k N) (* (+ k 2) N)) n))) ; The same intervals, but now as sets. (define sets (map (lambda (xs) (list->set integer-compare 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 integer-compare xs)) lists-with-duplicates) 'list->set)) ;;; LIST OF SETS -> UNION (time (begin ; union of a list of sets (foldl union (empty integer-compare) 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 (intersection (car sets) (cadr sets)) (loop (cdr sets))))))) ; N=300, K=300 ; cpu time: 1375 real time: 1390 gc time: 203 ; list->set ; cpu time: 25141 real time: 25250 gc time: 10734 ; union ; cpu time: 375 real time: 375 gc time: 234 ; intersection