On Wed, 31 Dec 2003 12:35:23 +0100, Wolfgang Jeltsch <wolfgang@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell