4 ms·

The grep one is tricky. If no characters match, it's fast. But if some match, and if it is ignoring case, it's much slower. It's actually faster to read the w

• rspeer 11y ago
  Is this still the case if you set LANG=C on the command, so that you're lowercasing ASCII bytes instead of Unicode?
  • lqdc13 11y ago
    Edit: There was a bug. No it's actually slower when the locale is set to C. I have 4434 files with about 100 words of text in them. here is python func that searches utf8: def find_sp(paths): for path in paths: with open(path,'rb') as f: if b"snow" in f.read().lower(): yield True else: yield False %timeit [o for o in find_sp(glob.glob('./*'))] 10 loops, best of 3: 35.2 ms per loop Here is the bash one: $>echo $LANG C $>time grep -Riq "snow" . real 0m0.015s user 0m0.005s sys 0m0.010s However, if you have a lot of files and you are doing the searching for them in a not very smart way, it takes a lot longer. time for f in ./*txt; do grep -iq "snow" $f;done real 0m2.307s user 0m0.337s sys 0m2.113s
    • jbnicolai 11y ago
      In the python example you're running a function, while in the grep example you're launching a program (grep) from your shell. To make the comparison more fair you'd store the python program and time starting and running both from a shell.
• wruza 11y ago
  Grep is not that naive, afaik. https://news.ycombinator.com/item?id=2393587 https://news.ycombinator.com/item?id=2393587
  • agumonkey 11y ago
    Deceptively simple old tools are often full of gems.
• mehrdada 11y ago
  Assuming your pattern is static, it shouldn't be much slower. String matching can be done in linear time with some preprocessing: check out Knuth-Morris-Pratt and Boyer-Moore algorithms. Basically, the idea is that you build a deterministic finite state automaton and try feeding the string through it. Each character would cause exactly one automaton transition. Therefore, you can do the whole thing in O(n) after you pay the cost of preprocessing to build the automaton, with a quite tiny constant for small patterns.
  • weinzierl 11y ago
    Actually Boyer-Moore (somewhat counter intuitively) is faster for longer search strings than for short ones. It makes sense if you think about a search string that has the same length as the searched string. If they don't match you can find that out with a single character comparison.
  • lqdc13 11y ago
    It's much slower because you are checking the first character in all zeros string, but checking multiple characters in the case that the first ones match using Boyer-Moore.