You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Benson Margulies <bi...@gmail.com> on 2009/12/23 18:43:40 UTC
[math]: how to test sorts
So, I'm staring at a file containing several copies of a very
carefully implemented versions of quickSort and mergeSort.
I'd like to remove the deprecation. I can feed it 4 things out of
order and get them back sorted. Is that good enough?
Re: [math]: how to test sorts
Posted by Isabel Drost <is...@apache.org>.
On Wednesday 23 December 2009 22:09:48 Grant Ingersoll wrote:
> Beyond that, we could start implementing Clover test coverage, I suppose.
It comes with the code quality reports added earlier. They are generated on a
daily basis through Hudson and are linked to in the dev section of our web
page. (The maven options to generate the reports locally are documented in
MAHOUT-210). However we should update report generation to Clover version
2.6.
Isabel
--
|\ _,,,---,,_ Web: <http://www.isabel-drost.de>
/,`.-'`' -. ;-;;,_
|,4- ) )-,_..;\ ( `'-'
'---''(_/--' `-'\_) (fL) IM: <xm...@spaceboyz.net>
Re: [math]: how to test sorts
Posted by Grant Ingersoll <gs...@apache.org>.
On Dec 23, 2009, at 3:52 PM, Benson Margulies wrote:
>>
>> If you want to test speed, then a pretty easy way is to pick permutations at
>> random, possibly emphasizing some kinds of permutations and run a sort for
>> those permutations using both algorithms. Measuring speeds and taking the
>> fastest iteration for each permutation should allow speed comparisons.
>
> Keep in mind that I am I not changing any algorithms. I want to get
> rid of the deprecations on the call graph of the collections code, if
> nothing else, and that call graph includes a mixed bag of nuts. So,
> what I'm really asking is this: when you all put deprecations on all
> of Colt, what level of testing did you anticipate doing before
> removing them?
>
I guess some testing, but by no means complete. Personally, I'd say if you write a test for it that does the reasonable thing (correct output on correct input and maybe some edge testing) then we can remove the deprecation, but just use your best judgment. Beyond that, we could start implementing Clover test coverage, I suppose.
Re: [math]: how to test sorts
Posted by Ted Dunning <te...@gmail.com>.
Functionality and correctness only. It could even be regression tests, but
we would obviously prefer real tests of correctness.
On Wed, Dec 23, 2009 at 12:52 PM, Benson Margulies <bi...@gmail.com>wrote:
> when you all put deprecations on all
> of Colt, what level of testing did you anticipate doing before
> removing them?
>
--
Ted Dunning, CTO
DeepDyve
Re: [math]: how to test sorts
Posted by Benson Margulies <bi...@gmail.com>.
>
> If you want to test speed, then a pretty easy way is to pick permutations at
> random, possibly emphasizing some kinds of permutations and run a sort for
> those permutations using both algorithms. Measuring speeds and taking the
> fastest iteration for each permutation should allow speed comparisons.
Keep in mind that I am I not changing any algorithms. I want to get
rid of the deprecations on the call graph of the collections code, if
nothing else, and that call graph includes a mixed bag of nuts. So,
what I'm really asking is this: when you all put deprecations on all
of Colt, what level of testing did you anticipate doing before
removing them?
>
> The down side of this is that you wind up with a pretty slow test. If the
> speed difference isn't large, then the test won't even be very reliable. I
> think that the better option is to test off-line to verify the improvement
> and just make a note in the javadocs with the results.
>
> On Wed, Dec 23, 2009 at 10:27 AM, Benson Margulies <bi...@gmail.com>wrote:
>
>> On Wed, Dec 23, 2009 at 1:24 PM, Benson Margulies <bi...@gmail.com>
>> wrote:
>> > '4' was lame humor. Thanks for the concrete suggestion, I'll go there.
>>
>> To be clearer about the lame joke: it's easy to test 'does it sort'.
>> It's hard to test, 'does it correctly get implement this particular
>> variation on quickSort which can be distinguished from others only by
>> speed.'
>>
>>
>>
>
Re: [math]: how to test sorts
Posted by Ted Dunning <te...@gmail.com>.
Speed is always hard to test with sort routines because average speed
depends on the distribution of the inputs. If your inputs are almost always
nearly in order, then bubble sort performs quite well. If all permutations
are equally likely, it definitely doesn't.
Most quick-sort variants improve speed for pathological cases. My feeling,
though, is that unit tests are more useful for testing correctness. I have
on occasion written "unit tests" for diagnostic purposes like speed tests.
These tests don't have assertions based on speed, but instead produce
diagnostic outputs.
If you want to test speed, then a pretty easy way is to pick permutations at
random, possibly emphasizing some kinds of permutations and run a sort for
those permutations using both algorithms. Measuring speeds and taking the
fastest iteration for each permutation should allow speed comparisons.
The down side of this is that you wind up with a pretty slow test. If the
speed difference isn't large, then the test won't even be very reliable. I
think that the better option is to test off-line to verify the improvement
and just make a note in the javadocs with the results.
On Wed, Dec 23, 2009 at 10:27 AM, Benson Margulies <bi...@gmail.com>wrote:
> On Wed, Dec 23, 2009 at 1:24 PM, Benson Margulies <bi...@gmail.com>
> wrote:
> > '4' was lame humor. Thanks for the concrete suggestion, I'll go there.
>
> To be clearer about the lame joke: it's easy to test 'does it sort'.
> It's hard to test, 'does it correctly get implement this particular
> variation on quickSort which can be distinguished from others only by
> speed.'
>
>
>
Re: [math]: how to test sorts
Posted by Jake Mannix <ja...@gmail.com>.
Ahhh... testing which impl is not critical. Testing stability, bounds,
worst case speed, as Sean suggested, is good.
-jake
On Dec 23, 2009 10:27 AM, "Benson Margulies" <bi...@gmail.com> wrote:
On Wed, Dec 23, 2009 at 1:24 PM, Benson Margulies <bi...@gmail.com>
wrote: > '4' was lame humo...
To be clearer about the lame joke: it's easy to test 'does it sort'.
It's hard to test, 'does it correctly get implement this particular
variation on quickSort which can be distinguished from others only by
speed.'
> > On Wed, Dec 23, 2009 at 1:03 PM, Jake Mannix <ja...@gmail.com>
wrote: >> Er... four is a...
Re: [math]: how to test sorts
Posted by Benson Margulies <bi...@gmail.com>.
On Wed, Dec 23, 2009 at 1:24 PM, Benson Margulies <bi...@gmail.com> wrote:
> '4' was lame humor. Thanks for the concrete suggestion, I'll go there.
To be clearer about the lame joke: it's easy to test 'does it sort'.
It's hard to test, 'does it correctly get implement this particular
variation on quickSort which can be distinguished from others only by
speed.'
>
> On Wed, Dec 23, 2009 at 1:03 PM, Jake Mannix <ja...@gmail.com> wrote:
>> Er... four is a very small number. Can you use a fixed random seed to
>> generate one
>> nice big permutation of 1...n, and sort it, and verify that 1...n comes out
>> in order?
>>
>> -jake
>>
>> On Wed, Dec 23, 2009 at 9:43 AM, Benson Margulies <bi...@gmail.com>wrote:
>>
>>> So, I'm staring at a file containing several copies of a very
>>> carefully implemented versions of quickSort and mergeSort.
>>>
>>> I'd like to remove the deprecation. I can feed it 4 things out of
>>> order and get them back sorted. Is that good enough?
>>>
>>
>
Re: [math]: how to test sorts
Posted by Benson Margulies <bi...@gmail.com>.
'4' was lame humor. Thanks for the concrete suggestion, I'll go there.
On Wed, Dec 23, 2009 at 1:03 PM, Jake Mannix <ja...@gmail.com> wrote:
> Er... four is a very small number. Can you use a fixed random seed to
> generate one
> nice big permutation of 1...n, and sort it, and verify that 1...n comes out
> in order?
>
> -jake
>
> On Wed, Dec 23, 2009 at 9:43 AM, Benson Margulies <bi...@gmail.com>wrote:
>
>> So, I'm staring at a file containing several copies of a very
>> carefully implemented versions of quickSort and mergeSort.
>>
>> I'd like to remove the deprecation. I can feed it 4 things out of
>> order and get them back sorted. Is that good enough?
>>
>
Re: [math]: how to test sorts
Posted by Sean Owen <sr...@gmail.com>.
I'd test sorting 0, 1, and n things. I would also try sorting n..1.
That's probably good.
On Wed, Dec 23, 2009 at 6:03 PM, Jake Mannix <ja...@gmail.com> wrote:
> Er... four is a very small number. Can you use a fixed random seed to
> generate one
> nice big permutation of 1...n, and sort it, and verify that 1...n comes out
> in order?
Re: [math]: how to test sorts
Posted by Jake Mannix <ja...@gmail.com>.
Er... four is a very small number. Can you use a fixed random seed to
generate one
nice big permutation of 1...n, and sort it, and verify that 1...n comes out
in order?
-jake
On Wed, Dec 23, 2009 at 9:43 AM, Benson Margulies <bi...@gmail.com>wrote:
> So, I'm staring at a file containing several copies of a very
> carefully implemented versions of quickSort and mergeSort.
>
> I'd like to remove the deprecation. I can feed it 4 things out of
> order and get them back sorted. Is that good enough?
>