[
https://issues.apache.org/jira/browse/LUCENE-9125?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17012926#comment-17012926
]
Bruno Roustant commented on LUCENE-9125:
----------------------------------------
I benchmarked using non-trivial automata for automaton/fuzzy queries.
Making Automaton.step() use binary search reduces step() call time by -20% (and
obviously it becomes O(log(n))).
By introducing Automaton.next() to iterate & lookup more efficiently through a
state transitions, I measured -40% binary search loop executions. This is a net
gain with same functional logic, because each time we increase the lower bound
for the binary search instead of always starting from the first transition.
This will result in faster AutomatonQuery and FuzzyQuery construction.
> Improve Automaton.step() with binary search and introduce Automaton.next()
> --------------------------------------------------------------------------
>
> Key: LUCENE-9125
> URL: https://issues.apache.org/jira/browse/LUCENE-9125
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Bruno Roustant
> Priority: Major
> Time Spent: 10m
> Remaining Estimate: 0h
>
> Implement the existing todo in Automaton.step() (lookup a transition from a
> source state depending on a given label) to use binary search since the
> transitions are sorted.
> Introduce new method Automaton.next() to optimize iteration & lookup over all
> the transitions of a state. This will be used in RunAutomaton constructor and
> in MinimizationOperations.minimize().
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
