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@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