[
https://issues.apache.org/jira/browse/NUMBERS-206?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17852711#comment-17852711
]
Alex Herbert edited comment on NUMBERS-206 at 6/6/24 11:10 AM:
---------------------------------------------------------------
h2. Saturated Indices
Using the same data as previously (n=50000, BM distribution)
|| ||500||1000||5000||10000||50000||Total||
|ISP|7107387233|7757771325|8899903475|9925539708|10609585958|33690601741|
|SELECT|6308182425|7045016725|8423035575|8798568667|9504493042|30574803392|
|IDP|6023154508|6650004933|8043503983|8634537741|9257381325|29351201166|
Average separation is 100, 50, 10, 5, 1 respectively. The SortJDK method took
an average of 6338586897 on 6 runs (see previous results). This result shows
that the selection is a similar speed to a sort when the number of keys is
500-1000. This many indices is a reasonable upper limit for the use in a QQ
plot of quantiles.
Some of the BM distributions are easy to sort with a merge sort due to
ascending/descending runs. The data can be made more difficult by changing the
benchmark to use uniformly distributed random data. The following shows the
result of n=50000 with 400 samples and 10 repeats of the random indices:
||Method||500||1000||5000||10000||Total||
|ISP|4205753375|4660640933|5587189925|5920384433|20373968667|
|SortJDK|4665368408|4690999142|4729445525|4685222425|18771035500|
|SELECT|3729310475|4143622242|4966502342|5275207142|18114642200|
|IDP|3725283483|4105095059|4974550508|5218439467|18023368517|
This result shows selection is a similar speed to a sort when the average
separation approaches 10 (k=5000).
Note that the selection routine is not optimised for sorting. There are changes
that could be made to increase performance on saturated indices but these would
compromise performance for sparse indices. The current settings ensure that the
performance is never catastrophically bad when the number of indices saturates
the range.
was (Author: alexherbert):
h2. Saturated Indices
Using the same data as previously (n=50000, BM distribution)
||Method||500||1000||5000||10000||Total||
|ISP|7107387233|7757771325|8899903475|9925539708|33690601741|
|SELECT|6308182425|7045016725|8423035575|8798568667|30574803392|
|IDP|6023154508|6650004933|8043503983|8634537741|29351201166|
Average separation is 100, 50, 10, 5 respectively. The SortJDK method took an
average of 6338586897 on 6 runs (see previous results). This result shows that
the selection is a similar speed to a sort when the number of keys is 500-1000.
This many indices is a reasonable upper limit for the use in a QQ plot of
quantiles.
Some of the BM distributions are easy to sort with a merge sort due to
ascending/descending runs. The data can be made more difficult by changing the
benchmark to use uniformly distributed random data. The following shows the
result of n=50000 with 400 samples and 10 repeats of the random indices:
||Method||500||1000||5000||10000||Total||
|ISP|4205753375|4660640933|5587189925|5920384433|20373968667|
|SortJDK|4665368408|4690999142|4729445525|4685222425|18771035500|
|SELECT|3729310475|4143622242|4966502342|5275207142|18114642200|
|IDP|3725283483|4105095059|4974550508|5218439467|18023368517|
This result shows selection is a similar speed to a sort when the average
separation approaches 10 (k=5000).
Note that the selection routine is not optimised for sorting. There are changes
that could be made to increase performance on saturated indices but these would
compromise performance for sparse indices. The current settings ensure that the
performance is never catastrophically bad when the number of indices saturates
the range.
> 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)
