Even if you cannot determine whether each result returned by your algorithm is correct, you probably can determine whether the distribution of results is correct. (This is what I had to do to test the random-data generators for Test::Lectrotest.)

First, analyze your algorithm to determine the expected distribution of the results. Then run your algorithm in a large number of random trials to generate a set of observed results. Finally, use statistical tests to determine whether the results conform to the expected distribution (for the level of confidence you desire).

There is a trade off between the degree of confidence you require and the "power" of statistical tests to detect small deviations from the norm. The more confidence you want, the less power the tests will have. The way to increase the power is to run more trials. Unless you have a really bizarre distribution, however, a few seconds of compute time will probably provide more than enough data to provide ample confidence and power. (But still you should do the math to verify this for your situation.)

That is the idea. Now, to implement it, you will need to (1) determine the distribution of your expected results, (2) write a test driver to run the trials and collect the output results, and (3) write code to test the collected output against the expected distribution.

Steps (1) and (3) require some familiarity with statistics. (If you need a refresher, take a look at the resources on the Statistics on the Web page maintained by Clay Helberg.) If you are not writing unit tests to be automated, you can perform step (3) by hand in a statistics program like R. Otherwise, you will need to code up some statistical tests or borrow them (e.g., Statistics::ChiSquare) and call them from your unit tests.

I hope that this helps.

Cheers,
Tom

Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder

In reply to Re: Non-deterministic Testing by tmoertel
in thread Non-deterministic Testing by moot

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.