from array update algorithm to nice Haskell code
Wolfgang Jeltsch
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
> 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
More information about the Haskell
mailing list