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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
