[erlang-questions] Data structures are strange things

[Robert Virding]

I have some more data to add. I did a quick version of AVL trees so the final data is: 

----- Original Message -----

> Here are the figures. I have also included dict, which is the slowest
> on insertion/deletion but significantly faster lookup times. All
> times are in usecs for the whole set:

> Operation                        Load        Fetch       Load
>        Fetch
> # of elements                         100000                  10000
> Overhead time                          43000                   3700

avldict     AVL trees             430000      150000      31000       14500 
> ttdict 2-3 trees 310000 161000 24000 15500
> ttfdict 2-3-4 trees 312000 173000 24200 16500
> llrbdict Left Leaning RB trees 390000 164000 27100 14900

> rbdict Red Black trees 380000 167000 27100 15000
> aadict AA trees 423000 167000 30000 15000

> gb_trees using faster insert/3 370000 190000 26500 16200
> dict 522000 107000 28000 11000
I hope the table is still readable. The loading for AVL trees can be made faster as the algorithm I use is quite naive and probably does too much copying. As Richard C pointed out the RB trees, AA trees and now AVL trees all need an extra field, which the 2-3 and 2-3-4 trees do not. So in terms of space 2-3-4 is better than 2-3 is better than gb_trees is better than other trees. The code size for 2-3-4 trees is bigger than for 2-3 trees, more alternatives to consider. Considering the added code size, though not really complexity, 2-3 trees seems to be a reasonable choice for a tree module with the dict API in terms of speed, code size and data size. Or maybe the Left Leaning RB trees and AVL trees. The fastest trees yet. 

Robert 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20120610/f4ce8a39/attachment.htm>