[GitHub] [lucene-solr] pcsanwald opened a new pull request #966: LUCENE-9024 Optimize IntroSelector to use median of medians

[GitBox <gi...@apache.org>]

pcsanwald opened a new pull request #966: LUCENE-9024 Optimize IntroSelector to use median of medians
URL: https://github.com/apache/lucene-solr/pull/966
 
 
   # Description
   
   Today, `IntroSelector.slowSelect` falls back to a heap sort; This PR moves that implementation to use a median of medians approach, suggested by a TODO in the code.
    
   # Solution
   
   Implemented a median of medians algorithm.
   
   # Tests
   
   I didn't add any new tests for this as I believe the current test cases, `TestIntroSelector`, should cover the basic functionality. However, one thing I'd like input on: Today, `select(int from, int to, int k)`, the `to` parameter is _exclusive_. Since it's also a specified parameter in the test, the test never checks the case where the full array should be used. `doTestSelect` has a call to `Arrays.sort(expected, from, to);`, but `to` will never be the last index in the array because the size of the array is allocated to `from + to + random().nextInt(5)`, so the actual size of the array will be a minimum of `from + to`.
   
   I'd be happy to address this problem in this PR, or in a subsequent PR if that's preferred. 
   
   # Checklist
   
   Please review the following and check all that apply:
   
   - [ ] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/solr/HowToContribute) and my code conforms to the standards described there to the best of my ability.
   - [ ] I have created a Jira issue and added the issue ID to my pull request title.
   - [ ] I am authorized to contribute this code to the ASF and have removed any code I do not have a license to distribute.
   - [ ] I have given Solr maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
   - [ ] I have developed this patch against the `master` branch.
   - [ ] I have run `ant precommit` and the appropriate test suite.
   - [ ] I have added tests for my changes.
   - [ ] I have added documentation for the [Ref Guide](https://github.com/apache/lucene-solr/tree/master/solr/solr-ref-guide) (for Solr changes only).
   

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org