[
https://issues.apache.org/jira/browse/LUCENE-6361?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14364054#comment-14364054
]
Michael McCandless commented on LUCENE-6361:
--------------------------------------------
I'm not sure this is safe? It used to be O(1) to get the next state to work on
but with this patch it becomes O(N)? (N = number of states in the incoming
automaton), albeit with a tiny constant in front of the N since bitsets can
scan very quickly...
So then the loop becomes O(N^2) when it's O(N) now?
I realize the automata we see in this method are supposed to be very small
(graph expansions of one suggestion after analysis) but still...
> Optimized AnalyzinSuggester#topoSortStates()
> --------------------------------------------
>
> Key: LUCENE-6361
> URL: https://issues.apache.org/jira/browse/LUCENE-6361
> Project: Lucene - Core
> Issue Type: Improvement
> Components: core/other
> Affects Versions: 5.0
> Reporter: Markus Heiden
> Priority: Minor
> Attachments: topoSortStates.patch
>
>
> Optimized implementation of AnalyzinSuggester#topoSortStates().
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
