function-alpha.html
  
function-cate.html
 score

OSILA

OSILA finds the k-th order statistic

expand all in page

Syntax

Description

OSILA is an algorithm for computing order statistics through an approach based on random sampling. For arrays of dimension bigger than 10^4, it allows to achieve the exact solution remarkably faster than the naive approach (i.e. sorting all the elements and take the k-th one).

example

out =OSILA(X, k) OSILA: standard application - alpha=0.99 (default value), n calculated.

example

out =OSILA(X, k, alpha) OSILA with alpha supplied and n calculated.

example

out =OSILA(X, k, alpha, n) OSILA with n (sample dimension) supplied and alpha empty (default value).

Examples

expand all

  • OSILA: standard application - alpha=0.99 (default value), n calculated.

    • N=10^7;
    Y=randn(N,1);
    k=34580;
    out=OSILA(Y,k);
    % Check the result
    sorY=sort(Y);
    disp([out,sorY(k)])
    disp(['Distance = ' num2str(abs(out-sorY(k)))])
             -2.70         -2.70

Distance = 0

  • OSILA with alpha supplied and n calculated.

    • N=10^7;
    Y=randn(N,1);
    k=34580;
    n=50;
    s1=tic;
    out1=OSILA(Y,k,0.01);
    t1=toc(s1);
    s2=tic;
    out2=OSILA(Y,k);
    t2=toc(s2);
    disp(['Execution time with n = 50: ' num2str(t1)])
    disp(['Execution time with n optimal: ' num2str(t2)])
    disp(['Execution time difference: ' num2str(t1-t2)])
    Execution time with n = 50: 0.014744
Execution time with n optimal: 0.014975
Execution time difference: -0.0002313

  • OSILA with n (sample dimension) supplied and alpha empty (default value).

    • N=10^7;
    Y=randn(N,1);
    k=34580;
    n=50;
    s1=tic;
    out1=OSILA(Y,k,[],n);
    t1=toc(s1);
    s2=tic;
    out2=OSILA(Y,k);
    t2=toc(s2);
    disp(['Execution time with n = 50: ' num2str(t1)])
    disp(['Execution time with n optimal: ' num2str(t2)])
    disp(['Execution time difference: ' num2str(t1-t2)])
    Execution time with n = 50: 0.019032
Execution time with n optimal: 0.018166
Execution time difference: 0.0008653

    Related Examples

    expand all

  • OSILA: Execution time difference with respect to the naive procedure.

    • N=10^7;
    Y=randn(N,1);
    k=34580;
    s1=tic;
    out=OSILA(Y,k);
    t1=toc(s1);
    s2=tic;
    sorY=sort(Y);
    out=sorY(k);
    t2=toc(s2);
    disp(['Execution time OSILA: ' num2str(t1)])
    disp(['Execution time naive: ' num2str(t2)])
    disp(['Execution time difference: ' num2str(t1-t2)])
    Execution time OSILA: 0.014972
Execution time naive: 0.17448
Execution time difference: -0.15951

    Input Arguments

    expand all

    X — a set of N numbers. Vector.

    Vector containing a set of N numbers.

    Data Type - double

    Data Types: single| double

    k — order statistic index. Scalar.

    An integer between 1 and N indicating the desired order statistic.

    Data Type - double

    Data Types: single| double

    Optional Arguments

    alpha — confidence level, it provides an upper value for the probability to have more than one iteration in the algorithm. If not provided (or empty), it is set to 0.99.

    Example: 0.99

    Data Types: double

    n — dimension of the random sample. If not provided (or n=0 or empty), it is calculated through the subfunction 'FindOptimalDimension' (see Section 3 of the reference).

    Example: 1000

    Data Types: double

    Output Arguments

    expand all

    out —k-th order statistic. Scalar

    Data Type - double

    References

    Cerasa, A. (2023). "Order statistics in large arrays (OSILA): a simple randomised algorithm for a fast and efficient attainment of the order statistics in very large arrays." Computational Statistics, p. 1-26.

    See Also

    This page has been automatically generated by our routine publishFS
    function-alpha.html
    		   score

    By Category

    		 Functions

    Alphabetical List 

    • The developers of the toolbox • The forward search group • Terms of Use • Acknowledgments