Re: [boost] [algorithm] Review Request: edit_distance

Subject: Re: [boost] [algorithm] Review Request: edit_distance
From: Erik Erlandson (eje_at_[hidden])
Date: 2014-01-31 19:53:59

----- Original Message -----

> 
> - It would be great to see a benchmark against GNU diff!

So I cooked up an implementation of unix diff:
https://github.com/erikerlandson/algorithm/blob/edit_distance/sequence/example/edit_distance_diff_example.cpp

It produces standard default unix diff output:
http://en.wikipedia.org/wiki/Diff#Usage

That is to say, edit_distance_diff_example will reproduce the output of diff, at least if you just give both programs two files for arguments:

$ edit_distance_diff_example foo.txt bar.txt > ed.out
$ diff foo.txt bar.txt > diff.out
$ diff ed.out diff.out
$

I generated a few benchmarking data-sets, by editing /usr/share/dict/words.  On my machine (F18), the 'words' file has 479,828 lines (one word per line) and is 4,953,680 bytes.   So, a decent size of file in both line length and bytes.   I did a couple different experiments, where I compared against a variation that differed by around 150 lines, and then another variation that differed by around 1200 lines.   I also varied input size, by just duplicating the contents, so the result was twice the length and size.

Across these variations of input size and file difference that I tested, edit_distance_diff_example ran consistently 40% to 60% faster than unix diff.  So, roughly speaking it's performing about twice as fast.

And less than 150 lines of code!