bruno-roustant commented on a change in pull request #430:
URL: https://github.com/apache/lucene/pull/430#discussion_r748823600
##########
File path: lucene/core/src/java/org/apache/lucene/util/IntroSelector.java
##########
@@ -185,6 +204,115 @@ private void shuffle(int from, int to) {
}
}
+ /** Selects the k-th entry with a bottom-k algorithm, given that k is close
to {@code from}. */
Review comment:
Good remark, it means I miss more doc.
This algorithm is my own, and the idea is actually quite simple, maybe the
code is not clear enough.
When k is close to from, we take an int array of size (k - from + 1) called
bottom, and each bottom array element i points to the corresponding (from + i)
entry. And we determine the max of this bottom array. Then we loop on all the
remaining entries, for each entry e we compare it to the max of bottom, if e <
max then e evicts max and takes its slot in bottom, and we determine the new
max of bottom. (the speed comes from the fact that most of the time we only
compare e to bottom-max)
At the end, all slots in bottom point to the k least entries, we just have
to swap them and finally swap the bottom max at index k.
I'll add more doc!
--
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.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
