News for hackers. Stuff that matters.
Re:Node.js in Flame Graphs by ufo on Wednesday November 19, 2014 @02:07PM (#8631944)
The exponential blowup only occurs in the worst case. I don't have a proof at hand but I suspect that the final automaton shouldn't grow very large if your regexes are modeling web routes, since they are structured as a tree of paths with lots of "prefix-sharing" and no loops.

Other than that, if you are concerned about automaton size you can use a non-deterministc automaton instead of a deterministic one. You spend a bit more time (at each iteration you have to update a list of "active" states, while in the DFA case there is always a single active state) but on the other hand the automaton itself is much more compact.

There are no comments on this comment yet.