#lang racket (require racket/random) (define (make-keys n) (shuffle (build-list n (lambda (i) (crypto-random-bytes 64))))) (define (build-table/null keys) (void)) (define (build-table/alist keys) (let walk ((keys keys)) (match keys ['() '()] [(cons key rest) (cons (cons key key) (walk rest))]))) (define (build-table/hash keys) (let walk ((keys keys)) (match keys ['() (hash)] [(cons key rest) (hash-set (walk rest) key key)]))) (define (probe/null table key) #f) (define (probe/alist table key) (cond [(assoc key table) => cdr] [else #f])) (define (probe/alist/missing table key) (cond [(assoc 'NOT-PRESENT table) => cdr] [else #f])) (define (probe/hash table key) (hash-ref table key #f)) (define (probe/hash/missing table key) (hash-ref table 'NOT-PRESENT #f)) (module+ main (define TOTAL-ITERATIONS 1000000) (define-syntax-rule (time-expr keys builder prober) (let* ((num-keys (length keys)) (repeats (/ TOTAL-ITERATIONS num-keys)) (table (builder keys))) (define start-time (current-inexact-milliseconds)) (for* [(i (in-range repeats)) (key (in-list keys))] (prober table key)) (define stop-time (current-inexact-milliseconds)) (define delta (/ (- stop-time start-time) 1000.0)) (define per-repeat (/ delta repeats)) (define per-key (/ per-repeat num-keys)) (printf "~a,~a,~a,~a,~a,~a\n" num-keys (* repeats num-keys) 'prober per-key per-repeat delta) (flush-output))) (for [(num-keys (in-list '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 30 35 40 45 50 ;; 55 60 65 70 75 80 85 90 95 100 ;; 110 120 130 140 150 160 170 180 190 200 ;; 220 240 260 280 300 ;; 350 400 450 500 550 600 )))] (let ((keys (make-keys num-keys))) (collect-garbage) (collect-garbage) (collect-garbage) (time-expr keys build-table/null probe/null) (collect-garbage) (collect-garbage) (collect-garbage) (time-expr keys build-table/alist probe/alist) (collect-garbage) (collect-garbage) (collect-garbage) (time-expr keys build-table/hash probe/hash) (collect-garbage) (collect-garbage) (collect-garbage) (time-expr keys build-table/alist probe/alist/missing) (collect-garbage) (collect-garbage) (collect-garbage) (time-expr keys build-table/hash probe/hash/missing))) )