3 ms·
> Constructing the minimal DFA for a given NFA is PSPACE-hard. This isn't really a problem if you incur that cost only once by having the regex compiled when t
by zamalek 11y ago
> Constructing the minimal DFA for a given NFA is PSPACE-hard.
This isn't really a problem if you incur that cost only once by having the regex compiled when the script is parsed. However, idiomatic JS usually includes regex literals in the closure where it is used - decreasing performance, code reuse and clarity. Why? Probably for the same reasons that regex is being used in the first place.
- lorenzhs 11y agoWell, PSPACE-hard is pretty damn hard, so this really depends on the size and complexity of your NFA ;) Of course most of the time you don't hit the pathological cases like the one I described above. My comment was not meant to provide a guideline on how to fix this, consider it a fun observation on automata theory.
- zamalek 11y agoIndeed. What I failed to communicate was that there is no reason to incur that cost multiple times per process/application. For some reason idiomatic JS encourages incurring that cost multiple times. Your comment shows that this idiomatic form is even more absurd than I originally thought.