search

apache / lucene

Apache Lucene open-source search software
https://lucene.apache.org/
Apache License 2.0
2.6k stars 1.01k forks source link

Optimize IntroSelector for worst case [LUCENE-9024] #10067

Closed asfimport closed 4 years ago

asfimport commented 4 years ago

There is a TODO in IntroSelector.java to use the median of medians algorithm instead of HeapSort for the worst case, as median of medians offers a better time complexity.

I've discussed this with @jpountz and he has agreed to review my work on this.

Migrated from LUCENE-9024 by Paul Sanwald (@pcsanwald), resolved Oct 29 2019

asfimport commented 4 years ago

ASF subversion and git services (migrated from JIRA)

Commit d53e877152851a3dc91c7c56f01544a43ffe7397 in lucene-solr's branch refs/heads/master from Paul Sanwald https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=d53e877

LUCENE-9024: Optimize IntroSelector to use median of medians (#966)

asfimport commented 4 years ago

ASF subversion and git services (migrated from JIRA)

Commit 7d0dbdaf62299389876a01621430b3ede572ed80 in lucene-solr's branch refs/heads/branch_8x from Paul Sanwald https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=7d0dbda

LUCENE-9024: Optimize IntroSelector to use median of medians (#966)

asfimport commented 4 years ago

Adrien Grand (@jpountz) (migrated from JIRA)

Thanks @pcsanwald!

asfimport commented 4 years ago

ASF subversion and git services (migrated from JIRA)

Commit f23d5c122aa35ade7e738908319955684f0f4bba in lucene-solr's branch refs/heads/master from Adrien Grand https://gitbox.apache.org/repos/asf?p=lucene-solr.git;h=f23d5c1

LUCENE-9024: CHANGES entry.

asfimport commented 4 years ago

Adrien Grand (@jpountz) (migrated from JIRA)

Closing after the 8.4.0 release.