Re: FYI: nth_element

[Jaroslav Hajek]

On Thu, Oct 15, 2009 at 9:56 AM, Shai Ayal <address@hidden> wrote:
> On Thu, Oct 15, 2009 at 9:15 AM, Jaroslav Hajek <address@hidden> wrote:
>> hi all,
>>
>> Octave has just got a new function: nth_element:
>> http://hg.savannah.gnu.org/hgweb/octave/rev/aea3a3a950e1
>>
>> the docstring:
>>
>>  -- Built-in Function:  nth_element (X, N)
>>  -- Built-in Function:  nth_element (X, N, DIM)
>>     Select the n-th smallest element of a vector, using the ordering
>>     defined by `sort'.  In other words, the result is equivalent to
>>     `sort(X)(N)'.  N can also be a contiguous range, either ascending
>>     `l:u' or descending `u:-1:l', in which case a range of elements is
>>     returned.  If X is an array, `nth_element' operates along the
>>     dimension defined by DIM, or the first non-singleton dimension if
>>     DIM is not given.
>>
>>     nth_element encapsulates the C++ STL algorithms nth_element and
>>     partial_sort.  On average, the complexity of the operation is
>>     O(M*log(K)), where `M = size(X, DIM)' and `K = length (N)'.  This
>>     function is intended for cases where the ratio K/M is small;
>>     otherwise, it may be better to use `sort'.
>>
>>     See also: sort, min, max
>>
>> In short, it allows extracting a small portion of sort(X) without
>> actually doing the full sort.
>> This is sometimes useful for statistics when computing quantiles and
>> the like... statisticians can surely tell better.
>>
>> Maybe it can be used to boost some existing functions. As an example,
>> it can be readily used to speed up the "median" function:
>> http://hg.savannah.gnu.org/hgweb/octave/rev/b7b89061bd0e
>>
> It can also help hist quite a lot.
>

I don't see how. Can you clarify?


-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz