[plt-scheme] Hash Table implementation

From: David Einstein (deinst at gmail.com)
Date: Fri Aug 3 13:18:55 EDT 2007

Inspired by Jens and Grant, I decided to try my hand at some of the Project
Euler problems using PLT scheme, to see what it was capable of.  It has
proven itself capable on the few problems that I have completed so far, but
I just ran into what appears to be a bug of sorts.  It appears that the
hash-table implementation does not expand as more keys are added, and so if
the table reaches a certain size things slow down dramatically.  For example

(require (lib "42.ss" "srfi"))

(define (randfrac n)
  (/ (+ 1 (random n)) (+ 1 (random n))))

(define ht (make-hash-table 'equal))
(time (do-ec (: a 1 1000) (hash-table-put! ht (randfrac 1000) #t)))
(time (do-ec (: a 1 10000) (hash-table-put! ht (randfrac 1000) #t)))
(time (do-ec (: a 1 100000) (hash-table-put! ht (randfrac 1000) #t)))

results in

Welcome to DrScheme, version 370 [3m].
Language: Graphical (MrEd, includes MzScheme); memory limit: 1024 megabytes.
cpu time: 0 real time: 0 gc time: 0
cpu time: 125 real time: 125 gc time: 0
cpu time: 13047 real time: 13047 gc time: 0
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20070803/6fa6d523/attachment.html>

Posted on the users mailing list.