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 with about 30.000.000 lines (Radius Accounting) and I need to find the last match of a given pattern.

The command:

tac accounting.log | grep $pattern

gives what I need, but it's too slow because the OS has to first read the whole file and then send to the pipe.

So, I need something fast that can read the file from the last line to the first.

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

I don't understand why you're using tac, it does not help you unless you also use grep -m 1 (assuming GNU grep) to have grep stop after the first match:

tac accounting.log | grep -m 1 foo

From man grep:

   -m NUM, --max-count=NUM
          Stop reading a file after NUM matching lines.  

In the example in your question, both tac and grep need to process the entire file so using tac is kind of pointless.

So, unless you use grep -m, don't use tac at all, just parse the output of grep to get the last match:

grep foo accounting.log | tail -n 1 

Another approach would be to use Perl or any other scripting language. For example (where $pattern=foo):

perl -ne '$l=$_ if /foo/; END{print $l}' file

or

awk '/foo/{k=$0}END{print k}' file
share|improve this answer
1  
I'm using tac because I need to find the last match of a given pattern. Using your suggestion "grep -m1" the execution time goes from 0m0.597s to 0m0.007s \o/. Thanks everybody! –  Hábner Costa Feb 2 at 17:46
1  
@HábnerCosta you're very welcome. I understand why you're using tac, my point was that it doesn't help unless you also use -m since the file still needs to be read in full by two programs. Otherwise, you could just search for all occurences and keep only the last one as I do with tail -n 1. –  terdon Feb 2 at 17:49
1  
Why do you say "tac [...] needs to process the entire file"? The first thing tac does is seek to the end of the file and read a block from the end. You can verify this yourself with strace(1). When combined with grep -m, it should be quite efficient. –  camh Feb 4 at 8:16
    
@camh when combined with grep -m it is. The OP was not using -m so both grep and tac were processing the whole thing. –  terdon Feb 4 at 13:57
    
@StephaneChazelas true, but unlikely and I did not want to give the impression that the -e was necessary for the reversal. I changed $pattern to foo to be on the safe side. –  terdon Feb 4 at 14:30
add comment

The reason why

tac file | grep foo | head -n 1

doesn't stop at the first match is because of buffering.

Normally, head -n 1 exits after reading a line. So grep should get a SIGPIPE and exit as well as soon as it writes its second line.

But what happens is that because its output is not going to a terminal, grep buffers it. That is, it's not writing it until it has accumulated enough (4096 bytes in my test with GNU grep).

What that means is that grep will not exit before it has written 8192 bytes of data, so probably quite a few lines.

With GNU grep, you can make it exit sooner by using --line-buffered which tells it to write lines as soon as they are found regardless of whether goes to a terminal or not. So grep would then exit upon the second line it finds.

But with GNU grep anyway, you can use -m 1 instead as @terdon has shown, which is better as it exits at the first match.

If your grep is not the GNU grep, then you can use sed or awk instead. But tac being a GNU command, I doubt you'll find a system with tac where grep is not GNU grep.

tac file | sed "/$pattern/!d;q"                             # BRE
tac file | P=$pattern awk '$0 ~ ENVIRON["P"] {print; exit}' # ERE

Some systems have tail -r to do the same thing as GNU tac does.

Note that, for regular (seekable) files, tac and tail -r are efficient because they do read the files backward, they're not just reading the file fully in memory before printing it backward (as @slm's sed approach or tac on non-regular files would).

On systems where neither tac nor tail -r are available, the only options are to implement the backward-reading by hand with programming languages like perl or use:

grep -e "$pattern" file | tail -n1

Or:

sed "/$pattern/h;$!d;g" file

But those mean finding all the matches and only print the last one.

share|improve this answer
    
+1 very nice explanations! –  slm Feb 4 at 13:28
add comment

Using sed

Showing some alternative methods to @Terdon's fine answer using sed:

$ sed '1!G;h;$!d' file | grep -m 1 $pattern
$ sed -n '1!G;h;$p' file | grep -m 1 $pattern

Examples

$ seq 10 > file

$ sed '1!G;h;$!d' file | grep -m 1 5
5

$ sed -n '1!G;h;$p' file | grep -m 1 5
5

Using Perl

As a bonus here's a little easier notation in Perl to remember:

$ perl -e 'print reverse <>' file | grep -m 1 $pattern

Example

$ perl -e 'print reverse <>' file | grep -m 1 5
5
share|improve this answer
1  
That's (especially the sed one) likely to be several orders of magnitude slower than grep 5 | tail -n1 or sed '/5/h;$!d;g'. It will also potentially use a lot of memory. It's not a lot more portable as you're still using GNU's grep -m. –  Stephane Chazelas Feb 4 at 11:26
add comment

Here is a possible solution that will find the location of first occurrence of pattern from last:

tac -s "$pattern" -r accounting.log | head -n 1

This makes use of the -s and -r switches of tac which are as follows:

-s, --separator=STRING
use STRING as the separator instead of newline

-r, --regex
interpret the separator as a regular expression
share|improve this answer
add comment

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.