2008/6/16 Jacob Perkins <<a href="mailto:japerk@gmail.com">japerk@gmail.com</a>>:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I ran the following code thru fprof using N=1000 for Mod=dict and Mod=rbdict. The basic results were that rbdict was ~10-20ms slower than dict for both store and fetch.<br><br>store(Mod, N) -><br>    Fold = fun(I, D) -> Mod:store(I, I, D) end,<br>

    lists:foldl(Fold, Mod:new(), lists:seq(1, N)).<br><br>fetch(Mod, N, Dict) -><br>    Map = fun(I) -> Mod:fetch(I, Dict) end,<br>    lists:map(Map, lists:seq(1, N)).<font color="#888888"></font></blockquote><div>
<br>This is expected, rb-trees are O(n lg n) but dict is based on a hashing algorithm as is almost O(1).<br><br>Here are some more comparisons done on a 10k element random list:<br><br>           Insert      Fetch       Update      Delete<br>
<br>dict        31.8        6.64        22.345      21.09<br>rbdict      28.36       8.435       27.11       21.795<br>gb_trees    22.105      9.61        17.735      15.235<br>            30.94                   28.825      24.845<br>
<br>Pardon the alignment but it looks ok with constant width.<br><br>Gb_trees have two values each for inserting/updating/deletion as it has two functions for each depending on whether you know if the element is in the tree or not. It is faster if you know. The dict modules don't have this separation in the interface.<br>
</div></div><br>The benefit of using rbdict (and gb_trees) is that it is a much lighter structure. It is also ordered but there is no interface for this. Which one you choose depends of course on your application and it is easy to use the different modules and measure. Even testing with gb_trees is easy as the interfaces are close.<br>
<br>Robert<br><br>