Sorry, an error occurred while loading the content.

## RE: [XP] Testing non-deterministic methods

Expand Messages
• Victor, I read Rodolfo s message differently. The question I heard was, How do you write assertions when multiple answers are acceptable? It is exacerbated
Message 1 of 34 , Dec 1, 2008
Victor,

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

_____

From: extremeprogramming@yahoogroups.com
[mailto:extremeprogramming@yahoogroups.com] On Behalf Of Victor
Sent: Thursday, November 27, 2008 6:58 AM
To: extremeprogramming@yahoogroups.com
Subject: Re: [XP] Testing non-deterministic methods

Hi Rodolfo,

I have the impression you are confusing two different kinds of tests, TDD
and acceptance.

The purpose of TDD is to validate that the mechanics of the code are
working, while the purpose of acceptance is to additionally verify that the
outputs are meaningful within the context of the application.

The computerized random calculations have a way of making the process
deterministic. You can use this for your TDD.
For the acceptance tests, you need to know what the range of expected values

is; then run the test a thousand times (or a million, or whatever large
number) and compare the results against the range. This is something very
easy to do in Smalltalk (use the properties of bags), and it could take no
more than a few seconds to run, depending on your system and number of
comparisons. I don't know about other languages.

Victor

======================

----- Original Message -----
From: "Rodolfo Carvalho" <rhcarvalho@gmail. <mailto:rhcarvalho%40gmail.com>
com>
To: <extremeprogramming@ <mailto:extremeprogramming%40yahoogroups.com>
yahoogroups.com>
Sent: Thursday, November 27, 2008 9:02 AM
Subject: Re: [XP] Testing non-deterministic methods

> On Thu, Nov 27, 2008 at 11:54, Olof Bjarnason
> <olof.bjarnason@ <mailto:olof.bjarnason%40gmail.com> gmail.com>wrote:
>
>>
>> ... and when I posted I saw how strange that remark was :)
>>
>> What you need to know is some kind of property about the correct
>> answer (length of path eg.) and having a way to measure that property
>> for you computed approxiate answer (length of path again). Then you
>> can compare them in your tests.
>
>
> I've used this kind of test (on output properties) for most of what I
> wrote,
> however, imho, it doesn't seem to force me, to drive me to the "good code"
> as I write more test cases.
>
> Roughly speaking, I could spit some random output that attends properties
> as
> length, having all vertices, etc, and still be absolutely far from an
> optimum solution.
>
>
> []'s
>
> Rodolfo
>
>
> [Non-text portions of this message have been removed]
>
>
> ------------------------------------
>
> To Post a message, send it to: extremeprogramming@
<mailto:extremeprogramming%40eGroups.com> eGroups.com
>
> To Unsubscribe, send a blank message to:
> extremeprogramming- <mailto:extremeprogramming-unsubscribe%40eGroups.com>
unsubscribe@...
>
> ad-free courtesy of objectmentor.comYahoo! Groups Links
>
>
>
>

[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@...
>
> ad-free courtesy of objectmentor.comYahoo! Groups Links
>
>
>
>

--
C. Keith Ray, IXP Coach, Industrial Logic, Inc.
http://industriallogic.com 866-540-8336 (toll free)
Groove with our Agile Greatest Hits: http://www.industriallogic.com/elearning/
http://agilesolutionspace.blogspot.com/
Your message has been successfully submitted and would be delivered to recipients shortly.