Hi Wolfgang,
I think that you are mixing up worst case bounds O(..) with some specific
case. I guess that you mean by O(1) elements a known and constant number
of elements.
I mean a constant maximum number of elements. An example would be that the
set b is guaranteed to have not more than one
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
Now assume that I have a set a with O(n) elements and a set b with O(1)
elements.
You can't have O(1) elements ... (A bound like O(..) talks about
the worst case time/space of an operation.)
a `minusSet` b would take O(n) time and so would a `intersect` b.
If I'd use
foldr (flip delFromSet) a
Am Freitag, 9. Januar 2004 23:45 schrieb Daan Leijen:
Now assume that I have a set a with O(n) elements and a set b with O(1)
elements.
You can't have O(1) elements ... (A bound like O(..) talks about the worst
case time/space of an operation.)
Well, the O calculus isn't bound to resource
On Tue, 30 Dec 2003 23:14:05 +0100, Wolfgang Jeltsch
[EMAIL PROTECTED] wrote:
[replying indirectly because the original email doesn't seem to have
gotten here yet]
I have an algorithm which updates one or more arrays in a loop. The
update operations depend on the (old) contents of the
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
On Wed, 31 Dec 2003 12:35:23 +0100, Wolfgang Jeltsch [EMAIL PROTECTED] wrote:
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
Hello,
I have an algorithm which updates one or more arrays in a loop. The update
operations depend on the (old) contents of the arrays, so I cannot use
accumArray. I want to implement this algorithm without mutable arrays in
Haskell. Are there any possibilities to do so efficiently? Are
Hi Wolfgang,
is there some documentation about the complexity of the FiniteMap and Set operations?
My DData library gives some useful links to papers about this subject, also
take a look at the IntSet and IntMap libraries as they have an interesting
complexity class. Also, all DData functions
