Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I have a file that's growing about 200,000 lines a day, and it is all formed with blocks of three lines as such:

1358726575123       # key
    Joseph Brunner  # name
    carpenter       # job
9973834728345
    Andres Smith
    student
7836472098652
    Mariah Anthony
    dentist

Now, I have another file from which I extract about 10,000 key patterns, such as 1358726575123. Then I run a for loop with these patterns and have to check them against the first file. If the file doesn't contain such pattern, I save the pattern in a third file for further processing:

for number in $(grep -o '[0-9]\{12\}' file2); do  # finds about 10.000 keys
     if ! grep -q ^$number$ file1; then           # file1 is a huge file
         printf "$number\n" >>file3               # we'll process file3 later
     fi
done

The example code greps a huge file 10,000 times, and I run this loop about once a minute, during the whole day.

Since the huge file keeps growing, what can I do to make all this faster and save some CPU? I wonder whether sorting the file somehow by its key (if so, how?) or using a db instead of plain text would help...

share|improve this question

11 Answers 11

up vote 8 down vote accepted

This answer is based on the awk answer posted by potong..
It is twice as fast as the comm method (on my system), for the same 6 million lines in main-file and 10 thousand keys... (now updated to use FNR,NR)

Although awk is faster than your current system, and will give you and your computer(s) some breathing space, be aware that when data processing is as intense as you've described, you will get best overall results by switching to a dedicated database; eg. SQlite, MySQL...


awk '{ if (/^[^0-9]/) { next }              # Skip lines which do not hold key values
       if (FNR==NR) { main[$0]=1 }          # Process keys from file "mainfile"
       else if (main[$0]==0) { keys[$0]=1 } # Process keys from file "keys"
     } END { for(key in keys) print key }' \
       "mainfile" "keys" >"keys.not-in-main"

# For 6 million lines in "mainfile" and 10 thousand keys in "keys"

# The awk  method
# time:
#   real    0m14.495s
#   user    0m14.457s
#   sys     0m0.044s

# The comm  method
# time:
#   real    0m27.976s
#   user    0m28.046s
#   sys     0m0.104s

share|improve this answer
    
This is fast, but I don't understand much of awk: what the file names should look like? I tried file1 -> mainfile and file2 -> keys with gawk and mawk, and it outputs wrong keys. –  Teresa e Junior Jan 22 '12 at 6:39
    
file1 has keys, names and jobs. –  Teresa e Junior Jan 22 '12 at 6:41
    
'mainfile' is the big file (with keys, names and jobs). I've just called it "mainfile' because I kept getting mixed up which file was which (file1 vs file2).. 'keys' contains only the 10 thousand, or however many, keys.. For your situaton do NOT redirect anyting ... just use file1 EOF file2 They are the names of your files.. "EOF" is a 1-line file creadte by the script to indicate the end of the first file (main data file) and the start of teh second file (keys). awk allow you to read in a series of files.. In this case that series has 3 files in it. The output goes to stdout –  Peter.O Jan 22 '12 at 7:40
    
This script will print any keys which are present in mainfile, AND it will also print any keys from the keys file which are NOT in mainfile... That's probably what is happening... (I'll look a bit further into it... –  Peter.O Jan 22 '12 at 8:01
    
Thank you, @Peter.O! Since the files are confidential, I'm trying to create sample files with $RANDOM for uploading. –  Teresa e Junior Jan 22 '12 at 8:38

The problem, of course, is that you run grep on the big file 10,000 times. You should read both files only once. If you want to stay outside scripting languages, you can do it this way:

  1. Extract all numbers from file 1 and sort them
  2. Extract all numbers from file 2 and sort them
  3. Run comm on the sorted lists to get what's only on the second list

Something like this:

$ grep -o '^[0-9]\{12\}$' file1 | sort -u -o file1.sorted
$ grep -o  '[0-9]\{12\}'  file2 | sort -u -o file2.sorted
$ comm -13 file1.sorted file2.sorted > file3

See man comm.

If you could truncate the big file every day (like a log file) you could keep a cache of sorted numbers and wouldn't need to parse it whole every time.

share|improve this answer
1  
Neat! 2 seconds (on not particularly fast drives) with 200,000 random lines entries in mainfile (ie. 600,000 lines) and 143,000 random keys (that's just how my test data ended up)... tested, and it works (but you knew that :) ... I do wonder about the {12}.. OP has used 12, but the example keys are 13 long... –  Peter.O Jan 21 '12 at 15:20
1  
Just a little note, you can do it without dealing with temporary files by using <(grep...sort) where the file names are. –  Kevin Jan 21 '12 at 17:20
    
Thank you, but grepping and sorting the files takes much longer than my previous loop (+2min.). –  Teresa e Junior Jan 21 '12 at 19:36
    
@Teresa e Junior. How big is your main file? ... You have mentioned that it grows at 200,000 lines a day, but not how big it is... To reduce the amount of data you nee to process, you can read just the current days' 200,000 lines by taking a note of the last line number processed (yesterday) and using tail -n +$linenum to output only the latest data. That way you will be processing only approximately 200,000 lines each day.. I just tested it with 6 million lines in main-file and 10 thousand keys... time: real 0m0.016s, user 0m0.008s, sys 0m0.008s –  Peter.O Jan 21 '12 at 19:56
    
I'm really quite puzzled/curious about how you can grep your main file 10,000 times and find it faster than this method which only greps it once (and once for the much smaller file1)... Even if your sort takes longer than my test, I just can't get my head around the idea that reading a big file that many times doesn't outweigh a single sort (timewise) –  Peter.O Jan 21 '12 at 20:16

Yes, definitely do use a database. They're made exactly for tasks like this.

share|improve this answer
    
Thanks! I don't have much experience with databases. Which database do you recommend? I've got MySQL and the sqlite3 command installed. –  Teresa e Junior Jan 21 '12 at 9:47
1  
They are both fine for this, sqlite is simpler because it's basically just a file and an SQL API to access it. With MySQL you need to set up a MySQL server in order to use it. While that's not very difficult either, sqlite might be best to start with. –  Mika Fischer Jan 21 '12 at 14:07

This might work for you:

 awk '/^[0-9]/{a[$0]++}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3

EDIT:

Amended script to allow for duplicates and unknown keys in both files, still produces keys from the first file not present in the second:

 awk '/^[0-9]/{if(FNR==NR){a[$0]=1;next};if($0 in a){a[$0]=2}}END{for(x in a)if(a[x]==1)print x}' file{1,2} >file3
share|improve this answer
    
This will miss new keys which occur more than once in the main file (and for that matter, which occurr more than once in the keys file) It seems to require that the array count incrementing of the main file is not alowed to exceed 1, or some equivalent workaround (+1 because it is pretty close to the mark) –  Peter.O Jan 22 '12 at 4:40
1  
I tried with gawk and mawk, and it outputs wrong keys... –  Teresa e Junior Jan 22 '12 at 6:42
    
@Peter.O I assumed the main file had unique keys and that file 2 was a subset of the main file. –  potong Jan 22 '12 at 15:11
    
@potong The second one works good and very fast! Thank you! –  Teresa e Junior Jan 22 '12 at 16:55
    
@Teresa e Junior Are you sure it is working correctly yet?.. Using the test data you provided, which should output 5000 keys, when I run it, it produces 136703 keys, just as I got until I finally understood what your requirements were... @potong Of course! FNR==NR (I've never used it before :) –  Peter.O Jan 22 '12 at 22:17

With that much data, you should really switch to a database. In the meantime, one thing you must do to get anywhere near decent performance is not to search file1 separately for each key. Run a single grep to extract all the non-excluded keys at once. Since that grep also returns lines that don't contain a key, filter those away.

grep -o '[0-9]\{12\}' file2 |
grep -Fxv -f - file1 |
grep -vx '[0-9]\{12\}' >file3

(-Fx means to search whole lines, literally. -f - means to read a list of patterns from standard input.)

share|improve this answer
    
Unless I'm mistaken, this doesn't address the problem of storing keys that aren't in the big file, it will store the keys that are in it. –  Kevin Jan 21 '12 at 17:15
    
@Kevin exactly, and this has forced me to use the loop. –  Teresa e Junior Jan 21 '12 at 18:07
    
@TeresaeJunior: adding -v (-Fxv) may take care of that. –  Dennis Williamson Jan 21 '12 at 18:28
    
@DennisWilliamson That would pick all the lines in the big file that don't match any in the key file, including names, jobs, etc. –  Kevin Jan 22 '12 at 3:26
    
@Kevin Thanks, I'd misread the question. I've added a filter for non-key lines, though my preference now goes to using comm. –  Gilles Jan 22 '12 at 19:12

Permit me to reinforce what others have said, "Get thee to a database!"

There are MySQL binaries freely available for most platforms.

Why not SQLite? It's memory-based, loading a flat-file when you start it, then closing it when you're done. This means that if your computer crashes or the SQLite process goes away, so does all the data.

Your problem looks like just a couple lines of SQL, and will run in milliseconds!

After installing MySQL (which I recommend over other choices), I'd shell out $40 for O'Reilly's SQL Cookbook by Anthony Molinaro, which has lots of problem patterns, starting with simple SELECT * FROM table queries, and going through aggregates and multiple joins.

share|improve this answer
    
Yes, I'll start migrating my data to SQL in a few days, thank you! The awk scripts have been helping me a lot until I get it all done, though! –  Teresa e Junior Jan 27 '12 at 7:59

I'm not sure if this is the exact output that you are looking for, but probably the easiest way is:

grep -o '[0-9]\{12\}' file2 | sed 's/.*/^&$/' > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

You could also use:

sed -ne '/.*\([0-9]\{12\}.*/^\1$/p' file2 > /tmp/numpatterns.grep
grep -vf /tmp/numpatterns.grep file1 > file3
rm -f /tmp/numpatterns.grep

Each of these creates a temporary pattern file which is used to glean out the numbers from the large file (file1).

share|improve this answer
    
I believe this too finds numbers that are in the big file, not those that aren't. –  Kevin Jan 21 '12 at 17:22
    
Correct, I didn't see the '!' in the OP. Just need to use grep -vf instead of grep -f. –  Arcege Jan 21 '12 at 17:40
2  
No @arcege, grep -vf won't display keys not matched, it will display everything including names and jobs. –  Teresa e Junior Jan 21 '12 at 18:11

I fully agree with you getting a database (MySQL is fairly easy to use). Until you get that running, I like Angus's comm solution, but so many people are trying with grep and getting it wrong that I thought I'd show the (or at least one) correct way to do it with grep.

grep -o '[0-9]\{12\}' keyfile | grep -v -f <(grep -o '^[0-9]\{12\}' bigfile) 

The first grep gets the keys. The third grep (in the <(...)) takes all the keys used in the big file, and the <(...) passes it like a file as an argument to -f in the second grep. That causes the second grep to use it as a list of lines to match. It then uses this to match its input (the list of keys) from the pipe (first grep), and prints any keys extracted from the key file and not (-v) the big file.

Of course you can do this with temporary files you have to keep track of and remember to delete:

grep -o '[0-9]\{12\}'  keyfile >allkeys
grep -o '^[0-9]\{12\}' bigfile >usedkeys
grep -v -f usedkeys allkeys

This prints all lines in allkeys that don't appear in usedkeys.

share|improve this answer
    
Unfortunately it is slow, and I get a memory error after 40 seconds: grep: Memory exhausted –  Peter.O Jan 22 '12 at 4:59
    
@Peter.O But it's correct. Anyway, that's why I'd suggest a database or comm, in that order. –  Kevin Jan 22 '12 at 5:43
    
Yes that works, but is much slower than the loop. –  Teresa e Junior Jan 22 '12 at 6:43

The keyfile does not change? Then you should avoid searching the old entries again and again.

With tail -f you can get the output of a growing file.

tail -f growingfile | grep -f keyfile 

grep -f reads the patterns from a file, one line as a pattern.

share|improve this answer
    
That would be good, but the key file is always different. –  Teresa e Junior Jan 22 '12 at 17:49

Wasn't going to post my answer because I thought that such amount of data shouldn't be processed with a shell script, and the right answer to use a database was already given. But since now there are 7 other approaches...

Reads the first file in memory, then greps the second file for numbers and checks if values are stored in memory. It should be faster than multiple greps, if you have enough memory to load the whole file, that is.

declare -a record
while read key
do
    read name
    read job
    record[$key]="$name:$job"
done < file1

for number in $(grep -o '[0-9]\{12\}' file2)
do
    [[ -n ${mylist[$number]} ]] || echo $number >> file3
done
share|improve this answer
    
I've got enough memory, but I found this one even slower. Thanks though! –  Teresa e Junior Jan 22 '12 at 20:05

I agree with @jan-steinman that you should use a database for this kind of task. There are lots of ways to hack together a solution with a shell script as the other answers show, but doing it that way will lead to a lot of misery if you're going to use and maintain the code for any length of time more than just a one-day throw-away project.

Assuming you're on a Linux box then you most likely have Python installed by default which includes the sqlite3 library as of Python v2.5. You can check your Python version with:

% python -V
Python 2.7.2+

I recommend using sqlite3 library because it is a simple file-based solution that exists for all platforms (including inside your web browser!) and it does not require a server to be installed. Essentially zero-configuration and zero-maintenance.

Below is a simple python script that will parse the file format that you gave as an example and then does a simple "select all" query and outputs everything it stored in the db.

#!/usr/bin/env python

import sqlite3
import sys

dbname = '/tmp/simple.db'
filename = '/tmp/input.txt'
with sqlite3.connect(dbname) as conn:
    conn.execute('''create table if not exists people (key integer primary key, name text, job text)''')
    with open(filename) as f:
        for key in f:
            key = key.strip()
            name = f.next().strip()
            job = f.next().strip()
            try:
                conn.execute('''insert into people values (?,?,?)''', (key, name, job))
            except sqlite3.IntegrityError:
                sys.stderr.write('record already exists: %s, %s, %s\n' % (key, name, job))
    cur = conn.cursor()

    # get all people
    cur.execute('''select * from people''')
    for row in cur:
        print row

    # get just two specific people
    person_list = [1358726575123, 9973834728345]
    cur.execute('''select * from people where key in (?,?)''', person_list)
    for row in cur:
        print row

    # a more general way to get however many people are in the list
    person_list = [1358726575123, 9973834728345]
    template = ','.join(['?'] * len(person_list))
    cur.execute('''select * from people where key in (%s)''' % (template), person_list)
    for row in cur:
        print row

Yes, this means that you'll need to learn some SQL, but it will be well worth it in the long run. Also, instead of parsing your log files, maybe you could write data directly to your sqlite database.

share|improve this answer
    
Thank you for the python script! I think /usr/bin/sqlite3 works the same way for shell scripts (packages.debian.org/squeeze/sqlite3), though I've never used it. –  Teresa e Junior Jan 27 '12 at 8:04
    
Yes, you can use /usr/bin/sqlite3 with shell scripts, however I recommend avoiding shell scripts except for simple throw-away programs and instead use a language like python which has better error handling and is easier to maintain and grow. –  aculich Jan 27 '12 at 16:46

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.