**Update (2011-09-03):**I've added new functions to the release that edit the arrays in-place. This is not good Matlab style but gives significant speedups for the very performance conscious. It appears it may be useful for me to add a multithreaded version as well, so this may come in an upcoming release.C++ `std::nth_element` is a standard specification for an efficient rank selection algorithm. This algorithm can be used to solve a number of rank selection problems efficiently.

One example is median finding. A naive median finding algorithm, as implemented in MatLab (at least up to R2010a) is to sort the entire list of values and then just take the value in the middle position. But sorting the entire list is overkill; it is more efficient to do a sort of partial sort just to the point where the desired value is in the correct position. The version of this typically implemented in `nth_element` is known as quickselect or Hoare's Selection Algorithm. See Wikipedia: Selection algorithm for more details.

I find that a MatLab `fast_median` function based on `nth_element` runs about twice as fast as the native MatLab `median` function based on `sort`. Theoretically, the average complexity of quickselect is O(n), while the best performance complexity of the sort based method is O(n log n).

Finding median values is central to robust statistics, for example calculating the Median Absolute Deviation.

If you are interested, my MatLab wrapping of `nth_element` and an example implementation of `fast_median` are available at MatLab Central File Exchange.

## No comments:

## Post a Comment