[Haskell-cafe] Re: Data.HashTable
gwern0 at gmail.com
gwern0 at gmail.com
Fri Mar 7 18:08:24 EST 2008
On 2008.03.06 22:43:53 +0100, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> 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).
> 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:
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>.
Air eavesdropping pipe-bomb TSCM Centro ^X JIC TWA USACIL Protection
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080307/248c8f7a/attachment.bin
More information about the Haskell-Cafe