31 Dec
2003
31 Dec
'03
11:35 a.m.
Am Mittwoch, 31. Dezember 2003 00:06 schrieb Daan Leijen:
Hi Wolfgang,
is there some documentation about the complexity of the FiniteMap and Set operations?
[...]
The operations in the "Data.FiniteMap" library in Ghc have the same complexity of the operations in the "DData.Map" library. The "Data.Set" library in Ghc is based on the FiniteMap library (and thus has the same complexity)
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?
[...]
Wolfgang