## Testing non-deterministic methods

Expand Messages
• Hi, I m puzzled with the challenge to write tests to methods that return arbitrary output. Is it possible? I mean, good tests that are actually meaningful (I
Message 1 of 34 , Nov 27, 2008
Hi,

I'm puzzled with the challenge to write tests to methods that return
"arbitrary" output. Is it possible?
I mean, good tests that are actually meaningful (I can think of testing for
data types, which I don't think is of much use...).

Specifically, I'm writing a "home made" Python program to treat graphs, and
some common algorithms in this field do not work as 2 + 2 = 4, since there
may be several right answers to problems like finding a Minimum Spanning
Tree.
I would now write a polynomial algorithm to find a candidate solution to the
Travelling Salesman Problem using some heuristics (so, I don't intend to
find the best solution, just one that is close), and have no clue on how to
solve it trough TDD.

Insights?

(I may propose this task to a dojo session soon if we're lucky!)

Rodolfo Carvalho

[Non-text portions of this message have been removed]
• FWIW, I think one of the sources of bugs in programs relying on random numbers, is when the numbers are untypical but theoretically possible -- e.g. all the
Message 34 of 34 , Dec 3, 2008
FWIW, I think one of the sources of bugs in programs' relying on
random numbers, is when the numbers are "untypical" but theoretically
possible -- e.g. all the "random" numbers are zero, or all are a large
number, or are all even numbers, or all are prime, etc. It's not that
the numbers are buggy, it's the logic that assumes these untypical
sequences won't happen.

On Wed, Dec 3, 2008 at 2:07 PM, Julian Hall <jules@...> wrote:
> --- In extremeprogramming@yahoogroups.com, "kentb" <kentb@...> wrote:
>> I read Rodolfo's message differently. The question I heard was, "How
> do you
>> write assertions when multiple answers are acceptable?" It is
> exacerbated in
>> his case because calculating by hand for a realistic-sized problem is
>> difficult.
>>
>> The techniques I've used in cases like this (some of which were
> mentioned
>> * Work out some small problems by hand--"Given this simplified
> map, this
>> heuristic should produce Chicago-London-Katmandu as the shortest path".
>> These tests can verify that a heuristic behaves as expected.
> However, they
>> tend to produce false failures because in such algorithmic
> development you
>> often tweak heuristics.
>> * Make vaguer assertions about large problems--"Given this
> realistic map,
>> the algorithm should produce a path of less than 10,000 km". I think
> this
>> was what Rodolfo was proposing but he was concerned that they
> wouldn't drive
>> development in the same way ordinary TDD tests do. They also tend to run
>> slowly (which I suppose is part of their lack of drive).
>> * Run an exhaustive algorithm in parallel with the optimized
> algorithm on
>> a small data set and compare the results, either for an exact match or a
>> ratio.
>> * Compare the output of versions of the optimized algorithm to
> make sure,
>> for example, that the answers never get worse.
>>
>> All in all, heuristic algorithm development is not the sweet spot
> for TDD,
>> although tests can still support such development.
>>
>> Cheers,
>>
>> Kent
>
>
> As this is something I've been working on recently, I thought I'd
> share my experiences. The problem domain of my current project is
> machine learning, specifically neural networks and "simulated
> annealing" optimization of parameters.
>
> Some of the tests I've found useful:
>
> * A by-hand calculated example. You can do simple neural networks by
> hand and work out how an iteration or two should cause the network to
> be updated.
> * Tests designed to force the algorithm down specific paths. I've
> been using implementations of java.util.Random that return a
> hand-picked sequence that causes the situation I want to test.
> * "Gold standard" tests: run the algorithm on a particular input with
> a standard Random seeded to a known value, then check the result
> manually. If it's acceptable, set up a test that breaks if it changes.
>
> A slight variant of this suggestion:
>
>> Make vaguer assertions about large problems--"Given this realistic map,
>> the algorithm should produce a path of less than 10,000 km". I think
> this
>> was what Rodolfo was proposing but he was concerned that they
> wouldn't drive
>> development in the same way ordinary TDD tests do. They also tend to run
>> slowly (which I suppose is part of their lack of drive).
>
> Because my algorithm is probabilistic and I only expect it to work on
> 95% of runs, I need to fix the random number generator seed to ensure
> the test runs every time. If a change breaks it, I have to try a few
> additional seeds to check it hasn't just shifted the meaning of the
> random seed and the new one is one of the few that doesn't work.
>
>
>
> ------------------------------------
>
> To Post a message, send it to: extremeprogramming@...
>
> To Unsubscribe, send a blank message to: extremeprogramming-unsubscribe@...
>