Re:Go 1.1beta1 now on the benchmarks game
by Bakkot on Wednesday April 17, 2013 @12:52PM
(#5565498)
Why not use the potentially exponential algorithm initially and timeout and fall back to the linear case if the sometimes-quick one has taken longer than the linear one would have? At most a 2x slowdown for complex cases, and substantial speedup for the simple ones.
[ Parent
| on HN ]
Re:Go 1.1beta1 now on the benchmarks game
by danieldk on Wednesday April 17, 2013 @01:12PM
(#5565641)
It depends, if you have the opportunity to build a DFA once, why not do it? It's only a one-time cost.
I think the more serious problem is that what most people consider to be a 'regular expression' does not express a regular language, and hence cannot be expressed as a finite state automaton.