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