[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: FYI: nth_element
From: |
Shai Ayal |
Subject: |
Re: FYI: nth_element |
Date: |
Thu, 15 Oct 2009 09:56:50 +0200 |
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.
Shai
Re: FYI: nth_element, Jordi Gutiérrez Hermoso, 2009/10/17