On Sunday 15 May 2011 11:34:33, Matthias Guedemann wrote:
Hi Manfred
It didn't make much of a difference in runtime doing it without toList. I'm not quite sure if it is really more efficient or not. Perhaps I would have to create dictonary with some millions entries in order to see a noticable difference?
Probably, Haskell is not very deterministic for memory / runtime forecasts :-)
In theory there should be no difference in complexity, both need one sweep over all entries of the Map. There could perhaps be a constant cost for constructing the list.
The call-tree for the list construction is similar to the call-tree that traverse builds. However, traverse assembles a new Map. While it's trivial to discard consumed list-cells (if the list is consumed sequentially), that is not so for Maps. Unless the compiler manages to completely eliminate the new Map, that is going to cost considerably more than the throwaway list-cells.
Nevertheless, laziness should make it possible to run in constant space, as neither the list, nor the transformed Map is used.
Well, you need the space for the initial Map, that is O(size). I assume you mean that the additional memory needed is O(1). That is almost true for going through the list, since that is swiftly collected. The call-tree to get at the elements, however, is O(log size), but that's practically constant size. For traverse, that is only true if the new Map is completely discarded (Maps are spine-strict, so if it's not completely ignored, its full spine is built, requiring O(size) space).
So differences are probably small.
But is possible, take some measurements and report, not just runtime, but also heap space usage.
Note that the "mapM_ print . toAscList" prints the (key, value) pairs while the traverse (or Data.Traversable.mapM) only prints the values. That makes a difference. I put together a small (trivial) test: viaList :: (Ord k, Show k, Show v) => Map k v -> IO () viaList = mapM_ print . toAscList -- and the same using elems instead of toAscList to only print the values perTraverse :: (Ord k, Show v) => Map k v -> IO () perTraverse mp = traverse print mp >> return () main :: IO () main = do args <- getArgs let sz = case args of (a:_) -> read a _ -> 100000 mp :: Map Int Int mp = fromDistinctAscList [(i,2*i+1) | i <- [0 .. sz]] print $ size mp -- force the spine perTraverse mp -- or via list (pairs/values only) Everything compiled with -O2 (output redirected to /dev/null), the results for input 1000000 are: ./useElems 1000000 +RTS -s 1,026,031,460 bytes allocated in the heap 247,759,432 bytes copied during GC 40,026,204 bytes maximum residency (8 sample(s)) 353,148 bytes maximum slop 103 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 1869 collections, 0 parallel, 0.53s, 0.53s elapsed Generation 1: 8 collections, 0 parallel, 0.48s, 0.49s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 1.54s ( 1.55s elapsed) GC time 1.01s ( 1.02s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2.56s ( 2.56s elapsed) %GC time 39.6% (39.7% elapsed) Alloc rate 664,729,202 bytes per MUT second Productivity 60.3% of total user, 60.1% of total elapsed ---------------------------------------- ./useAscList 1000000 +RTS -s 1,337,743,996 bytes allocated in the heap 247,972,620 bytes copied during GC 40,026,204 bytes maximum residency (8 sample(s)) 413,304 bytes maximum slop 103 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 2467 collections, 0 parallel, 0.53s, 0.53s elapsed Generation 1: 8 collections, 0 parallel, 0.45s, 0.45s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 2.23s ( 2.23s elapsed) GC time 0.98s ( 0.99s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 3.22s ( 3.22s elapsed) %GC time 30.6% (30.7% elapsed) Alloc rate 599,228,735 bytes per MUT second Productivity 69.3% of total user, 69.3% of total elapsed ---------------------------------------- ./useTraverse 1000000 +RTS -s 1,266,460,972 bytes allocated in the heap 568,553,592 bytes copied during GC 61,013,024 bytes maximum residency (10 sample(s)) 614,608 bytes maximum slop 159 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 2328 collections, 0 parallel, 1.32s, 1.32s elapsed Generation 1: 10 collections, 0 parallel, 1.18s, 1.18s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 1.82s ( 1.83s elapsed) GC time 2.50s ( 2.50s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 4.32s ( 4.33s elapsed) %GC time 57.8% (57.8% elapsed) Alloc rate 695,540,479 bytes per MUT second Productivity 42.1% of total user, 42.0% of total elapsed ---------------------------------------- Data.Traversable.traverse uses more memory. Not twice as much, since the original Map is disassembled while traversing it. If I force the original Map to stay intact, it's about twice. I conclude that the new Map assembled by traverse is not discarded. So, overall, going through the list is better. Cheers, Daniel