2

I just realized that I could solve this problem by reversing line numbers from 1, 2, 3,...,n to n, n-1, ..., 3,2,1 and then use the same logic as earlier. So I want to know how can I reverse the order of lines?

Community
  • 1

4 Answers4

5

tac (cat backwards, and included in coreutils as well) will cat a file in reverse order:

$ cat /tmp/test
One
Two
Three

$ tac /tmp/test
Three
Two
One

(In the case of the particular problem you mentioned the solutions there are better than reversing the entire file just so you can append a file and reverse the whole file again)

Michael Mrozek
  • 93,103
  • 40
  • 240
  • 233
  • go on and elaborate on the last point. I am uncertain what you are really aiming at. Does it not depend on the file system so on data stuctures and how it saves files how good some method really is? Suppose lines are connected with linked list that forms a torus so it requires only constant time to reverse the file (namely to read backwards). But sure if line connections are done differently, it can require more ops, not just constant time and that way "better" -- but I cannot see this method worse than the other methods without knowing the file system and how lines are connected. –  Sep 18 '11 at 16:37
  • @hhh If lines were really connected in a circular linked list then inserting one at the end would be O(1), but I'm pretty sure no filesystem in the world has ever done that. Most likely your files are just stored on disk linearly; filesystems don't have a concept of "lines" in a file – Michael Mrozek Sep 18 '11 at 16:49
  • 2
    @hhh All unix systems store text files as a flat sequence of characters, with the LF character (\n) marking the end of each line. There are a few OSes that store files as arrays of records (lines), but even if you were to access such files from unix, there is no API to read them other than byte by byte. – Gilles 'SO- stop being evil' Sep 18 '11 at 17:41
4

For your particular problem, this is not the most efficient way to go about it, however, you can use any of the following to print a file with lines in reverse order, with varying degrees of portability (tac for example is not included by default on many Unixes):

  • sed '1!G;h;$!d' [file]
  • awk '{f[n=NR]=$0}END{for(i=n;i>0;i--)print f[i]}' [file]
  • perl -e 'print reverse<>' [file]
  • tac [file]

On my system the fastest is tac, as tested by the following:

$ printf '%s\n' {a..z}{a..z}{a..z} > foo
$ time sed '1!G;h;$!d' foo > /dev/null 2>&1

real    0m0.582s
user    0m0.544s
sys     0m0.012s

$ time awk '{f[n=NR]=$0}END{for(i=n;i>0;i--)print f[i]}' foo > /dev/null 2>&1

real    0m0.060s
user    0m0.052s
sys     0m0.008s

$ time perl -e 'print reverse<>' foo > /dev/null 2>&1

real    0m0.021s
user    0m0.016s
sys     0m0.004s

$ time tac foo > /dev/null 2>&1

real    0m0.003s
user    0m0.004s
sys     0m0.000s

... so if you have tac, use it, but otherwise, use perl or awk.

Chris Down
  • 125,559
  • 25
  • 270
  • 266
  • Your awk one-liner's printf will fail if the input contains % sign. Better use a separate format string: printf "%s",i. – manatwork Sep 19 '11 at 07:56
  • @manatwork Good point, fixed. – Chris Down Sep 19 '11 at 13:04
  • Taking another look at your code alternatives, those concatenations in awk and perl are slowing down your solutions. I suggest to change your strategy and spare the concatenations by using arrays: awk '{f[n=NR]=$0}END{for(i=n;i>0;i--)print f[i]}' foo and perl -ne 'push@f,$_;END{print reverse@f}' foo. – manatwork Sep 19 '11 at 13:38
  • @manatwork - Thanks for the awk array suggestion, that was the original one I posted, but I forgot to compare the efficiency of the two methods. As for perl, is there any reason not to simply do perl -e 'print reverse<>'? It seems to be slightly less expensive. – Chris Down Sep 19 '11 at 13:46
  • No reason excepting my lack of knowledge. – manatwork Sep 19 '11 at 13:49
2

The tac utility reverses lines. It is cat in reverse.

Shawn J. Goff
  • 46,081
1

GNU utilities (Linux, Cygwin) and BusyBox have the tac command, which reverses the order of the lines in a text file.

On systems that don't have tac, you can work it from standard commands. Chris Down's answer shows a few ways to do it by storing the file entirely in memory. For a very large file, a way that will work without thrashing on most unices is to make sort do the reversal. This is not as efficient for medium-sized files, but sort implementations can typically cope with files that are larger than the available memory.

nl | sort -nr | sed 's/.*\t//'

(Replace \t by a literal tab character.)

As already noted by Michael Mrozek, reversing lines is a poor way of prepending data to a file. The method is hard to understand, and performs a lot of extra work.

Community
  • 1
Gilles 'SO- stop being evil'
  • 829,060