6 ms·
Try running the search many times. The lazy DFA should get faster. The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is w
by burntsushi 4y ago
Try running the search many times. The lazy DFA should get faster.
The lazy DFA is technically O(m*n) just like the NFA. The "lazy" part of the "lazy DFA" is why. Because it builds itself during the search. A real DFA would be truly O(n) because it would be fully built before starting a search.
- eesmith 4y agoI get 141.5 seconds for the first time, (laptop in suspend mode during the second), 84.8 seconds for the third, 67.9 seconds for the fourth, and re2/re2.cc:821: DFA out of memory: pattern length 2493008, program size 1323834, list count 1089251, bytemap range 54 is concatenation? True time: 102.0 seconds for the fifth. It would appear to not be caching, or at least not in a way that makes this timing faster than the NFA. In any case, my point is that we know this problem can be solved in O(n) time.
- burntsushi 4y agoYeah, you would need to give more memory to the lazy DFA. And yeah sorry, I was only commenting narrowly on RE2 based on my knowledge of its internals.