[Numpy-discussion] A faster median (Wirth's method)
Sturla Molden
sturla@molden...
Thu Sep 3 00:09:02 CDT 2009
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
More information about the NumPy-Discussion
mailing list