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)).
Description
Description:
Description
In$O(N)$ is currently used to find the largest transition index where the transition's minimum label is less than the
CompiledAutomaton.javawithin theaddTailmethod, a linear scanleadLabel: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)).