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

Re: [XP] Testing non-deterministic methods - accepting alternative valid results

Expand Messages
  • Jeff Grigg
    ... (I m a fan of the alternate algorithm idea -- as I posted on Gregorian-Julian conversion functions. And also see my comment below.) ... AND... * Assert
    Message 1 of 34 , Dec 1, 2008
    • 0 Attachment
      --- "kentb" <kentb@...> wrote:
      > I read Rodolfo's message differently. The question
      > I heard was,
      > "How do you write assertions when multiple answers
      > are acceptable?"
      > [...]
      >
      > The techniques I've used in cases like this (some of
      > which were mentioned already) are:
      > * Work out some small problems by hand--[...]
      > * Make vaguer assertions about large problems--"Given
      > this realistic map, the algorithm should produce a
      > path of less than 10,000 km". [...]
      > * Run an exhaustive algorithm in parallel with the
      > optimized algorithm on a small data set and compare
      > the results, [...]

      (I'm a fan of the "alternate algorithm" idea -- as I posted on
      Gregorian-Julian conversion functions. And also see my comment below.)

      > * Compare the output of versions of the optimized
      > algorithm to make sure, for example, that the
      > answers never get worse.

      AND...
      * Assert that the result is /one of/ the acceptable answers.

      IE: You CAN put "or" conditions into assertions.

      For the case below...
      assertTrue("ABD".equals(path) || "ACD".equals(path));

      When two possible answers are equally valid. And all other answers
      are invalid... Then assert that the answer is one of the valid ones.

      --- "Rodolfo Carvalho" <rhcarvalho@...> wrote:
      > Imagine a very simple graph with four vertices like this:
      >
      > A---(3)---B
      > | |
      > (1) (1)
      > | |
      > C---(3)---D
      >
      > (not a good repr. but...) the optimum distance from
      > A to D is 4, and there are 2 paths that are "right
      > answers" (ABD or ACD).
    • 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
      • 0 Attachment
        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.