Loading ...
Sorry, an error occurred while loading the content.
 

RE: [XP] Testing non-deterministic methods

Expand Messages
  • kentb
    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
      already) are:
      * 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]
    • Keith Ray
      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
        >> already) are:
        >> * 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.