hghwng
commented
8 years ago After tracing the execution very carefully, I found the cause of slow exploration.
For most modes, getWordsFromGraph() calls exploirerSubAuto() twice. The first call explores all possible states to find loops. The second call actually writes to the file.
The first call is the cause of slow exploration. How can we solve it?
- Use a faster loop detection algorithm. For simple graph, Tarjan's deep first search is efficient to detect strong connected components. But subcalls makes the states infinite effectively.
- Disable the loop check. If so, users won't be able to be informed about loops; other parts remain functional.
- Use random-based search. At first we can initialize some items to store results. For each item, choose next state by random. We build the items in parallel, when a given number of items reach final state, other items are discarded. In this way, items that are too computational-expensive are discarded automatically.
Pull request #7 disables the loop check. Merge with caution.
eric-laporte
Submitted by @eric-laporte
Fst2List lists the paths of a graph. When using it, the user can set a limit on the number of paths to be listed. But the computation takes the same time whatever the limit. The limit does not seem to prevent a complete exploration of the paths.
What steps will reproduce the problem?
In the experiment recorded in the attached log (Unitex3.1beta, revision 23 November 2015), I set the limit to 10 paths and apply Fst2List to a graph. The output is displayed after 6 s. Then, I set the limit to 100 000 paths and apply Fst2List to the same graph. The 100 000 paths are displayed after 6 s too.
What is the expected output?
In the case of a grammar with many paths or infinitely many paths, the limit on the number of paths could be a way of obtaining an incomplete list of paths without waiting for a hypothetical output. Would it be possible to stop the path exploration once the number of paths reaches the limit?
More info