interesting test of hash-table vs a-list

From: Brian Denheyer <briand_at_deldotd.com>
Date: Thu, 29 Apr 1999 20:03:34 -0700 (PDT)

I ran a simple test of hash-tables vs. a-lists, bith using eq?, to see
where the "break-even" point was for efficiency in terms of accessing
the elements.

It turns out a-lists are with 10% of the running speed of hash-tables
until there are > 60 elements in the list/table.

I didn't expect the break-even to occur for that high a number, I
figured it would occur down around 10 or 20 elements.

Just thought I'd share the results :-)


Brian

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; when is a hash better than an a-list ?

(define n 65)

(define t (make-hash-table eq?))

(do ((i 0 (+ i 1)))
    ((> i n))
  (hash-table-put! t
                   (string->symbol (string-append "s-" (number->string i)))
                   i))

(define alist
  (let loop ((i 0))
    (if (> i n)
        '()
        (cons (list
               (string->symbol (string-append "a-" (number->string i)))
               i)
              (loop (+ i 1))))))

(display "alist\n")
(display alist)
(newline)

(display "hash-table\n")
(hash-table-for-each
 t
 (lambda (key value)
   (format #t "~A:~A\n" key value)))
(newline)

(define n-trials 40000)

;; display was used to verify the test was running correctly and then
;; I took it out. The display of a two-element list is much slower
;; than the display of an integer !

(time
 (do ((i 0 (+ i 1)))
     ((> i n-trials))
   (assq
    (string->symbol (string-append "a-"
                                   (number->string (random n))))
    alist)))

(time
 (do ((i 0 (+ i 1)))
     ((> i n-trials))
   (hash-table-get
    t
    (string->symbol (string-append "s-"
                                   (number->string (random n))))
    #f)))

(exit)
Received on Fri Apr 30 1999 - 05:04:56 CEST