from array update algorithm to nice Haskell code
Daan Leijen
daanleijen at xs4all.nl
Wed Dec 31 14:35:24 EST 2003
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
>
More information about the Haskell
mailing list