search

sebfisch / haskell-regexp

Regular Expression Matching in Haskell
http://sebfisch.github.com/haskell-regexp/
Other
34 stars 5 forks source link

single traversal #18

Closed sebfisch closed 14 years ago

sebfisch commented 14 years ago

Currently, the combination of the functions next and acivateFirst leads to quadratic run-time for certain regular expressions. For example, in a****** activateFirst is called on every sub-expression and traverses each anew. Also, if all symbols in a?a?a?a?a? are activated, then step is called recursively on every sub-expression and calls activateFirst each time on the right child.

Write a single function that traverses an expression only once.

sebfisch commented 14 years ago

This may prevent the later use of parallelism because one probably needs to do a left-to-right walkthrough.

sebfisch commented 14 years ago

Implemented in simple version: 6c889ab753643d9813454dc490ea6c33eab18b82.

The implementation does not thread things through the tree and, hence, does not prevent later parallelisation. The evilRegExp example runs an order of magnitude faster (half a second for n=1000). Correctness not yet tested for other examples.

sebfisch commented 14 years ago

implemented together with the generalisation to semirings.