interesting test of hash-table vs a-list

From: Brian Denheyer <>
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 :-)



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

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

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

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

(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 !

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

 (do ((i 0 (+ i 1)))
     ((> i n-trials))
    (string->symbol (string-append "s-"
                                   (number->string (random n))))

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

This archive was generated by hypermail 2.3.0 : Mon Jul 21 2014 - 19:38:59 CEST