[Numpy-discussion] A faster median (Wirth's method)

[Sturla Molden]

Chad Netzer skrev:
> By the way, as far as I can tell, the above algorithm is exactly the
> same idea as a non-recursive Hoare (ie. quicksort) selection:  Do the
> partition, then only proceed to the sub-partition that must contain
> the nth element.    My version is a bit more general, allowing
> partitioning on a range of elements rather than just one, but the
> concept is the same.  The numpy quicksort already does non recursive
> sorting.
>
> I'd also like to, if possible, have a specialized 2D version, since
> image media filtering is one of my interests, and the C version works
> on 1D (raveled) arrays only.
I agree. NumPy (or SciPy) could have a select module similar to the sort 
module. If the select function takes an axis argument similar to the 
sort functions, only a small change to the current np.median would needed.

Take a look at this:

http://projects.scipy.org/numpy/attachment/ticket/1213/_selectmodule.pyx

Here is a select function that takes an axis argument. There are 
specialized versions for 1D, 2D, and 3D. Input can be contiguous or not. 
For 4D and above, axes are found by recursion on the shape array. Thus 
it should be fast regardless of dimensions.

I haven't tested the Cython code /thoroughly/, but at least it does compile.


Sturla Molden