[Haskell-cafe] (no subject)

Eugene Kirpichov ekirpichov at gmail.com
Thu Oct 15 02:15:46 EDT 2009

There are also the judy arrays

dons recently advertised the latter as being 2x faster than IntMap,
but I don't know in what respect these two packages differ and why Don
decided to create 'judy' despite the existence of HsJudy.

2009/10/15 wren ng thornton <wren at freegeek.org>:
> Jake McArthur wrote:
>> staafmeister wrote:
>>> Yes I know but there are a lot of problems requiring O(1) array updates
>>> so then you are stuck with IO again
>> Or use ST. Or use IntMap (which is O(log n), but n is going to max out on
>> the integer size for your architecture, so it's really just O(32) or O(64),
>> which is really just constant time).
> Actually, IntMap is O(min(n,W)) where W is the number of bits in an Int.
> Yes, IntMaps are linear time in the worst case (until they become
> constant-time). In practice this is competitive with all those O(log n)
> structures though.
> Whereas Data.Map is O(log n) for the usual balanced tree approach.
> --
> Live well,
> ~wren
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Eugene Kirpichov
Web IR developer, market.yandex.ru

More information about the Haskell-Cafe mailing list