On 2008.03.06 22:43:53 +0100, Johannes Waldmann scribbled 1.4K characters:

...

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.

Oh... I'm terribly sorry about that. It was I who uploaded HsJudy. The problem was, it's maintained by the Pugs project for some reason. The directory structure looks like: pugs/ thirdparty/ HsJudy/ hsregex/ HsSyck/ installed/ judy/ Judy-1.0.3/ Here Judy-1.0.3/ contains the actual C library Judy itself. So what the Cabalized package residing in HsJudy/ was doing was literally linking against stuff like '../judy/Judy-1.0.3/src/JudyL/*.o'. At the time I was packaging, Cabal didn't yet warn about problems like ../, so it would build and install just fine when I ran it with no problems; but I forgot that obviously all the ../ stuff would totally break in an sdist tarball. I think I've fixed it: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsJudy-0.1.1. -- gwern Air eavesdropping pipe-bomb TSCM Centro ^X JIC TWA USACIL Protection