Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

Is it faster to look for long or short search terms? Or does it affect speed at all? In other words, should you make search terms as exact as possible?

There are more than 100 000 files and each file contains between 20 and more than 5000 rows of data. Usually the grep is used to find just one instance of the search term.

Let's say the search term is "SEARCHTERM", and it will be in a row like this:

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

Is it faster to look for "SEARCH" or "SEARCHTERM"? Let's say that in this case we don't care if we also find matches in other unrelated lines.

This is how I currently do it:
grep NAD+DP 123* | grep SEARCHTERM

But I find it quite slow, still. It usually takes around 3-5 minutes to find the data, even when I know the rough filename, which limits the range to around 10 000 files.

So, would a longer or shorter search term help? As far as I know, grep looks for "blocks" of words of a certain length?

share|improve this question

4 Answers 4

up vote 2 down vote accepted

Some reference material:

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.

from Why GNU grep is fast.

The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). [...] In general, the algorithm runs faster as the pattern length increases.

from Boyer–Moore string search algorithm.

Conclusion: Use longer strings.

Now, a bit of benchmark for fun:

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v` # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

Results: 0.952s is the average for the short string, 0.244s is the average for the long string.

NB: The length is not the only criterion to be taken into account.

share|improve this answer
    
Thanks for my friend who talked to me about this question –  Josay May 31 '13 at 22:27

You can try yourself using SEARCH or SEARCHTERM. Also try changing the order of the two grep commands. Anyway the only useful option will be most probably to use several CPU cores for one search. See the parallel command.

share|improve this answer

I don't think specifying more specific search term will make it noticeably faster.

With so many files to search, you need to somehow index your data to make search faster.

I can suggest few ways:

  • Create database (PostgreSQL or MySQL), import your data into database - one file in one row, add FTS (full text search) index. Create some utility to query database.

  • Import data into database in more granular way, probably one line into one row (or maybe more than one table), create indexes such that your data is searchable by using index(es). Create some utility to query database.

  • Add your files into git repository, compact it using git gc, use git grep to search. In my experience, git grep can be faster than standard grep by factor of 10x-100x.

share|improve this answer

Logically, a shorter term will require less CPU time, as grep will be doing

if (filechar[i] == pattern[i]) ...

fewer times.  In reality, I would guess that a grep would be I/O-bound and not CPU-bound, so it won’t matter.

share|improve this answer
    
Surprisingly enough, this is wrong as grep is using a really smart algorithm, please refer to my answer. –  Josay May 31 '13 at 22:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.