3 ms·
If you don't have the entire string in memory then Boyer-Moore is usually fastest because you can avoid doing a lot of I/O (since you skip comparing many subseq
by techdebt5112 12y ago
If you don't have the entire string in memory then Boyer-Moore is usually fastest because you can avoid doing a lot of I/O (since you skip comparing many subsequences, you don't have to read those subsequences in the first place). This is why grep is very fast given a static string pattern to search for, even on huge files, but grepping for a regex is dog slow.
- sitkack 12y agoUntil they implement a JIT and compile the regex.
- techdebt5112 12y agoNo, you're missing the point -- using a regex does not allow you to read in less than all of the input (in the best case, even). If you grep a 1GB file with a regex you must read 1GB from disk, no exceptions, and that's many orders of magnitude slower than anything on the CPU (or in memory). With Boyer-Moore you can do less than 100% of the file size in I/O, especially if the given pattern is long relative to the full text.
- sitkack 12y agoWe have no context to the environment that those regexs are running. For all we know they could have implicit limits and be getting compiled down to FPGAs. I can guarantee you that those regexs aren't running unbounded. No point was missed.