Martin Jansche writes: > I'm attaching a patch for a modified implementation of > gsl_stats_minmax() that uses fewer comparisons than the current > version. The idea (which appears in the Cormen et al. textbook on > algorithms) is to unroll the main loop, considering two elements in > each iteration. Then only the smaller of the two needs to be compared > against the minimum, and the larger against the maximum. This saves > n/2 comparisons in total, compared with the current version.
Useful, I wasn't aware of that algorithm. > As an aside, it would be easy to modify this even further to deal with > NaNs by ignoring them. In the case of order statistics, it might make > sense to change the semantics so that max is an element from the input > array such that the array does not contain any element that is greater > than max. At the moment -- both in the current version and in this > patch -- the behavior is undefined if the array contains NaNs. Also, > it's not clear to me what should happen if n == 0. Thanks for pointing that out - It is important to handle NaNs. I decided to fix it by returning NaN (or the corresponding index) if the data contains NaN. I think that is in the IEEE spirit (that any operation involving a NaN gives a NaN result). Can you adjust your implementation to handle that? Take a look at the latest checked in version of minmax_source.c to see how I check for NaN. You might want to check whether it offers as much performance improvement then, because the isnan will add some overhead. -- Brian Gough Network Theory Ltd, Publishing Free Software Manuals --- http://www.network-theory.co.uk/ _______________________________________________ Bug-gsl mailing list [email protected] http://lists.gnu.org/mailman/listinfo/bug-gsl
