<div dir="ltr"><div>No, I never published them. I still have them of course. The one I prefer is the 2-3 trees which I use in my luerl implementation. Maps could replace them but they are lacking some functions I need. It will be interesting to see how they compare in speed.<br>
<br></div>Robert<br><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On 14 July 2014 08:40, Kirill Zaborsky <span dir="ltr"><<a href="mailto:qrilka@gmail.com" target="_blank">qrilka@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Robert,<div>I have came across this a bit old topic and I wonder - did you publish any of those modules?</div>
<div>I have only found your repo <a href="https://github.com/rvirding/rb" target="_blank">https://github.com/rvirding/rb</a> which is even 3 years older than this thread :)</div><div><br></div><div>Regards,</div><div>Kirill<br>
<br>пятница, 8 июня 2012 г., 4:55:29 UTC+4 пользователь Robert Virding написал:<div><div class="h5"><blockquote class="gmail_quote" style="margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div style="font-family:Times New Roman;font-size:12pt;color:#000000">
I was finally going to release some alternate modules with the dict interface using tree structures, either AA trees or Red Black trees. These are relatively well-known binary tree structures which are binary tree versions of 2-3 trees and 2-3-4 trees respectively. These contain codes with either 2, 3 or 4 sub-nodes. Generally the binary versions are recommended as being better/easier/more space efficient.<br>
<br>Before I released my modules I thought it would be interesting to try the non-binary versions to see how they behaved and what it was lie to program them. I was lucky to find a very good description of 2-3 trees and the rules for inserting/deleting elements; it was literally just translate the rules straight to Erlang and it worked. The code was a little more complex than working with the binary versions, not much. In some cases actually simpler. The I decided to measure speed, and the fun started.<br>
<br>All tests were done with sequences of random numbers as keys, the same for each implementation.<br><br>What I found was that the lookup times were about the same as for the binary versions, which was expected, but the insertion/deletion times were about 20% faster. This compared to my AA and RB tree versions. To check that it wasn't just bad coding on my part (not bloody likely :-)) I compared it with gb_trees and got the similar results. Also checking the data sizes I found that the 2-3 and 2-3-4 trees actually used *less* space than their binary counterparts.<br>
<br>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:<br><br><pre><pre>Operation Load Fetch Load Fetch<br>
# of elements 100000 10000<br>Overhead time 43000 3700<br></pre>ttdict 2-3 trees 310000 161000 24000 15500<br>
ttfdict 2-3-4 trees 312000 173000 24200 16500<br>llrbdict Left Leaning RB trees 390000 164000 27100 14900<br><br>rbdict Red Black trees 380000 167000 27100 15000<br>
aadict AA trees 423000 167000 30000 15000<br><br>gb_trees using faster insert/3 370000 190000 26500 16200<br>dict 522000 107000 28000 11000</pre>
<br>(I hope the table is readable)<br>Gb_trees are a variant of AA trees with a slightly different algorithm. One should be careful interpreting exact values here but the trend is clear.<br><br>I don't know why the straight multi-size versions are faster but my guess is that the pattern-matching/data construction is faster on the flat bigger nodes rather than on the nested pairs. My guess is that when they comment on the 2-3(-4) trees using more space it is because they use the same size node for all cases which in the cases with fewer sub-nodes wastes space, while just used different sized tuples which didn't waste space; it also made the pattern matching much easier.<br>
<br>It looks like I will be submitting the 2-3 tree version, ttdict, as reasonable choice. Next I will try AVL trees which were discarded long ago and see how they fare.<br><br>Robert<br><br>P.S. This is the reason why there was hoped to be many different dict modules with the same API but different data structures. So as it to make it easier to choose the most suitable version for each occasion. There is no generally "best" choice, even among trees.<br>
<br></div></div></blockquote></div></div></div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>