On Wed, 26 May 2004 10:53:54 +0100, Adrian Hey wrote:

I got these results:

For 500,000 random elements Insert Lookup Delete Data.Tree.AVL 0.923 0.203 0.798 Data.FiniteMap 1.150 0.203 1.259 DData.Map 1.177 0.205 1.084 DData.IntMap 0.648 0.163 0.627

For 500,000 ordered elements: Insert Lookup Delete Data.Tree.AVL 0.210 0.060 0.117 Data.FiniteMap 0.473 0.076 0.137 DData.Map 0.488 0.079 0.145 DData.IntMap 0.108 0.039 0.054

Very cool results for AVL :-)

We still have no idea how well AVL trees perform for set operations (haven't written the necessary code yet).

Let me take this opportunity to remind us all of being careful when interpreting these numbers: most programs don't just insert and lookup in that order, but mix the operations in a lazy fashion which can lead to wildly different results. Furthermore, I tend to use "union" a lot -- I know/suspect from simple tests that DData.IntMap tends to outperform Data.Map by a wide margin on those kind of operations, etc. Btw. Given the good performance of AVL, maybe we should try to make the interface look like DData.Map (or maybe provide a seperate AVL.Map module to does that). This would allow one to use IntMap, AVL.Map or Map without changing (much) code. All the best, Daan.

I can post the test code to anyone who wants it. The mods to test287.hs are:

Removed size calculation, as this O(n) for AVL trees but O(1) for FiniteMap and DData.map and is irrelevant to insertion/deletion times.

Increased testData size from 100,000 to 500,000.

Used foldl' instead of foldr to prevent stack overflow.

PerformGC at start of each test in test10

Had to swap args of Map.lookup in lookupsMap

Changed the way results are displayed to be more comprehensible (to me:-)

Regards -- Adrian Hey

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries