[erlang-questions] Sets and Dict test suites

[Robert Virding]

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
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: db_test.erl
Type: application/octet-stream
Size: 6037 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20100406/16fd560e/attachment.obj>