[jira] [Commented] (NUMBERS-206) Selection API

["Alex Herbert (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/NUMBERS-206?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17851609#comment-17851609 ] 

Alex Herbert commented on NUMBERS-206:
--------------------------------------

I have created and tested many implementation for selection. Benchmarks were performed using JMH on input double array data of various lengths. Typically data was created using the Bentley and McIlroy (BM) test suite:
{noformat}
Bentley and McIlroy (1993)
Engineering a sort function.
Software, practice and experience, Vol.23(11), 1249–1265.
{noformat}
The data consists of various distributions of length n, using a seed of m. Each power of 2 in [1, 2n) is used for m.
||Distribution||Description||
|Sawtooth|Ascending data from 0 to m, that repeats|
|Random|Uniform random data in [0, m]|
|Stagger|Interlaced ascending sequences generated using (i * m + i) % n|
|Plateau|Ascending data from 0 to m, then constant at m|
|Shuffle|Two interlaced ascending sequences. The second sequence is chosen with probability 1 / m.|

Each distribution is modified using:
||Modification||Description||
|Copy|Copy the data|
|Reverse|Reverse [0, n)|
|Reverse front|Reverse [0, n/2)|
|Reverse back|Reverse [n/2, n)|
|Sort|Sort the data|
|Dither|Add i % 5 to element i|

As an addition to the BM test suite, the basic distributions are modified per iteration using an offset. This effectively rotates the sequence by [0, n).

Other distributions were also added to the test suite. These can be manually specified. However these additional distributions do not change the relative ranking of selection algorithms. The results shown will be total runtimes across the BM test suite data unless otherwise stated.

The data generation allows a range to be specified for n. For example lengths of {1023, 1023, 1025} will span a power of 2 and trigger generation of distributions with m at just below and just above n; this creates in total 966 input array sequences. Due to the use of m as powers of 2 up to 2n, larger lengths generate more data sequences. This prohibits use of the BM data for very large lengths unless subsets are used.

> Selection API
> -------------
>
>                 Key: NUMBERS-206
>                 URL: https://issues.apache.org/jira/browse/NUMBERS-206
>             Project: Commons Numbers
>          Issue Type: New Feature
>          Components: arrays
>            Reporter: Alex Herbert
>            Priority: Major
>
> Create a selection API to select the k-th largest element in an array. This places at k the same value that would be at k in a fully sorted array.
> {code:java}
> public final class Selection {
>     public static void select(double[] a, int k);
>     public static void select(double[] a, int from, int to, int k);
>     public static void select(double[] a, int[] k);
>     public static void select(double[] a, int from, int to, int[] k);
>     // Extend to other primitive data types that are not easily sorted (e.g. long, float, int)
> {code}
> Note: This API will support multiple points (int[] k) for use in quantile estimation of array data by interpolation of neighbouring values (see STATISTICS-85).



--
This message was sent by Atlassian Jira
(v8.20.10#820010)