Data.HashTable

Johannes Waldmann waldmann at imn.htwk-leipzig.de
Thu Mar 6 16:43:53 EST 2008


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> In practice, Data.Map outperforms it in essentially all cases
> (Data.HashTable stops working beyond a certain size and so any
> asymptotic benefits, if they exist at all, don't have time to kick
> in). 

What!

I learned at school, and I teach my students,
* balanced binary tree: costs are log(size)
* hashtable: cost are essentially constant
therefore, hashtable should be preferred in almost all cases
(if you know a reasonable hash function
and except where you need persistency, of course)

the difference should be visible even for moderate sizes
(e.g. 1000). With a reasonable implementation  I expect
log(1000) = 10 comparisons (and dereferencings) for the tree;
while the hashtable should have the computation of the hash value
(ideally, in registers), one memory access, and one comparison.

... but indeed some experiments with Data.Map and Data.Hashtable
support the point you made. That's either good for Data.Map
or bad for Data.Hashtable.

PS: I did not manage to compile HsJudy-1.0 with ghc-6.8.2
(some hsc file missing - perhaps that should be auto-generated? how?)

Best regards, Johannes.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFH0GWZ3ZnXZuOVyMIRAn6FAJ4khFeY0F9dKnB0XyztmUEJq7SiGwCeMm7j
cinyds0gCbVeHMcCLY4jP2w=
=K9V5
-----END PGP SIGNATURE-----


More information about the Libraries mailing list