maybe this is included and i missed it, but it's asymptotically faster to maintain a sorted tree of values plus a list of pointers to nodes in order added. if you store "number of values to right" in each tree node then finding the next median (moving the window one position) is O(log w) and total cost for whole array is O(n log w) iirc.
this is used to median filter images in the IRAF package. i don't know if the approach is published anywhere (it's pretty obvious once the idea of keeping points within the window in a sorted tree "clicks"), but frank valdes did test it against other approaches.
the main drawbacks are that the overhead/constant is pretty high, so you need fairly large datasets (more exactly, large windows) for it to be a win, and implementation in old fortran is a pain...
Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
Comments
maybe this is included and i missed it, but it's asymptotically faster to maintain a sorted tree of values plus a list of pointers to nodes in order added. if you store "number of values to right" in each tree node then finding the next median (moving the window one position) is O(log w) and total cost for whole array is O(n log w) iirc.
this is used to median filter images in the IRAF package. i don't know if the approach is published anywhere (it's pretty obvious once the idea of keeping points within the window in a sorted tree "clicks"), but frank valdes did test it against other approaches.
the main drawbacks are that the overhead/constant is pretty high, so you need fairly large datasets (more exactly, large windows) for it to be a win, and implementation in old fortran is a pain...
If the window is the length of the data, that becomes O(n log n) -- essentially no better than a sort?
For images and other kernel-based filtering, there is a O(1) median algorithm available: http://nomis80.org/ctmf.html
Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
maybe i have misunderstood the application - i am talking about "median smoothing" with a "running window". w is typically fixed.
but thanks for link to paper - that is new to me.
Look at jallmanns comment [0]. Quickselect partially sorts the input array. If you reuse that array it will be faster on repeated runs.
[0] https://news.ycombinator.com/item?id=5728220
even w ordered data, sorting is O(n) isn't it?
Ordered data? Lookups into sorted data can use a binary search and are only O(log n).
but you need to move n/2 to "make room" - think of the whole process.
edit: you're not wrong, but what i am saying is that to make the filter practical you have to save the new point, too.
sorry for brief comments. on vacn w tablet only.