[Haskell-cafe] (no subject)

[Eugene Kirpichov]

There are also the judy arrays
http://hackage.haskell.org/package/HsJudy
http://hackage.haskell.org/package/judy

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