from array update algorithm to nice Haskell code
wolfgang at jeltsch.net
Fri Jan 9 19:17:48 EST 2004
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
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)
[x | x <- setToList b, x `elementOf` a]
instead of a `minusSet` b and a `intersect` b, I would get away with O(log n)
Is this true?
More information about the Haskell