Let’s start with the simplest linear time implementation of the Fibonacci number generating algorithm in Python:

def LinearFibonacci(n):
  fn = f1 = f2 = 1
  for x in xrange(2, n):
    fn = f1 + f2
    f2, f1 = f1, fn
  return fn

The theory says that this algorithm should run in O(n) - given the n-th Fibonacci number to find, the algorithm does a single loop up to n.

Now let’s verify if this algorithm is really linear in practice. If it’s linear then the plot of n vs. running time of LinearFibonacci(n) should be a line. I plotted these values for n up to 200,000 and here is the plot that I got:

Note: Each data point was averaged over 10 calculcations.

Oh no! This does not look linear at all! It looks quadratic! I fitted the data with a quadratic function and it fit nearly perfectly. Do you know why the seemingly linear algorithm went quadratic?

The answer is that the theoretical analysis assumed that all the operations in the algorithm executed in constant time. But this is not the case when we run the algorithm on a real machine! As the Fibonacci numbers get larger, each addition operation for calculating the next Fibonacci number “fn = f1 + f2 ” runs in time proportional to the length of the previous Fibonacci number. It’s because these huge numbers no longer fit in the basic units of computation in the CPU; so a big integer library is required. The addition of two numbers of length O(n) in a big integer library takes time of O(n).

I’ll show you that the running time of the real-life linear Fibonacci algorithm really is O(n^2) by taking into account this hidden cost of bigint library.

So at each iteration i we have a hidden cost of O(number of digits of f_i) = O(digits(f_i)). Let’s sum these hidden cost for the whole loop up to n:

Now let’s find the number of digits in the n-th Fibonacci number. To do that let’s use the well-known Binet’s formula, which tells us that the n-th Fibonacci number f_n can be expressed as:

It is also well-known that the number of digits in a number is integer part of log₁₀(number) + 1. Thus the number of digits in the n-th Fibonacci number is:

Thus if we now sum all the hidden costs for finding the n-th Fibonacci number we get:

There we have it. The running time of this “linear” algorithm is actually quadratic if we take into consideration that each addition operation runs proportionally to the length of addends.

Next time I’ll show you that if the addition operation runs in constant time, then the algorithm is truly linear; and later I will do a similar analysis of the logarithmic time algorithm for finding Fibonnaci numbers that uses this awesome matrix identity:

Don’t forget to subscribe if you are interested! It’s well worth every byte!

To get things going I’ll assume that you know what the two’s complement binary representation of an integer is and also that you know all the the bitwise operations.

I’ll use the following notation for bitwise operations in the article:

&   -  bitwise and
|   -  bitwise or
^   -  bitwise xor
~   -  bitwise not
<<  -  bitwise shift right
>>  -  bitwise shift left

The numbers in the article are 8 bit signed integers (though the operations work on arbitrary length signed integers) that are represented as two’s complement and they are usually named ‘x’. The result is usually ‘y’. The individual bits of ‘x’ are named b7, b6, b5, b4, b3, b3, b2, b1 and b0. The bit b7 is the sign bit (the most significant bit), and b0 is the least significant.

I’ll start with the most basic bit hacks and gradually progress to more difficult ones. I’ll use examples to explain how each bithack works.

If you are intrigued by this topic I urge you to subscribe to my blog. I can share a secret that there will be the 2nd part of this article where I cover more advanced bit hacks, and I will also release a cheat sheet with all these bit tricks! It’s well worth subscribing!

Here we go.

Bit Hack #1. Check if the integer is even or odd.

if ((x & 1) == 0) {
  x is even
}
else {
  x is odd
}

I am pretty sure everyone has seen this trick. The idea here is that an integer is odd if and only if the least significant bit b0 is 1. It follows from the binary representation of ‘x’, where bit b0 contributes to either 1 or 0. By AND-ing ‘x’ with 1 we eliminate all the other bits than b0. If the result after this operation is 0, then ‘x’ was even because bit b0 was 0. Otherwise ‘x’ was odd.

Let’s look at some examples. Let’s take integer 43, which is odd. In binary 43 is 00101011. Notice that the least significant bit b0 is 1 (in bold). Now let’s AND it with 1:

    00101011
&   00000001   (note: 1 is the same as 00000001)
    --------
    00000001

See how AND-ing erased all the higher order bits b1-b7 but left bit b0 the same it was? The result is thus 1 which tells us that the integer was odd.

Now let’s look at -43. Just as a reminder, a quick way to find negative of a given number in two’s complement representation is to invert all bits and add one. So -43 is 11010101 in binary. Again notice that the last bit is 1, and the integer is odd. (Note that if we used one’s complement it wouldn’t be true!)

Now let’s take a look at an even integer 98. In binary 98 is 1100010.

    01100010
&   00000001
    --------
    00000000

After AND-ing the result is 0. It means that the bit b0 of original integer 98 was 0. Thus the given integer is even.

Now the negative -98. It’s 10011110. Again, bit b0 is 0, after AND-ing, the result is 0, meaning -98 is even, which indeed is true.

Bit Hack #2. Test if the n-th bit is set.

if (x & (1<<n)) {
  n-th bit is set
}
else {
  n-th bit is not set
}

In the previous bit hack we saw that (x & 1) tests if the first bit is set. This bit hack improves this result and tests if n-th bit is set. It does it by shifting that first 1-bit n positions to the left and then doing the same AND operation, which eliminates all bits but n-th.

Here is what happens if you shift 1 several positions to the left:

1         00000001    (same as 1<<0)
1<<1      00000010
1<<2      00000100
1<<3      00001000
1<<4      00010000
1<<5      00100000
1<<6      01000000
1<<7      10000000

Now if we AND ‘x’ with 1 shifted n positions to the left we effectively eliminate all the bits but n-th bit in ‘x’. If the result after AND-ing is 0, then that bit must have been 0, otherwise that bit was set.

Let’s look at some examples.

Does 122 have 3rd bit set? The operation we do to find it out is:

122 & (1<<3)

Now, 122 is 01111010 in binary. And (1<<3) is 00001000.

    01111010
&   00001000
    --------
    00001000

We see that the result is not 0, so yes, 122 has the 3rd bit set.

Note: In my article bit numeration starts with 0. So it’s 0th bit, 1st bit, …, 7th bit.

What about -33? Does it have the 5th bit set?

    11011111      (-33 in binary)
&   00100000     (1<<5)
    --------
    00000000

Result is 0, so the 5th bit is not set.

Bit Hack #3. Set the n-th bit.

y = x | (1<<n)

This bit hack combines the same (1<<n) trick of setting n-th bit by shifting with OR operation. The result of OR-ing a variable with a value that has n-th bit set is turning that n-th bit on. It’s because OR-ing any value with 0 leaves the value the same; but OR-ing it with 1 changes it to 1 (if it wasn’t already). Let’s see how that works in action:

Suppose we have value 120, and we wish to turn on the 2nd bit.

    01111000    (120 in binary)
|   00000100    (1<<2)
    --------
    01111100

What about -120 and 6th bit?

    10001000   (-120 in binary)
|   01000000   (1<<6)
    --------
    11001000

Bit Hack #4. Unset the n-th bit.

y = x & ~(1<<n)

The important part of this bithack is the ~(1<<n) trick. It turns on all the bits except n-th.

Here is how it looks:

~1        11111110  (same as ~(1<<0))
~(1<<1)   11111101
~(1<<2)   11111011
~(1<<3)   11110111
~(1<<4)   11101111
~(1<<5)   11011111
~(1<<6)   10111111
~(1<<7)   01111111

The effect of AND-ing variable ‘x’ with this quantity is eliminating n-th bit. It does not matter if the n-th bit was 0 or 1, AND-ing it with 0 sets it to 0.

Here is an example. Let’s unset 4th bit in 127:

    01111111    (127 in binary)
&   11101111    (~(1<<4))
    --------
    01101111

Bit Hack #5. Toggle the n-th bit.

y = x ^ (1<<n)

This bit hack also uses the wonderful “set n-th bit shift hack” but this time it XOR’s it with the variable ‘x’. The result of XOR-ing something with something else is that if both bits are the same, the result is 0, otherwise it’s 1. How does it toggle n-th bit? Well, if n-th bit was 1, then XOR-ing it with 1 changes it to 0; conversely, if it was 0, then XOR-ing with with 1 changes it to 1. See, the bit got flipped.

Here is an example. Suppose you want to toggle 5th bit in value 01110101:

    01110101
^   00100000
    --------
    01010101

What about the same value but 5th bit originally 0?

    01010101
^   00100000
    --------
    01110101

Notice something? XOR-ing the same bit twice returned it to the same value. This nifty XOR property is used in calculating parity in RAID arrays and used in simple cryptography cyphers, but more about that in some other article.

Bit Hack #6. Turn off the rightmost 1-bit.

y = x & (x-1)

Now it finally gets more interesting!!! Bit hacks #1 - #5 were kind of boring to be honest.

This bit hack turns off the rightmost one-bit. For example, given an integer 00101010 (the rightmost 1-bit in bold) it turns it into 00101000. Or given 00010000 it turns it into 0, as there is just a single 1-bit.

Here are more examples:

    01010111    (x)
&   01010110    (x-1)
    --------
    01010110

    01011000    (x)
&   01010111    (x-1)
    --------
    01010000

    10000000    (x = -128)
&   01111111    (x-1 = 127 (with overflow))
    --------
    00000000

    11111111    (x = all bits 1)
&   11111110    (x-1)
    --------
    11111110

    00000000    (x = no rightmost 1-bits)
&   11111111    (x-1)
    --------
    00000000

Why does it work?

If you look at the examples and think for a while, you’ll realize that there are two possible scenarios:

1. The value has the rightmost 1 bit. In this case subtracting one from it sets all the lower bits to one and changes that rightmost bit to 0 (so that if you add one now, you get the original value back). This step has masked out the rightmost 1-bit and now AND-ing it with the original value zeroes that rightmost 1-bit out.

2. The value has no rightmost 1 bit (all 0). In this case subtracting one underflows the value (as it’s signed) and sets all bits to 1. AND-ing all zeroes with all ones produces 0.

Bit Hack #7. Isolate the rightmost 1-bit.

y = x & (-x)

This bit hack finds the rightmost 1-bit and sets all the other bits to 0. The end result has only that one rightmost 1-bit set. For example, 01010100 (rightmost bit in bold) gets turned into 00000100.

Here are some more examples:

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

    01110000  (x)
&   10010000  (-x)
    --------
    00010000

    00000001  (x)
&   11111111  (-x)
    --------
    00000001

    10000000  (x = -128)
&   10000000  (-x = -128)
    --------
    10000000

    11111111  (x = all bits one)
&   00000001  (-x)
    --------
    00000001

    00000000  (x = all bits 0, no rightmost 1-bit)
&   00000000  (-x)
    --------
    00000000

This bit hack works because of two’s complement. In two’s complement system -x is the same as ~x+1. Now let’s examine the two possible cases:

1. There is a rightmost 1-bit b_i. In this case let’s pivot on this bit and divide all other bits into two flanks - bits to the right and bits to the left. Remember that all the bits to the right b_i-1, b_i-2 … b₀ are 0’s (because b_i was the rightmost 1-bit). And bits to the left are the way they are. Let’s call them b_i+1, …, b_n.

Now, when we calculate -x, we first do ~x which turns bit b_i into 0, bits b_i-1 … b₀ into 1s, and inverts bits b_i+1, …, b_n, and then we add 1 to this result.

Since bits b_i-1 … b₀ are all 1’s, adding one makes them carry this one all the way to bit b_i, which is the first zero bit.

If we put it all together, the result of calculating -x is that bits b_i+1, …, b_n get inverted, bit b_i stays the same, and bits b_i-1, …, b₀ are all 0’s.

Now, AND-ing x with -x makes bits b_i+1, …, b_n all 0, leaves bit b_i as is, and sets bits b_i-1, …, b₀ to 0. Only one bit is left, it’s the bit b_i - the rightmost 1-bit.

2. There is no rightmost 1-bit. The value is 0. The negative of 0 in two’s complement is also 0. 0&0 = 0. No bits get turned on.

We have proved rigorously that this bithack is correct.

Bit Hack #8. Right propagate the rightmost 1-bit.

y = x | (x-1)

This is best understood by an example. Given a value 01010000 it turns it into 01011111. All the 0-bits right to the rightmost 1-bit got turned into ones.

This is not a clean hack, tho, as it produces all 1’s if x = 0.

Let’s look at more examples:

    10111100  (x)
|   10111011  (x-1)
    --------
    10111111

    01110111  (x)
|   01110110  (x-1)
    --------
    01110111

    00000001  (x)
|   00000000  (x-1)
    --------
    00000001

    10000000  (x = -128)
|   01111111  (x-1 = 127)
    --------
    11111111

    11111111  (x = -1)
|   11111110  (x-1 = -2)
    --------
    11111111

    00000000  (x)
|   11111111  (x-1)
    --------
    11111111

Let’s prove it, though not as rigorously as in the previous bithack (as it’s too time consuming and this is not a scientific publication). There are two cases again. Let’s start with easiest first.

1. There is no rightmost 1-bit. In that case x = 0 and x-1 is -1. -1 in two’s complement is 11111111. OR-ing 0 with 11111111 produces the same 11111111. (Not the desired result, but that’s the way it is.)

2. There is the rightmost 1-bit b_i. Let’s divide all the bits in two groups again (like in the previous example). Calculating x-1 modifies only bits to the right, turning b_i into 0, and all the lower bits to 1’s. Now OR-ing x with x-1 leaves all the higher bits (to the left) the same, leaves bit b_i as it was 1, and since lower bits are all low 1’s it also turns them on. The result is that the rightmost 1-bit got propagated to lower order bits.

Bit Hack #9. Isolate the rightmost 0-bit.

y = ~x & (x+1)

This bithack does the opposite of #7. It finds the rightmost 0-bit, turns off all bits, and sets this bit to 1 in the result. For example, it finds the zero in bold in this number 10101011, producing 00000100.

More examples:

    10111100  (x)
    --------
    01000011  (~x)
&   10111101  (x+1)
    --------
    00000001

    01110111  (x)
    --------
    10001000  (~x)
&   01111000  (x+1)
    --------
    00001000

    00000001  (x)
    --------
    11111110  (~x)
&   00000010  (x+1)
    --------
    00000010

    10000000  (x = -128)
    --------
    01111111  (~x)
&   10000001  (x+1)
    --------
    00000001

    11111111  (x = no rightmost 0-bit)
    --------
    00000000  (~x)
&   00000000  (x+1)
    --------
    00000000

    00000000  (x)
    --------
    11111111  (~x)
&   00000001  (x+1)
    --------
    00000001

Proof: Suppose there is a rightmost 0-bit. Then ~x turns this rightmost 0 bit into 1 bit. And so does x+1 (because bits more right to the rightmost 0 bit are 1’s). Now AND-ing ~x with x+1 evaporates all the bits up to this rightmost 0 bit. This is the highest order bit set in the result. Now what about lower order bits to the right of rightmost 0 bit? They also got evaporated because because x+1 turned them into 0’s (they were 1’s) and ~x turned them into 0’s. They got AND-ed with 0 and evaporated.

Bit Hack #10. Turn on the rightmost 0-bit.

y = x | (x+1)

This hack changes the rightmost 0-bit into 1. For example, given an integer 10100011 it turns it into 10100111.

More examples:

    10111100  (x)
|   10111101  (x+1)
    --------
    10111101

    01110111  (x)
|   01111000  (x+1)
    --------
    01111111

    00000001  (x)
|   00000010  (x+1)
    --------
    00000011

    10000000  (x = -128)
|   10000001  (x+1)
    --------
    10000001

    11111111  (x = no rightmost 0-bit)
|   00000000  (x+1)
    --------
    11111111

    00000000  (x)
|   00000001  (x+1)
    --------
    00000001

Here is the proof as a bunch of true statements. OR-ing x with x+1 does not lose any information. Adding 1 to x fills the first rightmost 0. The result is max{x, x+1}. If x+1 overflows it’s x and there were no 0 bits. If it doesn’t, it’s x+1 which just got rightmost bit filled with 1.

Bonus stuff.

If you decide to play more with these hacks, here are a few utility functions to print binary values of 8 bit signed integers in Perl, Python and C.

Print binary representation in Perl:

sub int_to_bin {
  my $num = shift;
  print unpack "B8", pack "c", $num;
}

Or you can print it from command line right away:

perl -wle 'print unpack "B8", pack "c", shift' 

# For example:
perl -wle 'print unpack "B8", pack "c", shift' 113
01110001

perl -wle 'print unpack "B8", pack "c", shift' -- -128
10000000

Print binary number in Python:

def int_to_bin(num, bits=8):
 r = ''
 while bits:
  r = ('1' if num&1 else '0') + r
  bits = bits - 1
  num = num >> 1
 print r

Print binary representation in C:

void int_to_bin(int num) {
  char str[9] = {0};
  int i;
  for (i=7; i>=0; i--) {
    str[i] = (num&1)?'1':'0';
    num >>= 1;
  }
  printf("%s\n", str);
}

Have fun with these! I’ll write about advanced bit hacks some time soon. If you are really intrigued by this topic I encourage you to subscribe to my blog. Thanks!

Ps. Let me know in the comments what you think about this article, and let me know if you do not know what two’s complement, or the basic binary operations are. If there are a few people who would like me to explain these concepts, I’ll be glad to write another article just about these fundamental topics.

Pps. There is a book entirely on bit hacks like these. It’s called “Hacker’s Delight“. It may be worth getting if you are into this stuff:

Let me quickly explain why this library is useful, and what the Google Sponsored Links are.

For a typical search, Google shows regular web search results on the left side of the page, and “Sponsored Links” in a column on the right side. “Sponsored” means the results are pulled from Googe’s advertising network (Adwords).

Here is a screenshot that illustrates the Sponsored Links:

Google Sponsored Links results for search term “security” are in red.

Okay, now why would I need a library to search the Sponsored results? Suppose that I am an advertiser on Adwords, and I buy some software related keywords like “video software”. It is in my interests to know my competitors, their advertisement text, what are they up to, the new players in this niche, and their websites. Without my library it would be practically impossible to keep track of all the competitors. There can literally be hundreds of changes per day. However, with my library it’s now piece of cake to keep track of all the dynamics.

How does the library work?

The sponsored links library pulls the results from this URL: http://www.google.com/sponsoredlinks. Here is an example of all the sponsored results for a query “security”:

Sponsored links results for “security”.

The library just grabs page after page, calls BeautifulSoup, and extracts the search result elements. Elementary.

How to use the library?

As I mentioned, this library is part of my xgoogle library. Download and extract it first:

Download: xgoogle library (.zip)
Downloaded: 1116 times.
Download url: http://www.catonmat.net/download/xgoogle.zip

Now, the source file that contains the implementation of this library is “xgoogle/sponsoredlinks.py”. To use it, do the usual import “from xgoogle.sponsoredlinks import SponsoredLinks, SLError”.

SponsoredLinks is the class that provides the API and SLError is exception class that gets thrown in case of errors, so it’s a good idea to import both.

The SponsoredLinks has a similar interface as the xgoogle.search (the plain google search module). The constructor of SponsoredLinks takes the keyword you want to search for, and the constructed object has several public methods and properties:

• method get_results() - gets a page of results, returning a list of SponsoredLink objects. It returns an empty list if there are no more results.
• property num_results - returns number of search results found.
• property results_per_page - sets/gets the number of results to get per page (max 100).

The returned SponsoredLink objects have four attributes — “title”, “desc”, “url”, and “display_url”. Here is a picture that illustrates what each attribute stands for:

The picture does not show the “display_url” attribute as it’s the actual link the result links to (href of blue link in the pic).

Here is an example usage of this library. It retrieves first 100 Sponsored Links results for keyword “video software”:

from xgoogle.sponsoredlinks import SponsoredLinks, SLError
try:
  sl = SponsoredLinks("video software")
  sl.results_per_page = 100
  results = sl.get_results()
except SLError, e:
  print "Search failed: %s" % e

for result in results:
  print result.title.encode('utf8')
  print result.desc.encode('utf8')
  print result.display_url.encode('utf8')
  print result.url.encode('utf8')
  print

Output:

Photoshop Video Software
Time saving software for video. Work faster in Photoshop.
www.toolsfortelevision.com
http://www.toolsfortelevision.com

...

That’s about it for this time. Use it to find your competitors and outsmart them!

Next time I am going to expand the library for Google Sets search.

Have fun!

Why didn’t I use Google’s provided REST API? Because it says “you can only get up to 8 results in a single call and you can’t go beyond the first 32 results”. Seriously, what am I gonna do with just 32 results?

I wrote it because I want to do various Google hacks automatically, monitor popularity of some keywords and sites, and to use it for various other reasons.

One of my next post is going to extend on this library and build a tool that perfects your English. I have been using Google for a while to find the correct use of various English idioms, phrases, and grammar. For example, “i am programmer” vs. “i am a programmer”. The first one is missing an indefinite article “a”, but the second is correct. Googling for these terms reveal that the first has 6,230 results, but the second has 136,000 results, so I pretty much trust that the 2nd is more correct than the first.

Subscribe to my posts via catonmat’s rss, if you are intrigued and would love to receive my posts automatically!

How to use the library?

First download the xgoogle library, and extract it somewhere.

Download: xgoogle library (.zip)
Downloaded: 1116 times.
Download url: http://www.catonmat.net/download/xgoogle.zip

At the moment it contains just the code for Google search, but in the future I will add other searches (google sets, google suggest, etc).

To use the search, from “xgoogle.search” import “GoogleSearch” and, optionally, “SearchError“.

GoogleSearch is the class you will use to do Google searches. SearchError is an exception class that GoogleSearch throws in case of various errors.

Pass the keyword you want to search as the first parameter to GoogleSearch’s constructor. The constructed object has several public methods and properties:

• method get_results() - gets a page of results, returning a list of SearchResult objects. It returns an empty list if there are no more results.
• property num_results - returns number of search results found.
• property results_per_page - sets/gets the number of results to get per page. Possible values are 10, 25, 50, 100.
• property page - sets/gets the search page.

As I said, get_results() method returns a SearchResult object. It has three attributes — “title”, “desc”, and “url”. They are Unicode strings, so do a proper encoding before outputting them.

Here is a screenshot that illustrates the “title”, “desc”, and “url” attributes:

Google search result for “catonmat”.

Here is an example program of doing a Google search. It takes the first argument, does a search on it, and prints the results:

from xgoogle.search import GoogleSearch, SearchError
try:
  gs = GoogleSearch("quick and dirty")
  gs.results_per_page = 50
  results = gs.get_results()
  for res in results:
    print res.title.encode('utf8')
    print res.desc.encode('utf8')
    print res.url.encode('utf8')
    print
except SearchError, e:
  print "Search failed: %s" % e

This code fragment sets up a search for “quick and dirty” and specifies that a result page should have 50 results. Then it calls get_results() to get a page of results. Finally it prints the title, description and url of each search result.

Here is the output from running this program:

Quick-and-dirty - Wikipedia, the free encyclopedia
Quick-and-dirty is a term used in reference to anything that is an easy way to implement a kludge. Its usage is popular among programmers, ...
http://en.wikipedia.org/wiki/Quick-and-dirty

Grammar Girl's Quick and Dirty Tips for Better Writing - Wikipedia ...
"Grammar Girl's Quick and Dirty Tips for Better Writing" is an educational podcast that was launched in July 2006 and the title of a print book that was ...Writing - 39k -
http://en.wikipedia.org/wiki/Grammar_Girl%27s_Quick_and_Dirty_Tips_for_Better_Writing

Quick & Dirty Tips :: Grammar  Girl
Quick & Dirty Tips(tm) and related trademarks appearing on this website are the property of Mignon Fogarty, Inc. and Holtzbrinck Publishers Holdings, LLC. ...
http://grammar.quickanddirtytips.com/
[...]

Compare these results to the output above.

You could also have specified which search page to start the search from. For example, the following code will get 25 results per page and start the search at 2nd page.

  gs = GoogleSearch("quick and dirty")
  gs.results_per_page = 25
  gs.page = 2
  results = gs.get_results()

You can also quickly write a scraper to get all the results for a given search term:

from xgoogle.search import GoogleSearch, SearchError
try:
  gs = GoogleSearch("quantum mechanics")
  gs.results_per_page = 100
  results = []
  while True:
    tmp = gs.get_results()
    if not tmp: # no more results were found
      break
    results.extend(tmp)
  # ... do something with all the results ...
except SearchError, e:
  print "Search failed: %s" % e

You can use this library to constantly monitor how your website is ranking for a given search term. Suppose your website has a domain “catonmat.net” and the search term you want to find your position for is “python videos”.

Here is a code that outputs your ranking: (it looks through first 100 results, if you need more, put a loop there)

import re
from urlparse import urlparse
from xgoogle.search import GoogleSearch, SearchError

target_domain = "catonmat.net"
target_keyword = "python videos"

def mk_nice_domain(domain):
    """
    convert domain into a nicer one (eg. www3.google.com into google.com)
    """
    domain = re.sub("^www(\d+)?\.", "", domain)
    # add more here
    return domain

gs = GoogleSearch(target_keyword)
gs.results_per_page = 100
results = gs.get_results()
for idx, res in enumerate(results):
  parsed = urlparse(res.url)
  domain = mk_nice_domain(parsed.netloc)
  if domain == target_domain:
    print "Ranking position %d for keyword '%s' on domain %s" % (idx+1, target_keyword, target_domain)

Output of this program:

Ranking position 6 for keyword python videos on domain catonmat.net
Ranking position 7 for keyword python videos on domain catonmat.net

Here is a much wicked example. It uses the GeoIP Python module to find all 10 websites for keyword “wicked code” that are physically hosting in California or New York in USA. Make sure you download GeoCityLite database from “http://www.maxmind.com/download/geoip/database/GeoLiteCity.dat.gz” and extract it to “/usr/local/geo_ip”.

import GeoIP
from urlparse import urlparse
from xgoogle.search import GoogleSearch, SearchError

class Geo(object):
  GEO_PATH = "/usr/local/geo_ip/GeoLiteCity.dat"

  def __init__(self):
    self.geo = GeoIP.open(Geo.GEO_PATH, GeoIP.GEOIP_STANDARD)

  def detect_by_host(self, host):
    try:
      gir = self.geo.record_by_name(host)
      return {'country': gir['country_code'].lower(),
              'region': gir['region'].lower()}
    except Exception, e:
      return {'country': 'none', 'region': 'none'}

dst_country = 'us'
dst_states = ['ca', 'ny']
dst_keyword = "wicked code"
num_results = 10
final_results = []
geo = Geo()

gs = GoogleSearch(dst_keyword)
gs.results_per_page = 100

seen_websites = []
while len(final_results) < num_results:
  results = gs.get_results()
  domains = [urlparse(r.url).netloc for r in results]
  for d in domains:
    geo_loc = geo.detect_by_host(d)
    if (geo_loc['country'] == dst_country and
                 geo_loc['region'] in dst_states and
                 d not in seen_websites):
      final_results.append((d, geo_loc['region']))
      seen_websites.append(d)
      if len(final_results) == num_results:
        break

print "Found %d websites:" % len(final_results)
for w in final_results:
    print "%s (state: %s)" % w

Here is the output of running it:

Found 10 websites:
www.wickedcode.com (state: ca)
www.retailmenot.com (state: ca)
www.simplyhired.com (state: ca)
archdipesh.blogspot.com (state: ca)
wagnerblog.com (state: ca)
answers.yahoo.com (state: ca)
devsnippets.com (state: ca)
friendfeed.com (state: ca)
www.thedacs.com (state: ny)
www.tipsdotnet.com (state: ca)

You may modify these examples the way you wish. I’d love to hear some comments about what you can come up with!

And just for fun, here are some other simple uses:

You can make your own Google Fight:

import sys
from xgoogle.search import GoogleSearch, SearchError

args = sys.argv[1:]
if len(args) < 2:
 print 'Usage: google_fight.py "keyword 1" "keyword 2"'
 sys.exit(1)

try:
  n0 = GoogleSearch('"%s"' % args[0]).num_results
  n1 = GoogleSearch('"%s"' % args[1]).num_results
except SearchError, e:
  print "Google search failed: %s" % e
  sys.exit(1)

if n0 > n1:
  print "%s wins with %d results! (%s had %d)" % (args[0], n0, args[1], n1)
elif n1 > n0:
  print "%s wins with %d results! (%s had %d)" % (args[1], n1, args[0], n0)
else:
  print "It's a tie! Both keywords have %d results!" % n1

Download: google_fight.py
Downloaded: 540 times.
Download url: http://www.catonmat.net/download/google_fight.py

Here is an example usage of google_fight.py:

$ ./google_fight.py google microsoft
google wins with 2680000000 results! (microsoft had 664000000)

$ ./google_fight.py "linux ubuntu" "linux gentoo"
linux ubuntu wins with 4300000 results! (linux gentoo had 863000)

After I wrote this, I generalized this Google Fight to take N keywords, and made their passing to program easier by allowing them to be separated by a comma.

import sys
from operator import itemgetter
from xgoogle.search import GoogleSearch, SearchError

args = sys.argv[1:]
if not args:
  print "Usage: google_fight.py keyword one, keyword two, ..."
  sys.exit(1)

keywords = [k.strip() for k in ' '.join(args).split(',')]
try:
  results = [(k, GoogleSearch('"%s"' % k).num_results) for k in keywords]
except SearchError, e:
  print "Google search failed: %s" % e
  sys.exit(1)

results.sort(key=itemgetter(1), reverse=True)
for res in results:
    print "%s: %d" % res

Download: google_fight2.py
Downloaded: 520 times.
Download url: http://www.catonmat.net/download/google_fight2.py

Here is an example usage of google_fight2.py:

$ ./google_fight2.py earth atmospehere, sun atmosphere, moon atmosphere, jupiter atmosphere
earth atmospehere: 685000
jupiter atmosphere: 31400
sun atmosphere: 24900
moon atmosphere: 8130

I am going to expand on this library and add search for Google Sets, Google Sponsored Links, Google Suggest, and perhaps some other Google searches. Then I’m going to build various tools on them, like a sponsored links competitor finder, use Google Suggest together with Google Sets to find various phrases in English, and apply them to tens of other my ideas.

Lecture twenty begins with a good overview of multithreaded programming paradigm, introduces to various concepts of parallel programming and at the end talks about Cilk programming language.

Lecture twenty-one implements several multithreaded algorithms, such as nxn matrix addition, nxn matrix multiplication, and parallel merge-sort. It then goes into great detail to analyze the running time and parallelism of these algorithms.

Lecture 20: Parallel Algorithms I

The lecture starts with an introduction to a particular model of parallel computation called dynamic multithreading. It’s easiest to understand this model with an example. Here is a multithreaded algorithm that computes Fibonacci numbers:

Fibonacci(n):
1   if n < 2:                     | thread A
2     return n                    | thread A
3   x = spawn Fibonacci(n-1)      | thread A
4   y = spawn Fibonacci(n-2)      | thread B
5   sync                          | thread C
6   return x + y                  | thread C

# this is a really bad algorithm, because it’s
# exponential time.
#
# see lecture three for four different
# classical algorithms that compute Fibonacci numbers

(A thread is defined to be a maximal sequence of instructions not containing the parallel control statements spawn, sync, and return, not something like Java threads or Posix threads.)

I put the most important keywords in bold. They are “spawn” and “sync“.

The keyword spawn is the parallel analog of an ordinary subroutine call. Spawn before the subroutine call in line 3 indicates that the subprocedure Fibonacci(n-1) can execute in parallel with the procedure Fibonacci(n) itself. Unlike an ordinary function call, where the parent is not resumed until after its child returns, in the case of a spawn, the parent can continue to execute in parallel with the child. In this case, the parent goes on to spawn Fibonacci(n-2). In general, the parent can continue to spawn off children, producing a high degree of parallelism.

A procedure cannot safely use the return values of the children it has spawned until it executes a sync statement. If any of its children have not completed when it executes a sync, the procedure suspends and does not resume until all of its children have completed. When all of its children return, execution of the procedure resumes at the point immediately following the sync statement. In the Fibonacci example, the sync statement in line 5 is required before the return statement in line 6 to avoid the anomaly that would occur if x and y were summed before each had been computed.

The spawn and sync keywords specify logical parallelism, not “actual” parallelism. That is, these keywords indicate which code may possibly execute in parallel, but what actually runs in parallel is determined by a scheduler, which maps the dynamically unfolding computation onto the available processors.

The lecture then continues with a discussion on how a parallel instruction stream can be viewed as a directed acyclic graph G = (V, E), where threads make up the set V of vertices, and each spawn and return statement makes up an edge in E. There are also continuation edges in E that exist between statements.

In Fibonacci example there are three threads: lines 1, 2, 3 make up the thread A, line 4 is thread B and lines 5, 6 are thread C.

Here is how a graph of Fibonacci(4) computation looks like:

A dag representing multithreaded computation of Fibonacci(4).

Here the threads are show as circles, and each group of threads belonging to the same procedure are surrounded by a rounded rectangle. Downward edges are spawn dependencies, horizontal edges represent continuation dependencies within a procedure, and upward edges are return dependencies. Every computation starts with a single initial thread, and ends with a single final thread.

So to compute Fib(4), first Fib(3) and Fib(2) have to be computed. Fib(4) spawns one thread to compute Fib(3) and another thread to compute Fib(2) and sync’es. In order to compute Fib(3), values of Fib(2) and Fib(1) have to be known, and to compute Fib(2) values of Fib(1) and Fib(0) have to be known. Fib(3) and Fib(2) spawn their threads and sync. This way the computation unwinds.

Next, the lecture introduces some concepts for measuring performance of multithreaded algorithms.

First some time measures:

• T_p - running time of an algorithm on p processors,
• T₁ - running time of algorithm on 1 processor, and
• T_∞ as critical path length, that is the longest time to execute the algorithm on infinite number of processors.

Based on these measures, the speedup of a computation on p processors is T₁/T_p, that is how much faster a p processor machine executes the algorithm than a one processor machine. If the speedup is O(p), then we say that the computation has a linear speedup. If, however, speedup > p, then we call it a super-linear speedup. The maximum possible speedup is called parallelism and is computed by T₁/T_∞.

After these concepts the lecture puts forward the concept of scheduling and greedy scheduler.

A scheduler maps computation to p processors.

The greedy scheduler schedules as much as it can at every time step. On a p-processor machine every step can be classified into two types. If there are p or more threads ready to execute, the scheduler executes any p of them (this step is also called a complete step). If there are fewer than p threads, it executes all of them (called incomplete step). The greedy scheduler is an offline scheduler and it’s 2-competitive (see lecture 13 on online/offline algorithms and the meaning of competitive algorithm).

The lecture ends with an introduction to Cilk parallel, multithreaded programming language. It uses a randomized online scheduler. It was used to write two chess programs *Socrates and Cilkchess.

See Charles Leiseron’s handout for a much more comprehensive overview of dynamic multithreading: A Minicourse on Dynamic Multithreaded Algorithms (pdf).

You’re welcome to watch lecture twenty:

Topics covered in lecture twenty:

• [01:33] Parallel algorithms.
• [02:33] Dynamic multi-threading.
• [03:15] A multithreaded algorithm for fibonnaci numbers.
• [04:50] Explanation of spawn and sync.
• [06:45] Logical parallelism.
• [08:00] Multithreaded computation.
• [12:15] Fibonacci(4) computation graph, and its concepts - init thread, spawn edge, continuation edge, return edge, final thread.
• [17:45] Edges: spawn, return, continuation.
• [19:40] Performance measures: running time on p processors T_p, work (serial time) T₁, critcial path length (longest path) T_infinity.
• [24:15] Lower bounds on T_p (running time on p processors).
• [29:35] Speedup, linear speedup, superlinear speedup.
• [32:55] Maximum possible speedup.
• [36:40] Scheduling.
• [38:55] Greedy scheduler.
• [43:40] Theorem by Grant and Brent (bound on T_p for greedy scheduler).
• [46:20] Proof of Grant, Brent theorem.
• [56:50] Corollary on greedy scheduler’s linear speedup.
• [01:02:20] Cilk programming language.
• [01:06:00] Chess programs: *Socrates, Clikchess.
• [01:06:30] Analysis of *Socrates running time on 512 processors.

Lecture twenty notes:

Lecture 20, page 1 of 2: dynamic multithreading, multithreaded computation, performance measures, speedup, scheduling, greedy scheduler.

Lecture 20, page 2 of 2: grant, brent theorem, cilk, socrates, cilkchess.

Lecture 21: Parallel Algorithms II

Lecture twenty-one is all about real multithreaded algorithms and their analysis.

It starts with a hugly important problem of multithreaded matrix multiplication: given two nxn matrices A and B, write a multithreaded algorithm Matrix-Multiply that multiplies them, producing matrix C. The natural approach is to use divide and conquer method from lecture three, and formulate the problem as follows:

Each nxn matrix can be expressed as 8 multiplications and 4 additions of (n/2)x(n/2) submatrices. So the first thing we need is Matrix-Add algorithm that adds two matrices in parallel.

Here is the parallel Matrix-Add algorithm:

Matrix-Add(C, T, n):
   // Adds matrices C and T in-place, producing C = C + T
   // n is power of 2 (for simplicity).
   if  n == 1:
     C[1, 1] = C[1, 1] + T[1, 1]
   else:
     partition C and T into (n/2)x(n/2) submatrices
     spawn Matrix-Add(C11, T11, n/2)
     spawn Matrix-Add(C12, T12, n/2)
     spawn Matrix-Add(C21, T21, n/2)
     spawn Matrix-Add(C22, T22, n/2)
     sync

The base case for this algorithm is when matrices are just scalars, then it just adds the only element of both matrices. In all other cases, it partitions matrices C and T into (n/2)x(n/2) matrices and spawns four subproblems.

Now we can implement the Matrix-Multiply algorithm, by doing 8 multiplications in parallel and then calling Matrix-Add to do 4 additions.

Here is the parallel Matrix-Multiply algorithm:

Matrix-Multiply(C, A, B, n):
   // Multiplies matrices A and B, storing the result in C.
   // n is power of 2 (for simplicity).
   if  n == 1:
     C[1, 1] = A[1, 1] · B[1, 1]
   else:
     allocate a temporary matrix T[1...n, 1...n]
     partition A, B, C, and T into (n/2)x(n/2) submatrices
     spawn Matrix-Multiply(C12,A11,B12, n/2)
     spawn Matrix-Multiply(C21,A21,B11, n/2)
     spawn Matrix-Multiply(C22,A21,B12, n/2)
     spawn Matrix-Multiply(T11,A12,B21, n/2)
     spawn Matrix-Multiply(T12,A12,B22, n/2)
     spawn Matrix-Multiply(T21,A22,B21, n/2)
     spawn Matrix-Multiply(T22,A22,B22, n/2)
     sync
     Matrix-Add(C, T, n)

The lecture then proceeds to calculating how good the algorithm is, turns out the parallelism (ratio of time of algorithm running on a single processor T₁ to running on infinite number of processors T_inf) for doing 1000×1000 matrix multiplication is 10⁷, which the parallel algorithm is fast as hell.

Matrix-Multiply used a temporary matrix which was actually unnecessary. To achieve higher performance, it’s often advantageous for an algorithm to use less space, because more space means more time. Therefore a faster algorithm can be added that multiplies matrices and adds them in-place. See lecture at 33:05 for Matrix-Multiply-Add algorithm. The parallelism of this algorithm for 1000×1000 matrix multiplication is 10⁶, smaller than the previous one, but due to fact that no temporary matrices had to be used, it beats Matrix-Multiply algorithm in practice.

The lecture then proceeds to parallel sorting. The classical sorting algorithms were covered in lectures four and five. This lecture parallelizes the Merge-Sort algorithm.

Here is the parallel merge-sort algorithm:

Parallel-Merge-Sort(A, p, r): // sort A[p...r]
  if p < r:
    q = floor((p+r)/2)
    spawn Parallel-Merge-Sort(A, p, q)
    spawn Parallel-Merge-Sort(A, q+1, r)
    sync
    Merge(A, p, q, r) // merge A[p...q] with A[q+1...r]

Instead of recursively calling Parallel-Merge-Sort for subproblems, we spawn them, thus utilizing the power of parallelism. After doing analysis turns out that due to fact that we use the classical Merge() function, the parallelism is just lg(n). That’s puny!

To solve this problem, a Parallel-Merge algorithm has to be written. The lecture continues with presenting a Parallel-Merge algorithm, and after that does the analysis of the same Parallel-Merge-Sort algorithm but with Parallel-Merge function. Turns out this algorithm has parallelism of n/lg²(n), that is much better. See lecture at 51:00 for Parallel-Merge algorithm.

The best parallel sorting algorithm know to date has the parallelism of n/lg(n).

You’re welcome to watch lecture twenty-one:

Topics covered in lecture twenty-one:

• [00:35] Multithreaded algorithms.
• [01:32] Multithreaded matrix multiplication.
• [02:05] Parallelizing with divide and conquer.
• [04:30] Algorithm Matrix-Multiply, that computes C = A*B.
• [10:13] Algorithm Matrix-Add, that computes C = C+T.
• [12:45] Analysis of running time of Matrix-Multiply and Matrix-Add.
• [19:40] Analysis of critical path length of Matrix-Multiply and Matrix-Add.
• [26:10] Parallelism of Matrix-Multiply and Matrix-Add.
• [33:05] Algorithm Matrix-Multiply-Add, that computes C = C + A*B.
• [35:50] Analysis of Matrix-Multiply-Add.
• [42:30] Multithreaded, parallel sorting.
• [43:30] Parallelized Merge-Sort algorithm.
• [45:55] Analysis of multithreaded Merge-Sort.
• [51:00] Parallel-Merge algorithm.
• [01:00:30] Analysis of Parallel-Merge algorithm.

Lecture twenty-one notes:

Lecture 21, page 1 of 2: multithreaded algorithms, matrix multiplication, analysis (critical path length, parallelism).

Lecture 21, page 2 of 2: paralel sorting, merge sort, parallel merge, analysis.

Have fun with parallel, multithreaded algorithms! The next post is going to be on cache oblivious algorithms! They are a class of algorithms that exploit all the various caches in modern computer architecture to make them run notably faster.

This lecture is given by JavaScript guru Doug Crockford. He’s the author of JSON, JSMin JavaScript minifier and JSLint.

The talk is based on Douglas’s recent book “JavaScript: The Good Parts“. It’s excellent.

The lecture begins with a brief intro of why JavaScript is the way it is and how it came to be so. An interesting point Doug makes is that JavaScript is basically Scheme, except with Java syntax. He talks about the bad and good parts of JavaScript and gives a few examples of common JavaScript problems, their solutions and patterns. Douglas also talks about how he discovered JSON. After the talk there is a 13 minute Q and A.

You’re welcome to watch the video lecture. It’s 1 hour long and it will definitely make your understanding of JavaScript better:

Here are some interesting points from the lecture:

[09:57] JavaScript was influenced by Scheme, Java and Perl. From Scheme it borrowed lambda functions and loose typing. From Java it took most of the syntax, and from Perl some of its regular expressions. And finally, it derived the idea of prototypal inheritance and dynamic objects from Self. See my previous post on JavaScript for explanation of prototypal inheritance.

[11:38] JavaScript bad parts:

• Global variables. Global variables make it harder to run independent subprograms in the same program. If the subprograms happen to have global variables that share the same names, then they will interfere with each other and likely fail, usually in difficult to diagnose ways.
• Newlines get converted into semicolons. JavaScript has a mechanism that tries to correct faulty programs by automatically inserting semicolons. It sometimes inserts semicolons in places where they are not welcome. For example:

  return
  {
      status: true
  };
  

  returns undefined because JavaScript inserts ‘;’ after return.

  Correct way:

  return {
      status: true
  };
  

• Operator typeof is not very helpful. For example, “typeof null” is “object”, “typeof [1,2,3]” is also “object”.
• Operator + adds numbers and concatenates. The + operator can add or concatenate. Which one it does depends on the types of the parameters. If either operand is an empty string, it produces the other operand converted to a string. If both operands are numbers, it produces the sum. Otherwise, it converts both operands to strings and concatenates them. This complicated behavior is a common source of bugs. If you intend + to add, make sure that both operands are numbers.
• Operators == and != do type coercion. Use of the === and !== operators is always preferred.
• Too many falsy values. 0, Nan, ” (empty string), false, null, undefined are all false.

[17:25] for … in operator mixes inherited functions with the desired data members (it does deep reflection). Use object.hasOwnProperty to filter out names that belong to object itself:

for (name in object) {
    if (object.hasOwnProperty(name)) {
        ...
    }
}

[22:00] Javascript good parts:

• Lambda. Enough said.
• Dynamic objects. Just add a property to an object, or remove it, no need for classes and derivation to create a similar object.
• Loose Typing. No need for type declarations.
• Object Literals. {} for object literals, [] for array literals and // for regexp literals.

[23:00] Two schools of inheritance - classical and prototypal. Prototypal inheritance means that objects can inherit properties directly from other objects. The language is class-free.

[24:35] Realization of prototypal inheritance in JavaScript:

if (typeof Object.create !== 'function') {
    Object.create = function (o) {
        function F() {}
        F.prototype = o;
        return new F();
    };
}

Now a newObject can be created by inheriting from oldObject:

newObject = Object.create(oldObject);

[26:05] Example of global variables and why they are bad and how to solve the problem by using closures.

var my_thing = function () {
    var names = ["zero", "one", ... ];
    return function(n) {
        return names[n];
    };
}();

[29:00] There are four ways to create a new object in JavaScript:

• Object literal — var object = { }.
• New — var object = new Object()
• Object.create — var object = Object.create(old_object).
• Call another constructor (use different inheritance model).

[42:42] JSLint. JSLint defines a professional subset of JavaScript. JSLint will hurt your feelings.

[52:00] Q/A: Does strict mode change the behavior or does it take things out? — Can’t have “with” in strict mode, changes the way eval() works, changes error handling.

[53:00] Q/A: What’s going on with DOM? — Ajax libraries fix DOM, these changes should be propagated back into DOM API.

[55:30] Q/A: How do you spell lambda in JavaScript? — function.

[55:54] Q/A: How to solve global variable problem? — Each of compilation unit should be isolated, but there should be a way how they can introduce (link) to each other.

[56:30] Q/A: How do JavaScript objects differ from hash tables, they seem the same to me?

[57:23] Q/A: What’s wrong with HTML 5 and web apps? — They are doing too much and there are way too many of them.

[59:10] Q/A: How come JSON and JavaScript have almost the same syntax? — Doug admits he forgot to include Unicode Line Separator (LS) and Paragraph Separator (PS) control codes as whitespace chars.

[01:00:32] Q/A: Why does JSON require quotes around the property names? — Three reasons: 1. Wanted to align with Python where quotes are required, 2. Wanted to make the grammar of standard simpler, 3. JavaScript has stupid reserved word policy.

[01:02:40] Q/A: Are there any prospects for adding concurrency to the language? — Definitely no threads. Could be some kind of a messaging model.

If you liked this talk, I recommend that you get Doug’s book:

Happy javascripting!

A tiny intro to those unfamiliar with the awk1line.txt and sed1line.txt files — they contain around 80 useful awk and sed one-liners for doing various text file manipulations. Some examples are double spacing a file, numbering the lines, doing various text substitutions, etc. They were compiled by Eric Pement. Kudos to him!

The article will be divided in six parts. In parts 1 - 5 I will create the one-liners and explain them, and in part 6 I will release the perl1line.txt file. I found that splitting the article in many parts is much easier to get it written, that’s why I do it.

Here is the general plan:

• Part I: File spacing.
• Part II: Numbering and calculations.
• Part III: String creation. Array creation.
• Part IV: Text conversion and substitution.
• Part V: Selective printing and deleting of certain lines.
• Part VI: Release of perl1line.txt.

The one-liners will make heavy use of Perl special variables. Luckily, a few years ago I compiled all the Perl special vars in a single file and called it Perl special variable cheat-sheet. Even tho it’s mostly copied out of perldoc perlvar, it’s still handy to have in front of you. I suggest that you print it.

Other than that, I can’t wait to start writing the article, so here I go:

File Spacing

1. Double space a file.

perl -pe '$\="\n"'

This one-liner double spaces a file. There are three things to explain in this one-liner. The “-p” and “-e” command line options, and the “$\” variable.

First let’s start with the “-e” option. The “-e” option can be used to enter a Perl program directly in the command line. Typically you don’t want to create source files for every small program. By using “-e” you can handily specify the program to execute on the command line.

Next the “-p” switch. Specifying “-p” to a Perl program causes it to assume the following loop around your program:

while (<>) {
    # your program goes here
} continue {
    print or die "-p failed: $!\n";
}

This construct loops over all the input, executes your code and prints the value of “$_”. This way you can effectively modify all or some lines of input. The “$_” variable can be explained as an anonymous variable that gets filled with the good stuff.

The “$\” variable is similar to ORS in Awk. It gets appended after every “print” operation. Without any arguments “print” prints the contents of “$_” (the good stuff).

In this one-liner the code specified by “-e” is ‘$\=”\n”‘, thus the whole program looks like this:

while (<>) {
    $\ = "\n";
} continue {
    print or die "-p failed: $!\n";
}

What happens is that after reading each line, “$_” gets filled with it (including the existing line’s newline), the “$\” gets set to a newline itself and “print” is called. As I already mentioned, without any arguments “print” prints the contents of “$_” and “$\” gets appended at the end. The result is that each line gets printed unmodified and it’s followed by the “$\” which has been set to newline. The input has been double-spaced.

There is actually no need to set “$\” to newline on each line. It was just the shortest possible one-liner that double-spaced the file. Here are several others that do the same:

perl -pe 'BEGIN { $\="\n" }'

This one sets the “$\” to newline just once before Perl does anything (BEGIN block gets executed before everything else).

perl -pe '$_ .= "\n"'

This one-liner is equivalent to:

while (<>) {
    $_ = $_ . "\n"
} continue {
    print or die "-p failed: $!\n";
}

It appends another new-line at the end of each line, then prints it out.

The cleanest and coolest way to do it is probably use the substitution “s///” operator:

perl -pe 's/$/\n/'

It replaces the regular expression “$” that matches at the end of line with a newline, effectively adding a newline at the end.

2. Double space a file, except the blank lines.

perl -pe '$_ .= "\n" unless /^$/'

This one-liner double spaces all lines that are not completely empty. It does it by appending a newline character at the end of each line that is not blank. The “unless” means “if not”. And “unless /^$/” means “if not ‘beginning is end of line’”. The condition “beginning is end of line” is true only for lines that contain the newline character.

Here is how it looks when expanded:

while (<>) {
    if ($_ !~ /^$/) {
        $_ .= "\n"
    }
} continue {
    print or die "-p failed: $!\n";
}

A better test that takes spaces and tabs on the line into account is this one:

perl -pe '$_ .= "\n" if /\S/'

Here the line is matched against “\S”. “\S” is a regular expression that is the inverse of “\s”. The inverse of “\s” is any non-whitespace character. The result is that every line that has at least one non-whitespace character (tab, vertical tab, space, etc) gets double spaced.

3. Triple space a file.

perl -pe '$\="\n\n"'

Or

perl -pe '$_.="\n\n"'

They are the same as one-liner #1, except that two new-lines get appended after each line.

4. N-space a file.

perl -pe '$_.="\n"x7'

This one-liner uses inserts 7 new lines after each line. Notice how I used ‘”\n” x 7′ to repeat the newline char 7 times. The “x” operator repeats the thing on the left N times.

For example:

perl -e 'print "foo"x5'

would print “foofoofoofoofoo”.

5. Add a blank line before every line.

perl -pe 's//\n/'

This one-liner uses the “s/pattern/replacement/” operator. It substitutes the first pattern (regular expression) in the “$_” variable with the replacement. In this one-liner the pattern is empty, meaning it matches any position between chars (and in this case it’s the position before first char) and replaces it with “\n”. The effect is that a newline char gets inserted before the line.

6. Remove all blank lines.

perl -ne 'print unless /^$/'

This one-liner uses “-n” flag. The “-n” flag causes Perl to assume to following loop around your program:

LINE:
while (<>) {
    # your program goes here
}

What happens here is that each line gets read by the diamond “<>” operator and is placed in the dolar underscore special variable “$_”. At this moment you are free to do with it whatever you want. You specify that in your main program text.

In this one-liner the main program is “print unless /^$/”, it gets inserted in the while loop above and the whole Perl program becomes:

LINE:
while (<>) {
    print unless /^$/
}

Unraveling it further:

LINE:
while (<>) {
    print $_ unless $_ =~ /^$/
}

This one-liner prints all non-blank lines.

A few other ways to do the same:

perl -lne 'print if length'

This one uses the “-l” command line argument. The “-l” automatically chomps the input line (basically gets rid of newline at the end). Next the line is tested for its length. If there are any chars left, it evals to true and the line gets printed.

perl -ne 'print if /\S/'

This one-liner behaves differently than the “print unless /^$/” one-liner. The “print unless /^$/” one-liner prints lines with spaces and tabs, this one doesn’t.

7. Remove all consecutive blank lines, leaving just one.

perl -00 -pe ''

Ok, this is really tricky, ain’t it? First of all it does not have any code, the -e is empty. Next it has a silly -00 command line option. This command line option turns paragraph slurp mode on. A paragraph is text between two newlines. All the other newlines get ignored. The paragraph gets put in “$_” and the “-p” option prints it out.

8. Compress/expand all blank lines into N consecutive ones.

perl -00 -pe '$_.="\n"x4'

This one-liner combines the previous one and one-liner #4. It slurps lines paragraph wise, then appends (N-1) new-line. This one-liner expands (or compresses) all new-lines to 5 (”\n” x 4 prints four, and there was one at the end of paragraph itself, so 5).

Have Fun!

Have fun with these file spacing one-liners. The next part is going to be about line numbering and calculations one-liners.

Can you think of other file spacing operations that I did not include here?

Netcat is often referred to as a “Swiss Army knife” utility, and for a good reason. Just like the multi-function usefulness of the venerable Swiss Army pocket knife, netcat’s functionality is as helpful. Some of its features include port scanning, transferring files, port listening and it can be used a backdoor.

In 2006 netcat was ranked #4 in “Top 100 Network Security Tools” survey, so it’s definitely a tool to know.

See the first post on pipe viewer for the introduction to this article series. If you feel like you are interested in this stuff, I suggest that you subscribe to my rss feed to receive my future posts automatically.

How to use nc?

Let’s start with a few very simple examples and build up on those.

If you remember, I said that netcat was a Swiss Army knife. What would a Swiss Army knife be if it also wasn’t a regular knife, right? That’s why netcat can be used as a replacement of telnet:

$ nc www.google.com 80

It’s actually much more handy than the regular telnet because you can terminate the connection at any time with ctrl+c, and it handles binary data as regular data (no escape codes, nothing).

You may add “-v” parameter for more verboseness, and two -v’s (-vv) to get statistics of how many bytes were transmitted during the connection.

Netcat can also be used as a server itself. If you start it as following, it will listen on port 12345 (on all interfaces):

$ nc -l -p 12345

If you now connect to port 12345 on that host, everything you type will be sent to the other party, which leads us to using netcat as a chat server. Start the server on one computer:

# On a computer A with IP 10.10.10.10
$ nc -l -p 12345

And connect to it from another:

# On computer B
$ nc 10.10.10.10 12345

Now both parties can chat!

Talking of which, the chat can be turned to make two processes talk to each other, thus making nc do I/O over network! For example, you can send the whole directory from one computer to another by piping tar to nc on the first computer, and redirecting output to another tar process on the second.

Suppose you want to send files in /data from computer A with IP 192.168.1.10 to computer B (with any IP). It’s as simple as this:

# On computer A with IP 192.168.1.10
$ tar -cf - /data | nc -l -p 6666

# On computer B
$ nc 192.168.1.10 6666 | tar -xf -

Don’t forget to combine the pipeline with pipe viewer from previous article in this series to get statistics on how fast the transfer is going!

A single file can be sent even easier:

# On computer A with IP 192.168.1.10
$ cat file | nc -l -p 6666

# On computer B
$ nc 192.168.1.10 6666 > file

You may even copy and restore the whole disk with nc:

# On computer A with IP 192.168.1.10
$ cat /dev/hdb | nc -l -p 6666

# On computer B
$ nc 192.168.1.10 6666 > /dev/hdb

Note: It turns out that “-l” can’t be used together with “-p” on a Mac! The solution is to replace “-l -p 6666″ with just “-l 6666″. Like this:

$ nc -l 6666

# nc now listens on port 6666 on a Mac computer

An uncommon use of netcat is port scanning. Netcat is not the best tool for this job, but it does it ok (the best tool is nmap):

$ nc -v -n -z -w 1 192.168.1.2 1-1000
(UNKNOWN) [192.168.1.2] 445 (microsoft-ds) open
(UNKNOWN) [192.168.1.2] 139 (netbios-ssn) open
(UNKNOWN) [192.168.1.2] 111 (sunrpc) open
(UNKNOWN) [192.168.1.2] 80 (www) open
(UNKNOWN) [192.168.1.2] 25 (smtp) : Connection timed out
(UNKNOWN) [192.168.1.2] 22 (ssh) open

The “-n” parameter here prevents DNS lookup, “-z” makes nc not to receive any data from the server, and “-w 1″ makes the connection timeout after 1 second of inactivity.

Another uncommon behavior is using netcat as a proxy. Both ports and hosts can be redirected. Look at this example:

$ nc -l -p 12345 | nc www.google.com 80

This starts a nc server on port 12345 and all the connections get redirected to google.com:80. If you now connect to that computer on port 12345 and do a request, you will find that no data gets sent back. That’s correct, because we did not set up a bidirectional pipe. If you add another pipe, you can get the data back on another port:

$ nc -l -p 12345 | nc www.google.com 80 | nc -l -p 12346

After you have sent the request on port 12345, connect on port 12346 to get the data.

Probably the most powerful netcat’s feature is making any process a server:

$ nc -l -p 12345 -e /bin/bash

The “-e” option spawns the executable with it’s input and output redirected via network socket. If you now connect to the host on port 12345, you may use bash:

$ nc localhost 12345
ls -las
total 4288
   4 drwxr-xr-x 15 pkrumins users    4096 2009-02-17 07:47 .
   4 drwxr-xr-x  4 pkrumins users    4096 2009-01-18 21:22 ..
   8 -rw-------  1 pkrumins users    8192 2009-02-16 19:30 .bash_history
   4 -rw-r--r--  1 pkrumins users     220 2009-01-18 21:04 .bash_logout
   ...

The consequences are that nc is a popular hacker tool as it is so easy to create a backdoor on any computer. On a Linux computer you may spawn /bin/bash and on a Windows computer cmd.exe to have total control over it.

That’s everything I can think of. Do you know any other netcat uses that I did not include?

How to install nc?

If you’re on Debian or Debian based system such as Ubuntu do the following:

$ sudo aptitude install netcat

If you’re on Fedora or Fedora based system such as CentOS do:

$ sudo yum install netcat

If you’re on Slackware, FreeBSD, NetBSD, Solaris or Mac, download the source code of nc and just:

$ tar -zxf nc-version.tar.gz
$ cd nc-version
$ ./configure && sudo make install

Another way to do it on Mac, if you have MacPorts is:

$ sudo port install netcat

On Slackware you can actually install it as a package from n/ package directory:

$ sudo installpkg nc-1.10-i386-1.tgz

If you’re on Windows, download the Windoze port of it from securityfocus.

The manual of the utility can be found here man nc.

Have fun netcatting, and until next time!

PS. My website just got featured on makeuseof.com website. Check it out!

I received an email from Eric Pement (the original author of Awk one-liners) and he said that there was a new version of awk1line.txt file available. I did a diff and found that there were seven new one-liners in it!

The new file has two new sections “String Creation” and “Array Creation” and it updates “Selective Printing of Certain Lines” section. I’ll explain the new one-liners in this article.

Here is the latest version of awk1line.txt: awk1line-new.txt.

The original Eric Pement’s Awk one-liner collection consists of five sections, and I explained them in my previous three articles:

• 1. File spacing (explained in part one),
• 2. Numbering and calculations (explained in part one)
• 3. Text conversion and substitution (explained in part two),
• 4. Selective printing of certain lines (explained in part three),
• 5. Selective deletion of certain lines (explained in part three).
• 6. String creation, array creation and update on selective printing of certain lines. (explained in this part).

Okay, let’s roll with the new one-liners:

String Creation

1. Create a string of a specific length (generate a string of x’s of length 513).

awk 'BEGIN { while (a++<513) s=s "x"; print s }'

This one-liner uses the “BEGIN { }” special block that gets executed before anything else in an Awk program. In this block a while loop appends character “x” to variable “s” 513 times. After it has looped, the “s” variable gets printed out. As this Awk program does not have a body, it quits after executing the BEGIN block.

This one-liner printed the 513 x’s out, but you could have used it for anything you wish in BEGIN, main program or END blocks.

Unfortunately this is not the most effective way to do it. It’s a linear time solution. My friend waldner (who, by the way, wrote a guest post on 10 Awk Tips, Tricks and Pitfalls) showed me a solution that’s logarithmic time (based on idea of recursive squaring):

function rep(str, num,     remain, result) {
    if (num < 2) {
        remain = (num == 1)
    } else {
        remain = (num % 2 == 1)
        result = rep(str, (num - remain) / 2)
    }
    return result result (remain ? str  : "")
}

This function can be used as following:

awk 'BEGIN { s = rep("x", 513) }'

2. Insert a string of specific length at a certain character position (insert 49 x’s after 6th char).

gawk --re-interval 'BEGIN{ while(a++<49) s=s "x" }; { sub(/^.{6}/,"&" s) }; 1'

This one-liner works only with Gnu Awk, because it uses the interval expression “.{6}” in the Awk program’s body. Interval expressions were not traditionally available in awk, that’s why you have to use “--re-interval” option to enable them.

For those that do not know what interval expressions are, they are regular expressions that match a certain number of characters. For example, “.{6}” matches any six characters (the any char is specified by the dot “.”). An interval expression “b{2,4}” matches at least two, but not more than four “b” characters. To match words, you have to give them higher precedence - “(foo){4}” matches “foo” repeated four times - “foofoofoofoo”.

The one-liner starts the same way as the previous - it creates a 49 character string “s” in the BEGIN block. Next, for each line of the input, it calls sub() function that replaces the first 6 characters with themselves and “s” appended. The “&” in the sub() function means the matched part of regular expression. The ‘”&” s’ means matched part of regex and contents of variable “s”. The “1″ at the end of whole Awk one-liner prints out the modified line (it’s syntactic sugar for just “print” (that itself is syntactic sugar for “print $0″)).

The same can be achieved with normal standard Awk:

awk 'BEGIN{ while(a++<49) s=s "x" }; { sub(/^....../,"&" s) }; 1

Here we just match six chars “......” at the beginning of line, and replace them with themselves + contents of variable “s”.

It may get troublesome to insert a string at 29th position for example… You’d have to go tapping “.” twenty-nine times “.............................”. Better use Gnu Awk then and write “.{29}”.

Once again, my friend waldner corrected me and pointed to Awk Feature Comparsion chart. The chart suggests that the original one-liner with “.{6}” would also work with POSIX awk, Busybox awk, and Solaris awk.

Array Creation

3. Create an array from string.

split("Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec", month, " ")

This is not a one-liner per se but a technique to create an array from a string. The split(Str, Arr, Regex) function is used do that. It splits string Str into fields by regular expression Regex and puts the fields in array Arr. The fields are placed in Arr[1], Arr[2], …, Arr[N]. The split() function itself returns the number of fields the string was split into.

In this piece of code the Regex is simply space character ” “, the array is month and string is “Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec”. After the split, month[1] is “Jan”, month[2] is “Feb”, …, month[12] is “Dec”.

4. Create an array named “mdigit”, indexed by strings.

for (i=1; i<=12; i++) mdigit[month[i]] = i

This is another array creation technique and not a real one-liner. This technique creates a reverse lookup array. Remember from the previous “one-liner” that month[1] was “Jan”, …, month[12] was “Dec”. Now we want to the reverse lookup and find the number for each month. To do that we create a reverse lookup array “mdigit”, such that mdigit[”Jan”] = 1, …, mdigit[”Dec”] = 12.

It’s really trivial, we loop over month[1], month[2], …, month[12] and set mdigit[month[i]] to i. This way mdigit[”Jan”] = 1, etc.

Selective Printing of Certain Lines

5. Print all lines where 5th field is equal to “abc123″.

awk '$5 == "abc123"'

This one-liner uses idiomatic Awk - if the given expression is true, Awk prints out the line. The fifth field is referenced by “$5″ and it’s checked to be equal to “abc123″. If it is, the expression is true and the line gets printed.

Unwinding this idiom, this one-liner is really equal to:

awk '{ if ($5 == "abc123") { print $0 } }'

6. Print any line where field #5 is not equal to “abc123″.

awk '$5 != "abc123"'

This is exactly the same as previous one-liner, except it negates the comparison. If the fifth field “$5″ is not equal to “abc123″, then print it.

Unwinding it, it’s equal to:

awk '{ if ($5 != "abc123") { print $0 } }'

Another way is to literally negate the whole previous one-liner:

awk '!($5 == "abc123")'

7. Print all lines whose 7th field matches a regular expression.

awk '$7  ~ /^[a-f]/'

This is also idiomatic Awk. It uses “~” operator to test if the seventh “$7″ field matches a regular expression “^[a-f]”. This regular expression means “all lines that start with a lower-case letter a, b, c, d, e, or f”.

awk '$7 !~ /^[a-f]/'

This one-liner matches negates the previous one and prints all lines that do not start with a lower-case letter a, b, c, d, e, and f.

Another way to write the same is:

awk '$7 ~ /^[^a-f]/'

Here we negated the group of letters [a-f] by adding “^” in the group. That’s a regex trick to know.

Have Fun!

Have fun with these Awk oneliners!

If you haven’t already, I recommend that you download my Awk cheat-cheet, read the “10 Awk Tips, Tricks and Pitfalls” article, and study the source code of my YouTube Video Downloader, written entirely in Gnu Awk.

The song is written by Finnish band called “Leech Axss“. This is their second geek song that I have posted on Musical Geek Friday. See “Leech Access is Coming at You“.

I had problems with understanding some parts of the song. I put “(???)” in the lyrics where I was not sure what was being said. I’d appreciate if someone helped me figure it out the correct lyrics!

The song is strongly NSFW, be sure to put your headphones on before listening at work.

Download this song: hax that fsck (musical geek friday #17)
Downloaded: 2626 times

Download lyrics: hax that fsck lyrics (musical geek friday #17)
Downloaded: 616 times

Here is the lyrics (I censored the explicit language, see the ‘download lyrics’ link above for uncensored version):

Hax that f**k, move that box
Exploit a hole in a FireFox
Haxing is about breaking in, not fame
Whoever you be haxing is all the same

Crack that code, buffer overflow
Alt-F4 makes a lamer go
Hax that Gibson and CIA
Sell your soul to the zero da-aa-ay

As you well know, I net sex with duty creatures (???)
I now have sex with the federal agents
You bruteforce the password of gay.com
Knock, knock, it’s the feds and the bubba is on

Right to remain silent like my box in ice
Perfect source code, never write it twice
Better go figure it out before you talk to a fed
It’s a feeling very close to a blue screen of death

A monkey Steve Jobs intringing with Bill Gates
That ain’t gonna tway with the fscking absura blades (????)
Apple in my eye and … (?) in my tank
I bought an itunes that are like tri-hand ****

Still in the game but before I went away
Nerdies want my wishes and they want my zero days
But behave you geeks, and I won’t go latest patch
The one that cycle is Christina Aguilera snatch

Hax that f**k, move that box
Exploit a hole in the FireFox
Haxing is about breaking in, not fame
Whoever you be haxing is all the same

Crack that code, buffer overflow
Alt-F4 makes a lamer go
Hax that Gibson and CIA
Sell your soul to the zero da-aa-ay

I read b0w and b0g
I sport AMD and fscking RISC
I am not like you, I never disrespect my box
Points to stolen motherf*****g Mozilla leanfox

What’s under the hood, I’ve got future of jobs
Sounds like d3s (?) in the court
Drop it like it’s hot, drop it like it’s hot, drop it like it’s hot
Check my benchmark, you skinny retard

[Hshhha] loves a key generator
If it’s not 0day, don’t seed it later
I met my share of lamers, I’ve got some spleen
Zero-bit (?) is like Commander Keen

I’ve been in hax of yours and to haxifice
I’ve seen in the eyes which drugsterize (???)
I’m haxing my way out of the paper bag
Authenticating g in my f*****g … (???)

Hax that f**k, move that box
Exploit a hole in the FireFox
Haxing is about breaking in, not fame
Whoever you be haxing is all the same

Crack that code, buffer overflow
Alt-F4 makes a lamer go
Hack that Gibbson and CIA
Sell your soul to the zero da-aa-ay

Hax that fsck, move that box
Exploit a hole in the FireFox
Haxing is about breaking in, not fame
Whoever you be haxing is all the same

Crack that code, buffer overflow
Alt-F4 makes a lamer go
Hax that Gibson and CIA
Sell your soul to the zero da-aa-ay

If you are intrigued by this topic, I suggest that you subscribe to my posts! For the introduction and first post in this article series, follow this link - Vim Plugins You Should Know About, Part I: surround.vim. Part II is here: repeat.vim.

Matchit extends the existing functionality of “%” key (percent key). I’ll first briefly remind you what the original “%” does and then explain how matchit.vim enhances it.

The original “%” key allows you to jump between various pairs of characters and some programming constructs. For example, it jumps between pairs of parenthesis ( )’s, { }’s, [ ]’s. It also jumps between opening and closing tags of C style comments /* and */. And it’s smart enough to jump between C preprocessor directives - from #if to #endif and match #elif or #else in between.

Here is an example. Suppose you have this code and you press “%”, the cursor jumps between { and } parens:

Matchit.vim extends this functionality. It’s written by Benji Fisher and it adds support to cycle between if, else if, else, endif keywords in various programming languages. Another improvement is the ability to find pairs of HTML tags, such as <p> … </p>. Another handy mapping is “g%” that does “%” in opposite direction (goes from endif to else to else if to if). The plugin also includes several other mappings like “]%”, “[%” and “a%” but I could not figure out how to effectively use them in real life code, so I don’t use them at all.

Here is another example. Suppose you are editing this HTML and you quickly want to go to the corresponding closing tag of <body>. Just press “%”:

Overall it’s a great plugin to have in your inventory!

How to install matchit.vim?

Matchit.vim has been included in vim since version 6.0. However there are newer versions of the script available with bug fixes and enhancements.

To get the latest version:

• 1. Download matchit.zip.
• 2. Extract matchit.zip to ~/.vim (on Unix/Linux) or ~\vimfiles (on Windows).
• 3. Run :helptags ~/.vim/doc (on Unix/Linux) or :helptags ~/vimfiles/doc (on Windows) to rebuild the tags file (so that you can read :help %, :help g%, etc.)
• 4. Restart Vim or source matchit.vim with “:so ~/.vim/plugin/matchit.vim” on Unix or “:so ~/vimfiles/plugin/matchit.vim” on Windows).
• 5. Use ‘%’ to find corresponding

For Python programmers: Turns out the original matchit.vim plugin does not match if / elif / else. Benji extended matchit.vim itself and created “python_matchit.vim“. This extension allows us to use the “%” key to cycle through if/elif/else, try/except/catch, for/continue/break, and while/continue/break structures. The script also defines g% to cycle in the opposite direction, and it defines two other motions, [% and ]%, go to the start and end of the current block, respectively.

How to install python_matchit.vim?

Python_matchit.vim is a filetype plugin. It has to be installed in “ftplugin” directory. Follow these steps to get it installed:

• 1. Download python_matchit.vim.
• 2. Put it in ~/.vim/ftplugin (on Unix/Linux) or ~\vimfiles\ftplugin (on Windows).
• 3. Restart Vim or source matchit.vim with “:so ~/.vim/ftplugin/python_matchit.vim” on Unix or “:so ~/vimfiles/ftplugin/python_matchit.vim” on Windows).

The same steps can be taken to install matchit for Ruby.

Have Fun!

Happy matching with matchit.vim!

Before I start, I want to clarify one thing - Why am I starting so many article series? The answer is that I want to write about many topics simultaneously and switch between them as I feel inspired.

The first post in this series is going to be about not so well known Unix program called Pipe Viewer or pv for short. Pipe viewer is a terminal-based tool for monitoring the progress of data through a pipeline. It can be inserted into any normal pipeline between two processes to give a visual indication of how quickly data is passing through, how long it has taken, how near to completion it is, and an estimate of how long it will be until completion.

Update: French translation available.

Pipe viewer is written by Andrew Wood, an experienced Unix sysadmin. The homepage of pv utility is here: pv utility.

If you feel like you are interested in this stuff, I suggest that you subscribe to my rss feed to receive my future posts automatically.

How to use pv?

Ok, let’s start with some really easy examples and progress to more complicated ones.

Suppose that you had a file “access.log” that is a few gigabytes in size and contains web logs. You want to compress it into a smaller file, let’s say a gunzip archive (.gz). The obvious way would be to do:

$ gzip -c access.log > access.log.gz

As the file is so huge (several gigabytes), you have no idea how long to wait. Will it finish soon? Or will it take another 30 mins?

By using pv you can precisely time how long it will take. Take a look at doing the same through pv:

$ pv access.log | gzip > access.log.gz
611MB 0:00:11 [58.3MB/s] [=>      ] 15% ETA 0:00:59

Pipe viewer acts as “cat” here, except it also adds a progress bar. We can see that gzip processed 611MB of data in 11 seconds. It has processed 15% of all data and it will take 59 more seconds to finish.

You may stick several pv processes in between. For example, you can time how fast the data is being read from the disk and how much data is gzip outputting:

$ pv -cN source access.log | gzip | pv -cN gzip > access.log.gz
source:  760MB 0:00:15 [37.4MB/s] [=>     ] 19% ETA 0:01:02
  gzip: 34.5MB 0:00:15 [1.74MB/s] [  <=>  ]

Here we specified the “-N” parameter to pv to create a named stream. The “-c” parameter makes sure the output is not garbaged by one pv process writing over the other.

This example shows that “access.log” file is being read at a speed of 37.4MB/s but gzip is writing data at only 1.74MB/s. We can immediately calculate the compression rate. It’s 37.4/1.74 = 21x!

Notice how the gzip does not include how much data is left or how fast it will finish. It’s because the pv process after gzip has no idea how much data gzip will produce (it’s just outputting compressed data from input stream). The first pv process, however, knows how much data is left, because it’s reading it.

Another similar example would be to pack the whole directory of files into a compressed tarball:

$ tar -czf - . | pv > out.tgz
 117MB 0:00:55 [2.7MB/s] [>         ]

In this example pv shows just the output rate of “tar -czf” command. Not very interesting and it does not provide information about how much data is left. We need to provide the total size of data we are tarring to pv, it’s done this way:

$ tar -cf - . | pv -s $(du -sb . | awk '{print $1}') | gzip > out.tgz
 253MB 0:00:05 [46.7MB/s] [>     ]  1% ETA 0:04:49

What happens here is we tell tar to create “-c” an archive of all files in current dir “.” (recursively) and output the data to stdout “-f -”. Next we specify the size “-s” to pv of all files in current dir. The “du -sb . | awk ‘{print $1}’” returns number of bytes in current dir, and it gets fed as “-s” parameter to pv. Next we gzip the whole content and output the result to out.tgz file. This way “pv” knows how much data is still left to be processed and shows us that it will take yet another 4 mins 49 secs to finish.

Another fine example is copying large amounts of data over network by using help of “nc” utility that I will write about some other time.

Suppose you have two computers A and B. You want to transfer a directory from A to B very quickly. The fastest way is to use tar and nc, and time the operation with pv.

# on computer A, with IP address 192.168.1.100
$ tar -cf - /path/to/dir | pv | nc -l -p 6666 -q 5

# on computer B
$ nc 192.168.1.100 6666 | pv | tar -xf -

That’s it. All the files in /path/to/dir on computer A will get transferred to computer B, and you’ll be able to see how fast the operation is going.

If you want the progress bar, you have to do the “pv -s $(…)” trick from the previous example (only on computer A).

Another funny example is by my blog reader alexandru. He shows how to time how fast the computer reads from /dev/zero:

$ pv /dev/zero > /dev/null
 157GB 0:00:38 [4,17GB/s]

That’s about it. I hope you enjoyed my examples and learned something new. I love explaining things and teaching!

How to install pv?

If you’re on Debian or Debian based system such as Ubuntu do the following:

$ sudo aptitude install pv

If you’re on Fedora or Fedora based system such as CentOS do:

$ sudo yum install pv

If you’re on Slackware, go to pv homepage, download the pv-version.tar.gz archive and do:

$ tar -zxf pv-version.tar.gz
$ cd pv-version
$ ./configure && sudo make install

If you’re a Mac user:

$ sudo port install pv

If you’re OpenSolaris user:

$ pfexec pkg install pv

If you’re a Windows user on Cygwin:

$ ./configure
$ export DESTDIR=/cygdrive/c/cygwin
$ make
$ make install

The manual of the utility can be found here man pv.

Have fun measuring your pipes with pv, and until next time!

A question to my readers: what other not so well known Unix utilities do you use and/or know about?

These algorithms require a thorough understanding of graphs. See the previous lecture for a good review of graphs.

Lecture seventeen focuses on the single-source shortest-paths problem: Given a graph G = (V, E), we want to find a shortest path from a given source vertex s ∈ V to each vertex v ∈ V. In this lecture the weights of edges are restricted to be positive which leads it to Dijkstra’s algorithm and in a special case when all edges have unit weight to Breadth-first search algorithm.

Lecture eighteen also focuses on the same single-source shortest-paths problem, but allows edges to be negative. In this case a negative-weight cycles may exist and Dijkstra’s algorithm would no longer work and would produce incorrect results. Bellman-Ford algorithm therefore is introduced that runs slower than Dijkstra’s but detects negative cycles. As a corollary it is shown that Bellman-Ford solves Linear Programming problems with constraints in form x_j - x_i <= w_ij.

Lecture nineteen focuses on the all-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can be solved faster with Floyd-Warshall algorithm or Johnson’s algorithm.

Lecture 17: Shortest Paths I: Single-Source Shortest Paths and Dijkstra’s Algorithm

Lecture seventeen starts with a small review of paths and shortest paths.

It reminds that given a graph G = (V, E, w), where V is a set of vertices, E is a set of edges and w is weight function that maps edges to real-valued weights, a path p from a vertex u to a vertex v in this graph is a sequence of vertices (v₀, v₁, …, v_k) such that u = v₀, v = v_k and (v_i-1, v_i) ∈ E. The weight w(p) of this path is a sum of weights over all edges = w(v₀, v₁) + w(v₁, v₂) + … + w(v_k-1, v_k). It also reminds that a shortest path from u to v is the path with minimum weight of all paths from u to v, and that a shortest path in a graph might not exist if it contains a negative weight cycle.

The lecture then notes that shortest paths exhibit the optimal substructure property - a subpath of a shortest path is also a shortest path. The proof of this property is given by cut and paste argument. If you remember from previous two lectures on dynamic programming and greedy algorithms, an optimal substructure property suggests that these two techniques could be applied to solve the problem efficiently. Indeed, applying the greedy idea, Dijkstra’s algorithm emerges.

Here is a somewhat precise definition of single-source shortest paths problem with non-negative edge weights: Given a graph G = (V, E), and a starting vertex s ∈ V, find shortest-path weights for all vertices v ∈ V.

Here is the greedy idea of Dijkstra’s algorithm:

• 1. Maintain a set S of vertices whose shortest-path from s are known (s ∈ S initially).
• 2. At each step add vertex v from the set V-S to the set S. Choose v that has minimal distance from s (be greedy).
• 3. Update the distance estimates of vertices adjacent to v.

I have also posted a video interview with Edsger Dijkstra - Edsger Dijkstra: Discipline in Thought, please take a look if you want to see how Dijkstra looked like.

The lecture continues with an example of running Dijkstra’s algorithm on a non-trivial graph. It also introduces to a concept of a shortest path tree - a tree that is formed by edges that were last relaxed in each iteration (hard to explain in English, see lecture at 43:40).

The other half of lecture is devoted to three correctness arguments of Dijkstra’s algorithm. The first one proves that relaxation never makes a mistake. The second proves that relaxation always makes the right greedy choice. And the third proves that when algorithm terminates the results are correct.

At the final minutes of lecture, running time of Dijkstra’s algorithm is analyzed. Turns out that the running time depends on what data structure is used for maintaining the priority queue of the set V-S (step 2). If we use an array, the running time is O(V²), if we use binary heap, it’s O(E·lg(V)) and if we use Fibonacci heap, it’s O(E + V·lg(V)).

Finally a special case of weighted graphs is considered when all weights are unit weights. In this case a single-source shortest-paths problem can be solved by a the Breadth-first search (BFS) algorithm that is actually a simpler version of Dijkstra’s algorithm with priority queue replaced by a FIFO! The running time of BFS is O(V+E).

You’re welcome to watch lecture seventeen:

Topics covered in lecture seventeen:

• [01:40] Review of paths.
• [03:15] Edge weight functions.
• [03:30] Example of a path, its edge weights, and weight of the path.
• [04:22] Review of shortest-paths.
• [05:15] Shortest-path weight.
• [06:30] Negative edge weights.
• [10:55] Optimal substructure of a shortest path.
• [11:50] Proof of optimal substructure property: cut and paste.
• [14:23] Triangle inequality.
• [15:15] Geometric proof of triangle inequality.
• [16:30] Single-source shortest paths problem.
• [18:32] Restricted single-source shortest paths problem: all edge weights positive or zero.
• [19:35] Greedy idea for ss shortest paths.
• [26:40] Dijkstra’s algorithm.
• [35:30] Example of Dijkstra’s algorithm.
• [43:40] Shortest path trees.
• [45:12] Correctness of Dijkstra’s algorithm: why relaxation never makes mistake.
• [53:55] Correctness of Dijkstra’s algorithm: why relaxation makes progress.
• [01:01:00] Correctness of Dijkstra’s algorithm: why it gives correct answer when it terminates.
• [01:15:40] Running time of Dijkstra’s algorithm.
• [01:18:40] Running time depending on using array O(V^2), binary heap O(E·lg(V)) and Fibonacci heap O(E + V·lg(V)) for priority queue.
• [01:20:00] Unweighted graphs.
• [01:20:40] Breadth-First Search (BFS) algorithm.
• [01:23:23] Running time of BFS: O(V+E).

Lecture seventeen notes:

Lecture 17, page 1 of 2: paths, shortest paths, negative edge weights, optimal substructure, triangle inequality, single-source shortest paths, dijkstra’s algorithm.

Lecture 17, page 2 of 2: example of dijkstra’s algorithm, correctness of dijkstra’s algorithm, running time of dijkstra, unweighted graphs, breadth first search (bfs).

Lecture 18: Shortest Paths II: Bellman-Ford Algorithm

Lecture eighteen begins with recalling that if a graph contains a negative weight cycle, then a shortest path may not exist and gives a geometric illustration of this fact.

Right after this fact, it jumps to Bellman-Ford algorithm. The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w: E → R, the Bellman-Ford algorithm produces the shortest paths from s and their weights, if there is no negative weight cycle, and it produces no answer if there is a negative weight cycle.

The algorithm uses relaxation, progressively decreasing an estimate on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight.

The running time of Bellman-Ford algorithm is O(VE). The lecture also gives a correctness proof of Bellman-Ford algorithm.

The other half of the lecture is devoted to a problem that can be effectively solved by Bellman-Ford. It’s called the linear feasibility problem that it is a special case of linear programming (LP) problem, where there is no objective but the constraints are in form x_i <= w_ij. It is noted that Bellman-Ford is actually a simple case of LP problem.

The lecture ends with an application of Bellman-Ford to solving a special case of VLSI layout problem in 1 dimension.

You’re welcome to watch lecture eighteen:

Topics covered in lecture eighteen:

• [00:20] A long, long time ago… in a galaxy far, far away…
• [00:40] Quick review of previous lecture - Dijkstra’s algorithm, non-negative edge weights.
• [01:40] Description of Bellman-Ford algorithm.
• [04:30] Bellman-Ford algorithm.
• [08:50] Running time of Bellman-Ford O(VE).
• [10:05] Example of Bellmen-Ford algorithm.
• [18:40] Correctness of Bellman-Ford algorithm:
• [36:30] Linear programming (LP).
• [42:48] Efficient algorithms for solving LPs: simplex algorithm (exponential in worst case, but practical), ellipsoid algorithm (polynomial time, impractical), interior point methods (polynomial), random sampling (brand new, discovered at MIT).
• [45:58] Linear feasibility problem - LP with no objective.
• [47:30] Difference constraints - constraints in form x_j - x_i <= w_ij.
• [49:50] Example of difference constraints.
• [51:04] Constraint graph.
• [54:05] Theorem: Negative weight cycle in constraint means difference constraints are infeasible/unsatisfiable.
• [54:50] Proof.
• [59:15] Theorem: If no negative weight cycle then satisfiable.
• [01:00:23] Proof.
• [01:08:20] Corollary: Bellman-Ford solves a system of of m difference constraints on n variables in O(mn) time.
• [01:12:30] VLSI Layout problem solved by Bellman-Ford.

Lecture eighteen notes:

Lecture 18, page 1 of 2: bellman-ford algorithm, correctness of bellman-ford, linear programming.

Lecture 18, page 2 of 2: feasibility problem, bellman-ford and difference constraints, vlsi layouts.

Lecture 19: Shortest Paths III: All-Pairs Shortest Paths and Floyd-Warshall Algorithm

Lecture nineteen starts with a quick review of lectures seventeen and eighteen. It reminds the running times of various single-source shortest path algorithms, and mentions that in case of a directed acyclic graphs (which was not covered in previous lectures), you can run topological sort and 1 round of Bellman-Ford that makes it find single-source shortest paths in linear time (for graphs) in O(V+E).

The lecture continues all-pairs shortest paths problem, where we want to know the shortest path between every pair of vertices.

A naive approach to this problem is run single-source shortest path from each vertex. For example, on an unweighted graph we’d run BFS algorithm |V| times that would give O(VE) running time. On a non-negative edge weight graph it would be |V| times Dijkstra’s algorithm, giving O(VE + V²lg(V)) time. And in general case we’d run Bellman-Ford |V| times that would make the algorithm run in O(V²E) time.

The lecture continues with a precise definition of all-pairs shortest paths problem: given a directed graph, find an NxN matrix (N = |V|), where each entry a_ij is the shortest path from vertex i to vertex j.

In general case, if the graph has negative edges and it’s dense, the best we can do so far is run Bellman-Ford |V| times. Recalling that E = O(V²) in a dense graph, the running time is O(V²E) = O(V⁴) - hypercubed in number of vertices = slow.

Lecture then proceeds with a dynamic programming algorithm without knowing if it will be faster or not. It’s too complicated to explain here, and I recommend watching lecture at 11:54 to understand it. Turns out this dynamic programming algorithm does not give a performance boost and is still O(V⁴), but it gives some wicked ideas.

The most wicked idea is to connect matrix multiplication with the dynamic programming recurrence and using repeated squaring to beat O(V⁴). This craziness gives O(V³lgV) time that is an improvement. Please see 23:40 in the lecture for full explanation.

After all this the lecture arrives at Floyd-Warshall algorithm that finds all-pairs shortest paths in O(V³). The algorithm is derived from a recurrence that the shortest path from vertex i to vertex j is minimum of { shortest path from i to j directly or shortest path from i to k and shortest path from k to j }.

Finally the lecture explains Johnson’s algorithm that runs in O(VE + V²log(V)) time for sparse graphs. The key idea in this algorithm is to reweigh all edges so that they are all positive, then run Dijkstra from each vertex and finally undo the reweighing.

It turns out, however, that to find the function for reweighing all edges, a set of difference constraints need to be satisfied. It makes us first run Bellman-Ford to solve these constraints.

Reweighing takes O(EV) time, running Dijkstra on each vertex takes O(VE + V²lgV) and undoing reweighing takes O(V²) time. Of these terms O(VE + V²lgV) dominates and defines algorithm’s running time (for dense it’s still O(V³).

You’re welcome to watch lecture nineteen:

Topics covered in lecture nineteen:

• [01:00] Review of single-source shortest path algorithms.
• [04:45] All-pairs shortest paths by running single-source shortest path algorithms from each vertex.
• [05:35] Unweighted edges: |V|xBFS = O(VE).
• [06:35] Nonnegative edge weights: |V|xDijkstra = O(VE + V²lg(V)).
• [07:40] General case: |V|xBellman-Ford = O(V²E).
• [09:10] Formal definition of all-pairs shortest paths problem.
• [11:08] |V|xBellman-Ford for dense graphs (E = O(V²)) is O(V⁴).
• [11:54] Trying to beat O(V⁴) with dynamic programming.
• [19:30] Dynamic programming algorithm, still O(V⁴).
• [23:40] A better algorithm via wicked analogy with matrix multiplication. Running time: O(V³lg(V)).
• [37:45] Floyd-Warshall algorithm. Runs in O(V³).
• [47:35] Transitive closure problem of directed graphs.
• [53:30] Johnson’s algorithm. Runs in O(VE + V²log(V))

Lecture nineteen notes:

Lecture 19, page 1 of 2: all-pairs shortest paths, dynamic programming algorithm, matrix multiplication analogy.

Lecture 19, page 2 of 2: floyd-warshall algorithm, transitive closure problem, johnson’s algorithn.

Have fun with shortest path algorithms! The next post is going to be an introduction to parallel algorithms - things like dynamic multithreading, scheduling and multithreaded algorithms.

PS. This course is taught from the CLRS book (also called “Introduction to Algorithms”). Chapters 24 and 25, called “Single-Source Shortest Paths” and “All-Pairs Shortest Paths” explain everything I wrote about here in much more detail. If these topics excite you, you may want to buy this awesome book:

Similarly to famous Awk one-liners, sed one-liners are short and concise sed programs that span less than one terminal line. They were written by Eric Pement and are floating around on the Internet as ‘sed1line.txt‘ file.

If you are intrigued by this article series, I suggest that you subscribe to my posts!

Eric’s sed one-liners are divided into several sections:

• 1. File spacing (explained in part one).
• 2. Numbering (explained in part one).
• 3. Text conversion and substitution (explained in part one).
• 4. Selective printing of certain lines (explained in part two).
• 5. Selective deletion of certain lines (explained in this part).
• 6. Special applications (explained in this part).

Grab my “sed cheat sheet” and a local copy of sed1line.txt file, and let the explanation begin!

5. Selective Deletion of Certain Lines

68. Print all lines in the file except a section between two regular expressions.

sed '/Iowa/,/Montana/d'

This one-liner continues where the previous left off. One-liner #67 used the range match “/start/,/finish/” to print lines between two regular expressions (inclusive). This one-liner, on the other hand, deletes lines between two regular expressions and prints all the lines outside this range. Just to remind you, a range “/start/,/finish/” matches all lines starting from the first line that matches a regular expression “/start/” to the first line that matches a regular expression “/finish/”. In this particular one-liner the “d”, delete, command is applied to these lines. The delete command prevents the matching lines from ever seeing the light.

For example, suppose your input to this one-liner was:

Florida
Iowa
New York
San Jose
Montana
Texas
Fairbanks

Then after the sed program has finished running, the output is:

Florida
Texas
Fairbanks

We see this output because the lines from Iowa to Montana matched the “/Iowa/,/Montana/” range match (i put the matched lines in bold) and were deleted.

69. Delete duplicate, consecutive lines from a file (emulates “uniq”).

sed '$!N; /^\(.*\)\n\1$/!P; D'

This one-liner acts as the “uniq” Unix utility. So how does it work? First of all, for every line that is not the very last line of input, sed appends the next line to the pattern space by the “N” command. The “N” command is restricted to all but the last line by “$!” restriction pattern. The newly appended line is separated from the previous line by the “\n” character. Next, the pattern space is matched against “/^\(.*\)\n\1$/” regular expression. This regular expression captures the previous line up to “\n” character and saves it in the match group “\1″. Then it tests if the newly appended line is the same as the previous one. If it is not, the “P” gets executed. If it is, the “P” command does not get executed. The “P” command prints everything in the pattern space up to the first “\n” character. Next the “D” command executes and deletes everything up to the first “\n” char, leaving only the newly read line in pattern space. It also forces the sed script to begin from the first command.

This way it loops over all lines, comparing two consecutive lines. If they are equal, the first line gets deleted, and a new line gets appended to what’s left. If they are not equal, the first one gets deleted, and deleted.

I think it’s hard to understand what is going on from this description. I’ll illustrate it with an example. Suppose this is the input:

foo
foo
foo
bar
bar
baz

The first thing sed does is it reads the first line of input in pattern space. The pattern space now contains “foo”. Now the “N” command executed. The pattern space now contains “foo\nfoo”. Next the pattern space is tested against “/^\(.*\)\n\1$/” regular expression. This regular expression matches because “\(.*\)” is “foo” and “/^\(.*\)\n\1$/” is “foo\nfoo”, exactly what we have in the pattern space. As it matched, the “P” command does not get executed. Now the “D” command executes, deleting the everything up to first “\n” from pattern space. The pattern space now contains just “foo”. The “D” command forces sed to start from the first command. Now the “N” is executed again, the pattern space now contains “foo\nfoo” again and the same thing happens, “P” does not get executed and “D” deletes the first “foo”, leaving the pattern space with just “foo” in it. Now the “N” gets executed once again, this time “bar” gets appended to pattern space. It contains “foo\nbar” now. The regular expression “/^\(.*\)\n\1$/” does not match and “P” gets executed, printing “foo”. After that “D” gets executed wiping “foo” from pattern space. The pattern space now contains “bar”. The commands restart and “N” gets executed, it appends the next “bar” to current pattern space. Now it contains “bar\nbar”. Just like with “foo\nfoo”, nothing gets printed, and “D” deletes the first “bar”, leaving pattern space with “bar”. The one-liner restarts its execution. Now “N” reads in the final line “baz”. The pattern space contains “bar\nbaz” which does not match the regular expression. The “P” prints out the “bar” and “D” deletes “bar”. Now “N” does not get executed because we are at the last line of input. The “$!N” restricts “N” to all lines but last. At this moment pattern space contains only the last “baz”, the regular expression does not match, so “baz” gets printed. The “D” command executes, emptying the pattern space. There is no more input and sed quits.

The output for this example is:

foo
bar
baz

I think this is one of the most detailed explanations I have written about a single one liner.

70. Delete duplicate, nonconsecutive lines from a file.

sed -n 'G; s/\n/&&/; /^\([ -~]*\n\).*\n\1/d; s/\n//; h; P'

This is a very tricky one-liner. It stores the unique lines in hold buffer and at each newly read line, tests if the new line already is in the hold buffer. If it is, then the new line is purged. If it’s not, then it’s saved in hold buffer for future tests and printed.

A more detailed description - at each line this one-liner appends the contents of hold buffer to pattern space with “G” command. The appended string gets separated from the existing contents of pattern space by “\n” character. Next, a substitution is made to that substitutes the “\n” character with two “\n\n”. The substitute command “s/\n/&&/” does that. The “&” means the matched string. As the matched string was “\n”, then “&&” is two copies of it “\n\n”. Next, a test “/^\([ -~]*\n\).*\n\1/” is done to see if the contents of group capture group 1 is repeated. The capture group 1 is all the characters from space ” ” to “~” (which include all printable chars). The “[ -~]*” matches that. Replacing one “\n” with two was the key idea here. As “\([ -~]*\n\)” is greedy (matches as much as possible), the double newline makes sure that it matches as little text as possible. If the test is successful, the current input line was already seen and “d” purges the whole pattern space and starts script execution from the beginning. If the test was not successful, the doubled “\n\n” gets replaced with a single “\n” by “s/\n//” command. Then “h” copies the whole string to hold buffer, and “P” prints the new line.

71. Delete all lines except duplicate consecutive lines (emulates “uniq -d”).

sed '$!N; s/^\(.*\)\n\1$/\1/; t; D'

This sed one-liner prints only the duplicate lines. This sed one-liner starts with reading in the next line from input with the “N” command. As I already mentioned, the current line and the next get separated by “\n” character after “N” executes. This one-liner also restrics “N” to all lines but last with “$!” restriction. Now a substitution “s/^\(.*\)\n\1$/\1/” is tried. Similarly to one-liner #69, this substitution replaces two repeating strings with one. For example, a string “foo\nfoo” gets replaced with just “foo”. Now, if this substitution was successful (there was a repeated string), the “t” command takes the script to the end where the current pattern space gets printed automatically. If the substitution was not successful, “D” executes, deleting the non-repeated string. The cycle continues and this way only the duplicate lines get printed once.

Let’s take a look at an example. Suppose the input is:

foo
foo
bar
baz

This one-liner reads the first line and immediately executes the “N” command. The pattern space now is “foo\nfoo”. The substitution “s/^\(.*\)\n\1$/\1/” is tried and it’s successful, because “foo” is repeated twice. The pattern space now contains just a single “foo”. As the substitution was successful, “t” command branches to the end of the script. At this moment “foo” gets printed. Now the cycle repeats. Sed reads in “bar”, the “N” command appends “baz” to “bar”. The pattern space now is “bar\nbaz”. The substitution is tried, but it’s not successful, as “bar” is not repeated. As the substitution failed, “t” does nothing and “D” executes, deleting “bar” from pattern space. The pattern space is left with single “baz”. Command “N” no longer executes as we reached end of file, substitution fails, “t” fails, and “D” deletes the “baz”.

The end result is:

foo

Just as we expected - only the duplicate line got printed.

72. Delete the first 10 lines of a file.

sed '1,10d'

This one-liner restricts the “d” command to a range of lines by number. The “1,10″ means a range matching lines 1 to 10 inclusive. On each of the lines the “d” command gets executed. It deletes the current pattern space, and restarts the commands from beginning. The default action for lines > 10 is to print the line.

73. Delete the last line of a file.

sed '$d'

This one-liner restricts the “d” command to the last line of file. It’s done by specifying the special char “$” as the line to match. It matches only the last line. The last line gets deleted, but the others get printed implicitly.

74. Delete the last 2 lines of a file.

sed 'N;$!P;$!D;$d'

This one-liner always keeps two lines in the pattern space. At the very last line, it just does not output these last two. All the others before last two get output implicitly. Let’s see how it does it. As soon as sed reads the first line of input in pattern space, it executes the first command “N”. It places the 2nd line of input in pattern space. The next two commands “$!P” and “$!D” print the first part of pattern space up to newline character, and delete this part from pattern space. They keep doing it until the very last line gets appended to pattern space by “N” command. At this moment the last two lines are in pattern space and “$d” executes, deleting them both. That’s it. Last two lines got deleted.

If there is just one line of data, then it outputs it.

75. Delete the last 10 lines of a file.

sed -e :a -e '$d;N;2,10ba' -e 'P;D'

This is really straight forward one-liner. It always keeps 10 lines in pattern-space, by appending each new input line with “N”, and deleting the 11th excessive line with “D”. Once the end of file is reached, it “d” the whole pattern space, deleting the last 10 lines.

sed -n -e :a -e '1,10!{P;N;D;};N;ba'

This is also a straight forward one-liner. For the lines that are not 1-10, it appends them to pattern space with “N”. For lines > 10, it prints the first line in pattern space with “P”, appends another line with “N” and deletes the printed line with “D”. The “D” command causes sed to branch to the beginning of script! The “N;ba” at the end never, ever gets executed again for lines > 10. It keeps looping this way “P”, “N”, “D”, always keeping 10 lines in pattern space and printing line-10 on each cycle. The “N” command causes script to quit if it tries to read past end of file.

76. Delete every 8th line.

gsed '0~8d'

This one-liner only works with GNU Sed only. It uses a special address range match “first~step” that matches every step‘th line starting with the first. In this one-liner first is 0 and step is 8. Zero is not a valid physical line number, so the very first line of input does not match. The first line to match is 8th, then 16th, then 24th, etc. Each line that matches is deleted by “d” command.

sed 'n;n;n;n;n;n;n;d;'

This is a portable version. The “n” command prints the current pattern space, empties it, and reads in the next line. It does so for every 7 lines, and 8th line gets deleted with “d”. This process continues until all input has been processed.

77. Delete lines that match regular expression pattern.

sed '/pattern/d'

This one-liner executes the “d” command on all lines that match “/pattern/”. The “d” command deletes the line and skips to the next line.

78. Delete all blank lines in a file (emulates “grep ‘.’”.

sed '/^$/d'

The regular expression “/^$/” in this one-liner tests if the beginning of line matches the end of the line. Only the empty lines have this property and sed deletes them.

Another way to do the same is:

sed '/./!d'

This one-liner tests if the line matches at least one character. The dot “.” in the regular expression matches any character. An empty line does not have any characters and it does not match this regular expression. Sed deletes all the lines that do not match this regular expression.

79. Delete all consecutive blank lines from a file (emulates “cat -s”).

sed '/./,/^$/!d'

This one-liner leaves one blank line at the end of the file, if there are multiple blanks at the end. Other than that, all consecutive blanks are stripped.

It uses an inverse range match “/start/,/finish/!” to “d” delete lines from first blank line, to first non-blank, non-inclusive.

sed '/^$/N;/\n$/D'

This one-liner leaves one blank line at the beginning and end of the file, if there are multiple blanks at both sides. Other than that, all consecutive blanks are stripped.

The consecutive empty lines get appended in pattern space by “/^$/N” command. The “/\n$/D” command matches and deletes blanks until only 1 is left. At that moment it no longer matches, and the line is output.

80. Delete all consecutive blank lines from a file except the first two.

sed '/^$/N;/\n$/N;//D'

In case of > 2 blank lines, this one-liner trims them down to two. There is a catch to this one-liner. Let me explain it first. See the last command “//D”? It’s a shortcut for “/previous-match/D”. In this case it’s shortcut for “/\n$/D”. Alright, now the one-liner itself. On every empty line, it appends the next to current pattern space with “/^$/N” command. Next it tests if the line just read in was actually a blank line with “/\n$/”, if it is, it reads another line in with “N”. At this moment it repeats the same test “/\n$/”. If the line was a blank one again, it deletes the first blank line and restarts sed script from the beginning. Notice that at all times only 2 consecutive blank lines are in pattern space. This way any number of blank lines get deleted and only two are left.

81. Delete all leading blank lines at the top of a file.

sed '/./,$!d'

This one-liner inverts a match “match from the first non-blank line to end of file”. It becomes “match from the beginning of file to last blank line”.

82. Delete all trailing blank lines at the end of a file.

sed -e :a -e '/^\n*$/{$d;N;ba' -e '}'

This one-liner accumulates blank lines in pattern space until it either hits end or hits a non-blank line. If it hits end, “$d” deletes the whole pattern space (which contained just the trailing blank lines) and quits. If however, it hits non-blank line, the whole pattern space gets printed implicitly and script continues as if nothing had happened.

This one is a portable version.

gsed -e :a -e '/^\n*$/N;/\n$/ba'

This is the same script, except a shorter version, made to work with Gnu Sed.

83. Delete the last line of each paragraph.

sed -n '/^$/{p;h;};/./{x;/./p;}'

This one-liner always keeps the previous line in hold buffer. It’s accomplished by 2nd block of commands “/./{x;/./p;}”. In this block, the pattern space (1 line) gets exchanged with hold buffer (1 line) by “x” command and if the hold buffer was not empty, it gets printed by “p”. The next moment to note is what happens on the first empty line. That is the line after the paragraph. At this moment “/^$/{p;h;}” gets executed, that prints the blank line (but does not print the last line of paragraph!), and puts the blank line in hold buffer. Once a new paragraph is reached, the script executed just like it was the very first paragraph of the input.

6. Special Sed Applications

84. Remove nroff overstrikes.

Nroff overstrikes are chars that are formatted to stand out in bold. They are achieved like in old typewriters, where you would do backspace and hit the same key again. In nroff it’s key CHAR, CTRL+H, CHAR. This one-liner deletes the CHAR, CTRL+H, leaving just plain CHAR.

sed 's/.^H//g'

Press Ctrl+V and then Ctrl+H to insert ^H literally in sed one-liner. It then uses the substitute command to delete any char “.” followed by CTRL+H “^H”.

Another way to do the same is use a hex escape expression that works in most recent seds:

sed 's/.\x08//g'

Yet another way is to use “echo” and enable interpretation of backslashed characters:

sed 's/.'`echo -e "\b"`'//g'

85. Print Usenet/HTTP/Email message header.

gsed -r '/^\r?$/q'

Usenet, HTTP and Email headers are similar. They are a bunch of text lines, separated from the body of the message with two new lines “\r\n\r\n”. Some implementations might even go with just “\n\n”. This one-liner quits on the first line that is either empty or contains “\r”. In other words, it prints the message header and quits.

86. Print Usenet/HTTP/Email message body.

sed '1,/^$/d'

This one-liner uses a range match “1,/^$/” to delete lines starting from 1st, and ending with the first blank line (inclusive). As I explained in the previous one-liner #78 above, “/^$/” matches empty lines. All the lines before first blank line in a Usenet/Email message or a HTTP header are message headers. They get deleted.

87. Extract subject from an email message.

sed '/^Subject: */!d; s///; q'

This one-liner deletes all lines that do not match “^Subject: “. Then it re-uses the match in “s///” to delete “Subject: ” part from the line, leaving just the real subject. Please notice how “s///” is equivalent to “s/previous-match//”, where “previous-match” is “^Subject: *” in this one-liner.

88. Extract sender information from an email message.

sed '/^From: */!d; s///; q'

This one liner is equivalent to the previous one, except it prints sender information from email.

89. Extract email address from a “Name Surname <email@domain.com>” string.

sed 's/.*< *//;s/ *>.*//;

This one-liner strips all symbols before < symbol (and any whitespace after it), and stips all symbols after > symbol (including whitespace before it). That’s it. What’s left is email@domain.com.

90. Add a leading angle bracket and space to each line (quote an email message).

sed 's/^/> /'

This one-liner substitutes zero-width anchor “^” that matches beginning of line with “> “. As it’s a zero-width anchor, the result is that “> ” gets added to beginning of each line.

91. Delete leading angle bracket from each line (unquote an email message).

sed 's/^> //'

It does what it says, deletes two characters “>” and a space ” ” from the beginning of each line.

92. Strip HTML tags.

sed -e :a -e 's/<[^>]*>//g;/</N;//ba'

Sed is not made for parsing HTML. This is a very crude version of HTML tag eraser. It starts by creating a branch label named “a”. Then on each line it substitutes “<[^>]*>” with nothing as many times as possible (”g” flag for s/// command). The “<[^>]*>” expression means match match symbol “<” followed by any other symbols that are not “>”, and that ends with “>”. This is a common pattern in regular expressions for non-greediness. Next, the one-liner tests if there are any open tags left on the line, if there are “N” reads the next line of input to make it work across multiple lines. “//ba” finally branches to the beginning of the script (it’s short for “/previous-expression/ba” which in this case is “/</ba”).

Have Fun!

This post completes the three part article on the superman of Unix stream editing. I hope that you learned a thing or two and it was my pleasure explaining them.

Just as with the three part article on famous Awk one-liners explained, my plans are to create a ‘awk1line-explained.txt‘ file that will be supplementary to ‘awk1line.txt’, and publish an ebook in pdf format.

If you have any comments on the one-liners, please let me know in the comments. Thanks!

I first read about this idea from my most favorite personal development blog at Steve Pavlina.com. In his post “Overclock Your Audio Learning” he says that he occasionally listens to audios at 4.1x. At this speed 4 hour video/audio can be listened in less 1 hour!

I personally found it impossible to understand anything at 4x speed. My optimal listening speed is 1.65x - 2.1x.

To speed up the videos you will first need to download and install AviSynth. AviSynth is kind of a video programming language with which you can do all kinds of manipulations to videos programmatically. If you are on Windows, then during the installation make sure to associate .avs file extension with Windows Media Player and not Notepad.

Next, create this AviSynth script, and place it in the same directory as your video. Name the script as “speedup.avs” or something similar. Make sure the extension is “.avs” if you are on Windows!

file = "file_name_of_video.avi"
speedup = 1.65
pitch = 100

DirectShowSource(file)

audio_rate = last.audiorate
video_rate = last.framerate

AssumeSampleRate(int(audio_rate*speedup))
AssumeFPS(video_rate*speedup)
TimeStretch(pitch = pitch)

There are three variables that you can change in this simple script. The first is “file“. It should be the filename of the video you are about to watch. The next is “speedup“. It’s the new playback rate, you may set it to any value you wish. For example, if you set it to 2.0, then the video will play twice as fast as it normally would. And the last parameter to change is the “pitch“. You may change it to something lower than 100 when the video plays at higher speeds to make the speaker sound lower. I usually keep “speedup” at 1.65 and “pitch” at 75.

Once you have made your own configuration, just double click the .avs on Windows to play it at the new playback speed, or play it through mplayer on Linux!

Update: My blog readers bobb and crb suggested two new techniques on how to watch videos faster. Bobb suggested just to use mplayer. Turns out it already has an option to play videos faster!

mplayer -speed 1.65 file.avi

# use keys [ ], and { } to control the playback speed
# use backspace to reset video speed to normal.

Crb suggested to use MySpeed™ Plug-In for YouTube to speed up video on YouTube in real time.

Here are a few examples that I crafted at speeds 1x, 1.4x, 1.65x, 2x, 2.25x, 2.5x, 2.75x and 3x. They are from Alan Kay’s keynote speech “The computer revolution hasn’t happend yet” at OOPSLA Conference in 1997.

After a few minutes of listening at higher speeds, try going back to listen at 1x. It will seem incredibly slow because your mind will have adapted to the faster input rate.

Do you have any other techniques to speed up videos? I am also curious at what speeds do you feel the most comfortable watching the videos?

It would also be cool to create a hack that modifies youtube and google video players to make them play videos faster natively.

Ps. Did you know that I was a big fan of video lectures? I have been collecting math, physics, computer science video lectures for almost 3 years now and posting them to my other Free Science Online Blog.