3 ms·

I doubt whatever you're doing is going to work in Rust or Go. Say that the length of your string is n, and the length of your regular expression is m. Isn't Re

I doubt whatever you're doing is going to work in Rust or Go. Say that the length of your string is n, and the length of your regular expression is m. Isn't Regular Expression matching in those languages guaranteed O(m n) time? In plain English, that's only linear time - which you practically can't improve on - even if you tried! It can only do worse if your implementation uses backtracking instead of Finite Automata - which was very common at one time, but is now considered The Wrong Way: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html There is actually a way to optimise your queries, which is by precompiling them to DFAs, but I don't think that's what you're doing.

lucideer 4y ago
I stand completely corrected. This is cool. > There is actually a way to optimise your queries, which is by precompiling them to DFAs, but I don't think that's what you're doing. You can do that, but the primary advantage of DFAs in practice is backtracking avoidance, so simply reduction of backtracking in manually constructed queries is more what I was referring to. The missing part of the puzzle here being that not supporting backtracking at all doesn't limit capabilities, so removal rather than reduction is the go/rust approach.