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?
[...]
Also, all DData functions have their complexity listed in the documentation.
See: <http://www.cs.uu.nl/~daan/ddata.html>
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)
In the Set module of DData the time complexities of difference and intersection are given as O(n + m). So I assume that the comlexities of minusSet and intersect from Data.Set are also O(n + m). Now assume that I have a set a with O(n) elements and a set b with O(1) elements. a `minusSet` b would take O(n) time and so would a `intersect` b. If I'd use foldr (flip delFromSet) a (setToList b) and [x | x <- setToList b, x `elementOf` a] instead of a `minusSet` b and a `intersect` b, I would get away with O(log n) time. Is this true? Wolfgang