undefined | Better HN

0 pointsburntsushi3y ago0 comments

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.

0 comments

2 comments · 1 top-level

eesmith3y ago· 1 in thread

I 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.

burntsushiOP3y ago

Yeah, 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.

j / k navigate · click thread line to collapse