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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
