[erlang-questions] Sets and Dict test suites

[James Aimonetti]

Robert,

Thanks for the suggestions and the db_test.erl. I've been playing with 
my implementation of sets and dict using splay trees and think I've 
concluded that they are not useful as a backend for the sets and dict 
API (barring a complete mucking of the implementation: 
http://github.com/jamesaimonetti/splay). The main issue I ran into is 
that splay trees rely on blindly restructuring after queries, as well as 
inserts and deletions, to improve the balanced nature of the tree. I 
re-read the section (5.4) in Okasaki's book and he does mention this 
shortcoming in using splays for sets and finite maps. I've included a 
bare bones splay implementation with add, find_min, has, delete, and 
delete_min, as well as some others like size and height, for creating a 
heap within an application.

Any feedback is appreciated :)

James

Robert Virding wrote:
> Hi James,
>
> Sorry, I saw your earlier mail but I missed it.
>
> I have used a relatively simple test suite when writing my RB and AA
> stuff. First I use all the examples given in books and papers and
> check that my trees look the same as theirs. This, of course, only
> works for small data sets. I also just sit and add and delete elements
> from the shell and check that the tree looks right.
>
> When I am satisfied that it looks right I try some bigger data sets.
> Easy ways to generate them are functions like:
>
> random_data(N) -> [ {random:uniform(),I} || I <- lists:seq(1, N) ].
>
> which generates a set of {Key,Value} pairs with random keys. I use
> such a set to build a dict. I then use the same set to 'fetch' all the
> keys to test that they are there and that I can reach them. Then I use
> the same and delete all the keys to check that I can and that the
> final dict is empty as it should be. It would better to both 'fetch'
> and delete each key to make sure that the tree is always consistent
> during deletes. I found deleting harder than adding.
>
> You can also do the same thing with non-random data sets to see if you
> get some funny trees, for example your tree degenerates to a list.
> Another good and simple test is to just count the depth of each node
> and see that you get a reasonable spread of the depth, i.e. that it
> really lg n like it should be.
>
> I do some simple unit testing by saving problem cases so I can retry them.
>
> I also have a test file for comparing various algorithms which is
> useful for testing as well. Run it through the compiler and generate
> the file after the macro expansions to see the resultant code,
> c(db_test, ['E']). There are some comments but it is really an
> internal file.
>
> Not very scientific I know but it seems to work. Also the trees
> quickly become unreadable when they grow big. I hope you do the
> splaydict and splaysets, I would like to see them. Real soon now (TM)
> I will adding rbdict and rbsets to the distribution. There are also
> some extensions to the API I would like to add.
>
> I hope this helps,
>
> Robert
>
>
> On 5 April 2010 21:27, James Aimonetti <james.aimonetti@REDACTED> wrote:
>   
>> Does anyone on the list have test suites for testing sets and dict
>> functionality using different backends? I'm going through Okasaki's book and
>> currently implementing the splay trees, and, having looked at the rbsets and
>> rbdict using red-black trees, I wanted to try implementing the API using the
>> splay trees and testing the results against the official implementations.
>>
>> Also, is there any writeup of the backends' strengths vs weaknesses for
>> various use cases (as concerns Erlang specifically)? If not, I'd be
>> interested in developing one if those with more experience could offer help
>> as I worked on it.
>>
>> Thanks,
>>
>> James
>>
>> --
>> James Aimonetti
>> mobile: 314.809.6307
>> work: 540.459.2220
>> email: james.aimonetti@REDACTED
>> website: http://jamesaimonetti.com
>>
>>
>> ________________________________________________________________
>> erlang-questions (at) erlang.org mailing list.
>> See http://www.erlang.org/faq.html
>> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>>
>>
>>     


-- 
James Aimonetti
mobile: 314.809.6307
work: 540.459.2220
email: james.aimonetti@REDACTED
website: http://jamesaimonetti.com