[
https://issues.apache.org/jira/browse/LUCENE-8796?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16835629#comment-16835629
]
Atri Sharma commented on LUCENE-8796:
-------------------------------------
bq. We could potentially reduce the number of comparisons (at average) using
the property that binary search uses same number of comparisons to search for a
value in 2^n and 2^n+1 -1. Could we adjust the lower bound of search space
based on that?
Something like:
{code:java}
int lowerBound = 0;
while(bound < length && docs[bound] < target) {
lowerBound += bound;
bound = std::min((bound + 1) * 2 - 1, length);
}
i = Arrays.binarySearch(docs, lowerBound, (lowerBound +
Math.min(bound, length)), target);
{code}
This might be wrong (I have not run a bunch of tests), but gives the general
idea.
> Use exponential search in IntArrayDocIdSet advance method
> ---------------------------------------------------------
>
> Key: LUCENE-8796
> URL: https://issues.apache.org/jira/browse/LUCENE-8796
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Luca Cavanna
> Priority: Minor
>
> Chatting with [~jpountz] , he suggested to improve IntArrayDocIdSet by making
> its advance method use exponential search instead of binary search. This
> should help performance of queries including conjunctions: given that
> ConjunctionDISI uses leap frog, it advances through doc ids in small steps,
> hence exponential search should be faster when advancing on average compared
> to binary search.
>
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
