On 2008.03.06 22:43:53 +0100, Johannes Waldmann <[EMAIL PROTECTED]> 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
pgpPeExTiZYSc.pgp
Description: PGP signature
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
