from array update algorithm to nice Haskell code

[Daan Leijen]

On Wed, 31 Dec 2003 12:35:23 +0100, Wolfgang Jeltsch <wolfgang at jeltsch.net> wrote:

> The documentation of DData.Map states the following as an advantage of
> DData.Map over Data.FiniteMap:
>     It uses the efficient hedge algorithm for both union and difference [...].
> Does this mean that the Data.FiniteMap functions for union and difference
> don't have an O(n + m) complexity as the DData.Map functions have?

No. Even though a "hedge" algorithm is generally more efficient, it doesn't
change the complexity class -- just the absolute efficiency. According to
measurements done by Stephen Adams, it is about 20% faster (for strict programs).

In my experience, the absolute efficiency is pretty important, especially for
small data sets and Haskell :-), for example, for small data sets, a simple list
is more efficient than a Set data type in many common situations.

Therefore, you will only notice the difference for "hedge" unions when you
use large data sets.

-- Daan.


>> [...]
>
> Wolfgang
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>