[
https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007511#comment-13007511
]
Robert Muir commented on LUCENE-2970:
-------------------------------------
bq. A DFA then has a cycle if every you recurse and find a gray node
well it seems it might work for an NFA too? Though i'm not sure how "great" of
NFAs AutomatonTestUtil.randomAutomaton generates?
if all else fails we can det as a side effect (this won't hurt lucene), but I'd
like to know for sure, and to send the patch upstream.
{quote}
Maybe rename the test-only isFiniteSimple to isFiniteSLOW or something?
Does the new random test case tend not to hit the super-slow cases...?
{quote}
The test definitely got faster, but maybe the type of DFAs i generate are not
represented fairly by the random generator? In other words they are
"worst-case" for the old method, but they are "reasonable" as far as queries,
finite and contained as far as the number of terms they accept.
> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain
> situations
> -----------------------------------------------------------------------------------
>
> Key: LUCENE-2970
> URL: https://issues.apache.org/jira/browse/LUCENE-2970
> Project: Lucene - Java
> Issue Type: Bug
> Affects Versions: 4.0
> Reporter: Robert Muir
> Assignee: Robert Muir
> Fix For: 4.0
>
> Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with
> finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in
> SpecialOperations.isFinite <-- this is used to determine if the DFA is
> acyclic or not.
> (in this case I am talking about even up to minutes of cpu).
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
