lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless (JIRA)" <>
Subject [jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
Date Wed, 16 Mar 2011 14:37:29 GMT


Michael McCandless commented on LUCENE-2970:

Patch looks correct to me!

The algo you impl'd is the same one described in Cormen, Leiserson, Rivest Algorithms book,
as a side effect of doing a depth-first walk through the DFA.  Their description of DFS colors
the nodes -- white is unvisited, black is visited, gray is "being visited" (ie on my current
path).  A DFA then has a cycle if every you recurse and find a gray node.

In your patch, the combination of "path" and "visited" maps to these colors, and you detect
a cycle when path is set and visited is not.

Maybe rename the test-only isFiniteSimple to isFiniteSLOW or something?

Does the new random test case tend not to hit the super-slow cases...?

> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>                 Key: LUCENE-2970
>                 URL:
>             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:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message