[Haskell-cafe] Need for speed: the Burrows-Wheeler Transform

[Stefan O'Rear]

On Fri, Jun 22, 2007 at 09:26:40PM +0100, Andrew Coppin wrote:
> OK, so I *started* writing a request for help, but... well I answered my 
> own question! See the bottom...
...
> Unfortunately, the resident C++ expert fails to grasp the concept of 
> "example code", and insists on comparing the efficiency of this program 
> to the C one on the website.
...
> Fact is, he's translated the presented C into C++, and it can apparently 
> transform a 145 KB file in 8 seconds using only 3 MB of RAM. The code 
...
> Woah... What the hell? I just switched to Data.ByteString.Lazy and WHAM! 
> Vast speed increases... Jeepers, I can transform 52 KB so fast I can't 
> even get to Task Manager fast enough to *check* the RAM usage! Blimey...
> 
> OK, just tried the 145 KB test file that Mr C++ used. That took 2 
> seconds + 43 MB RAM. Ouch.

Mr. C++ apparently isn't a very good C++ programmer, since his best
effort absolutely *pales* in comparison to Julian Seward's BWT:

stefan at stefans:/usr/local/src/hpaste$ head -c 135000 /usr/share/dict/words | (time bzip2 -vvv) > /dev/null
  (stdin): 
    block 1: crc = 0x25a18961, combined CRC = 0x25a18961, size = 135000
      0 work, 135000 block, ratio  0.00
      135000 in block, 107256 after MTF & 1-2 coding, 61+2 syms in use
      initial group 6, [0 .. 0], has 20930 syms (19.5%)
      initial group 5, [1 .. 1], has 4949 syms ( 4.6%)
      initial group 4, [2 .. 2], has 20579 syms (19.2%)
      initial group 3, [3 .. 4], has 17301 syms (16.1%)
      initial group 2, [5 .. 10], has 24247 syms (22.6%)
      initial group 1, [11 .. 62], has 19250 syms (17.9%)
      pass 1: size is 127140, grp uses are 339 550 192 440 12 613 
      pass 2: size is 51693, grp uses are 321 440 288 316 139 642 
      pass 3: size is 51358, grp uses are 329 387 376 304 122 628 
      pass 4: size is 51302, grp uses are 298 421 397 304 125 601 
      bytes: mapping 21, selectors 433, code lengths 110, codes 51297
    final combined CRC = 0x25a18961
    2.602:1,  3.075 bits/byte, 61.57% saved, 135000 in, 51887 out.

real	0m0.165s
user	0m0.044s
sys	0m0.012s


Yup, does slightly more work (huffman coding) in 1/200 the time :)

(Note, on my system .Lazy BWT3 takes 5.3s on the same input)

Stefan