[Haskell-cafe] (no subject)
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,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
Web IR developer, market.yandex.ru
More information about the Haskell-Cafe