# 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

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