from array update algorithm to nice Haskell code
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 there some hints about how to do this? Wolfgang
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 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) On Tue, 30 Dec 2003 23:14:05 +0100, Wolfgang Jeltsch <wolfgang@jeltsch.net> wrote:
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 there some hints about how to do this?
Storing the incremental changes might be a good options. You can get this somewhat automatically by using (lazy) balanced trees -- every insertion/update will only copy the changed 'path' in the tree, giving you a logarithmic copy time while being persistent (maintaining all old versions). -- Daan.
Wolfgang
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Tue, 30 Dec 2003 23:14:05 +0100, Wolfgang Jeltsch <wolfgang@jeltsch.net> 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 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 there some hints about how to do this?
You may want to look at DiffArrays http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.Array.Diff.h...
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 "Data.Set" library in Ghc is based on the FiniteMap library (and thus has the same complexity)
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 functions for union and difference don't have an O(n + m) complexity as the DData.Map functions have?
[...]
Wolfgang
On Wed, 31 Dec 2003 12:35:23 +0100, Wolfgang Jeltsch <wolfgang@jeltsch.net> 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 functions for union and difference don't have an O(n + m) complexity as the DData.Map functions have?
No. Even though a "hedge" algorithm is generally more efficient, it doesn't change the complexity class -- just the absolute efficiency. According to measurements done by Stephen Adams, it is about 20% faster (for strict programs). In my experience, the absolute efficiency is pretty important, especially for small data sets and Haskell :-), for example, for small data sets, a simple list is more efficient than a Set data type in many common situations. Therefore, you will only notice the difference for "hedge" unions when you use large data sets. -- Daan.
[...]
Wolfgang
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
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
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 (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.
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. However, in the worst case, this will degenerate to some "m" number of elements, and your function would take O(m*log n) time, i.e. much worse than O(n+m). All the best, Daan.
Is this true?
Wolfgang
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
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 analysis. According to [1] O is just something like O :: (Natural -> Natural) -> Set (Natural -> Natural) O f = {g | exists c. exists n0. forall n >= n0. g n <= c * f n}. Based on this definition, I mean that I have a quantity n (e.g. the size of a base set), and the size of the set a is less than c * n for some constant c while the size of b is always less than a constant c'.
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.
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 element.
However, in the worst case, this will degenerate to some "m" number of elements, and your function would take O(m*log n) time, i.e. much worse than O(n+m).
I don't understand this. If m doesn't depend on any input values but is really constant then O(m * log n) = O(log n)—regardless of how large m is. Well, the specification of O(n + m) time does only say that the time is less than c * (n + m) of some constant c which is no contradiction to an O(log n) time. But it leaves the possibility open that the calculation really needs linear time.
All the best, Daan.
[...]
Wolfgang [1] Schöning, Theoretische Informatik – kurzgefasst, Spektrum Akademischer Verlag
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 element.
Ah, I think I have the gist of your message now. For DData.Set, the worst case bound for intersect is O(n+m), however, for your particular case, it will behave as you want. i.e. for an intersection where one of the sets is empty, it will run in constant time; for an intersection where one of the sets has one element, it will take at most O(log n) time (where n is the number of elements in the other set). This is again a worst case bound: if n is zero (the empty set), it will be a constant time operation. Even stronger, if you ask for the intersection of two large sets that have no common elements, the operation will take (log n + log m) time. Still, in the worst case, where both trees have about the same size and the same kind of elements, the algorithm will degenerate to O(n+m). (btw. this is not the case when you would simply iterate over one set and test membership of the other (= O(m*log n))) I am not entirely sure if this also holds for Data.Set, but I guess it is the same. A small issue is that it *does* pay off to swap the arguments if their size differs (just as in your list example), and I don't know if Data.Set does that -- you should look in the CVS sources to find out. If you think that application to the sets with single values happens often, maybe I should add some special-case code to make this more (absolutely) efficient. All the best, Daan.
However, in the worst case, this will degenerate to some "m" number of elements, and your function would take O(m*log n) time, i.e. much worse than O(n+m).
I don't understand this. If m doesn't depend on any input values but is really constant then O(m * log n) = O(log n)—regardless of how large m is.
Well, the specification of O(n + m) time does only say that the time is less than c * (n + m) of some constant c which is no contradiction to an O(log n) time. But it leaves the possibility open that the calculation really needs linear time.
All the best, Daan.
[...]
Wolfgang
[1] Schöning, Theoretische Informatik – kurzgefasst, Spektrum Akademischer Verlag
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
participants (3)
-
Daan Leijen -
Derek Elkins -
Wolfgang Jeltsch