Optimize transition lookup in CompiledAutomaton.addTail using binary search
Nobody has claimed this yet.
Assessment
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Newbie friendliness
- 78/100
Research direction
Start in CompiledAutomaton.java at the addTail method and inspect how automaton.getTransition(state, index, transition) provides random access. Replace the sorted-transition scan with a binary search for the largest minimum label below leadLabel, preserving the existing maxIndex behavior. Done means the lookup is logarithmic while selecting the same transition boundary.
Written by the indexing model from the issue text.
Description
Description
Description:
Description
In CompiledAutomaton.java within the addTail method, a linear scan $O(N)$ is currently used to find the largest transition index where the transition's minimum label is less than the leadLabel:
// Find biggest transition that's < label
// TODO: use binary search here
int maxIndex = -1;
int numTransitions = automaton.initTransition(state, transition);
for (int i = 0; i < numTransitions; i++) {
automaton.getNextTransition(transition);
if (transition.min < leadLabel) {
maxIndex = i;
} else {
// Transitions are always sorted
break;
}
}
Since the automaton transitions are always sorted by minimum label first, we can optimize this transition lookup to run in $O(\log N)$ time by implementing a binary search using random access (automaton.getTransition(state, index, transition)).
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 4h
- Merged PRs (30d)
- 79
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from apache/lucene
-
type:bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
-
type:bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
-
type:task
Difficulty 1/5 Under an hour Newbie friendliness 76/100
-
type:enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
type:enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
infinispan/infinispan#18150 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
untriaged
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
opensearch-project/k-NN#3597 ·
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 82/100