Pablo López-García's Homepage

Donald Knuth said that premature optimization is the root of all evil. And I cannot but completely agree. Abstracting to a higher level is always better for both the code writer and especially the code reader and maintainer. It also makes you focus on the problem you are solving. Optimization can be done later, if needed.

Take a look at this simple example. Imagine you have the following text file containing a set of lines:

Hi!
How are you doing?
Fine, thanks
And you?
Good
Let's execute the code
Good idea

And now you need to build an n-gram file for each n-gram size. That is, you want a 1-grams.txt file containing all lines with 1 word, 2-grams.txt with lines with 2 words, and so on.

Here is an example of how 2-grams.txt should be:

Fine, thanks
And you?
Good idea

A Shell script and some command line utilities seem great for this kind of jobs. A possible, compact solution could be the following, where you pass the original file as the first argument:

#!/bin/sh
while read line
do
  nlen=`echo "$line" | wc -w`
  echo "$line" >> `echo $nlen | tr -d ''`-grams.txt
done < $1

You can later on use uniq or sort if you want to filter out duplicate n-grams or order the files, but the previous code solves the main problem of generating the n-gram files.

This solution, as elegant and compact as it is, however, stops being practical when the input text file is of certain size. Try with a 10MB or a 100MB text file and see what happens. How long do you think it will take? 1 second? 1 minute? 10 minutes? 1 hour? Computers are fast. Really. Just try and see how long it takes.

Are you satisfied with the performance?

The following is another equivalent solution, written in python. However, in this case the generated files won’t contain any duplicate n-gram and n-grams will appear in order.

#!/usr/bin/env python
import sys

ngrams = {}

for line in open(sys.argv[1]):
  try:
    nlen = len(line.split())
    ngrams[nlen].add(line)
  except KeyError:
    ngrams[nlen] = set()
    ngrams[nlen].add(line)

for n in ngrams:
  file = open(str(n) + '-grams.txt', "w")
  file.writelines(sorted(ngrams[n]))
  file.close()

Are you now satisfied?

If you don’t wanna test both solutions (although you should) I’ll just tell you: the first one takes hours, even for moderate file sizes (100 MB). The second one takes a few seconds. Can you explain why?

When you are working with files, be very careful about performance. If you’re not happy with it, just stop and think what’s going on beyond the stage: how often are files opened, closed or written? Although elegant and abstract solutions are excellent for understanding the problem we want to tackle and they might work for small input sizes, there might be a spot where that implementation is simply useless in practical terms.

A small change in how you tackle the problem can turn your solution from really bad to excellent in terms of performance.

In the previous post I presented a Ruby script to download and rename “El Quijote” audiobook from a site which was far from user friendly (remember there were 126 badly named, badly ID3-tagged MP3 files to download).

There was still something not solved by the script: the ID3 tags of the MP3 files. id3lib, a library to read and write ID3 tags, comes to the rescue. We can use it from Ruby thanks to the id3lib-ruby RubyGem. Note that id3lib-ruby requires id3lib installed on your system. If you are using a Macintosh with Snow Leopard, MacPorts and RubyGems, follow these instructions to install id3lib and id3lib-ruby:

sudo port install id3lib
sudo env ARCHFLAGS="-arch x86_64" gem install id3lib-ruby -- --with-opt-dir=/opt/local

Instead of modifying the small script of the previous post to add the ID3 tag fixing code, I decided to create a Rakefile (mainly a Makefile in Ruby) and use Rake. It’s nice as a learning example because each task recreates a different step: downloading the files, renaming the files and fixing the ID3 tags. You can use each of these tasks individually (e.g. rake rename) or, by default, perform them sequentially, following the logical dependencies.

Notice again that the idea here is to play with a variety of Ruby code (code blocks, regular expressions, files, call to command-line utilities…) and Rake tasks, not to be particularly efficient or smart. I hope you have fun and learn as much as I did with this example.

To run this Rakefile you will need wget, ruby, rubygems, id3lib, and id3lib-ruby. As usual, the following code is generated live from the latest version of the Rakefile available at my repository:

require 'rake'
require 'id3lib'

TOTAL_PARTS = "2"
CHAPTERS_IN_PART1 = "52"
CHAPTERS_IN_PART2 = "74"

def fix_tag(filename, part, total_parts, chapter, total_chapters_in_part)
  puts "Fixing ID3 tag of #{filename}..."
  tag = ID3Lib::Tag.new(filename)
  tag.strip!
  tag.title = "Parte #{part} - Capitulo #{chapter}"
  tag.album = "Don Quijote de la Mancha"
  tag.artist = "Miguel de Cervantes"
  tag.disc = "#{part}/#{total_parts}"
  tag.track = "#{chapter}/#{total_chapters_in_part}"
  tag.update!
end

desc "Download all files"
task :download do
  ("01"..CHAPTERS_IN_PART1).each do |chapter|
    `wget http://www.aularagon.org/files/espa/elquijote/p1/Parte%201%20Cap%C3%ADtulo-#{chapter}.mp3`
  end
  ("01"..CHAPTERS_IN_PART2).each do |chapter|
    `wget http://www.aularagon.org/files/espa/elquijote/p2/Parte%202%20Cap%C3%ADtulo-#{chapter}.mp3`
  end
end

desc "Rename files to remove accents and whitespaces"
task :rename do
  Dir.foreach(".") do |f|
    unless (m = f.match(/Parte\s(.*)\sCap.+tulo-(.*)\.mp3/)).nil?
      File.rename(f.to_s, "P" + m[1] + "-Capitulo-" + m[2] + ".mp3")
      puts "#{f.to_s}: Removed accents and whitespaces from filename"
    end
  end
end

desc "Fix ID3 tags"
task :fixid3  do
  ("01"..CHAPTERS_IN_PART1).each do |chapter|
    fix_tag("P1-Capitulo-#{chapter}.mp3", "1", TOTAL_PARTS, chapter, CHAPTERS_IN_PART1)
  end
  ("01"..CHAPTERS_IN_PART2).each do |chapter|
    fix_tag("P2-Capitulo-#{chapter}.mp3", "2", TOTAL_PARTS, chapter, CHAPTERS_IN_PART2)
  end
  puts "DONE!"
end

desc "Default: Download, rename and fix ID3 tags"
task :all => [:download, :rename, :fixid3]

task :default => [:all]