[SciPy-dev] Numerical Recipes (was tagging 0.7rc1 this weekend?)

Thouis (Ray) Jones thouis@broad.mit....
Tue Dec 16 14:41:43 CST 2008


On Tue, Dec 16, 2008 at 01:59, Jarrod Millman <millman@berkeley.edu> wrote:

> 2.  quickselect in scipy/signal/medianfilter.c
>
> Unresolved.

I looked at the NR code for select (2nd ed, page 342).  It was perhaps
a little too close for comfort, but someone else might disagree.

I rewrote the select algorithm(s) from scratch, referring to the
Wikipedia page describing quickselect, and tested it against the
existing functions on a large number of random cases (small and large
buffers, all the same values, etc.).  It is perhaps a little faster
than the current version.  It's also written as a single macro that
expands for the float/double/byte cases, rather than replicating the
code.

Someone should review this code, and if it looks good, I'll submit a
patch for medianfilter.c.

For 0.8, perhaps scipy should use a variant of constant time median
filtering (http://nomis80.org/ctmf.html)

Ray Jones
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: median_select_new.c
Url: http://projects.scipy.org/pipermail/scipy-dev/attachments/20081216/f2e6c68c/attachment.c 


More information about the Scipy-dev mailing list