Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Date: Wed, 16 Mar 2011 15:33:29 +0000 (UTC)
From: "Robert Muir (JIRA)" <jira@apache.org>
To: dev@lucene.apache.org
Message-ID: 
 <308176620.6663.1300289609538.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <905464115.6403.1300280669671.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have
 TERRIBLE TERRIBLE runtime in certain situations
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ 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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org