rajat315315 opened a new issue, #16360:
URL: https://github.com/apache/lucene/issues/16360
### 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`:
```java
// 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)`).
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
