Python で Variable Byte Code を実装 その2

先日 Python で実装してみた VBCode の続き。

ここからダウンロードしたはてなのデータを実際に圧縮してみた。

準備

ダウンロードしたやつの中に入っている eid_tags.txt を使う。

$ curl -LO http://image.gihyo.co.jp/assets/files/book/2010/978-4-7741-4307-1/hugedatabook_samplecode.zip  
$ unzip hugedatabook_samplecode.zip  
$ du -h hugedatabook_samplecode/hgdata_example/06/eid_tags.txt  
172M    hugedatabook_samplecode/hgdata_example/06/eid_tags.txt  

大きさは、だいたい172MBぐらいらしい。

フォーマットは、「はてなタグ<タブ>ID,ID,ID…」的なかんじ。
こいつを適切に読みつつ、IDの部分にVBCodeを適用してやります。
はてなタグは文字列。IDは整数(4byte)。
IDは、小さい順にソートされているので、前後の差分を取ってそいつを圧縮してやると効率がよいとのこと。
本の中では、ギャップと表現されてました。
例で表すと以下のとおり。

整数列:1, 5, 10, 12, 16  
差分 :1, 4, 5, 2, 4  

実行してみた

— 圧縮 —

$ time ./chap6_vbencode.py eid_tags.txt > eid_tags.txt.vb   
real    1m37.259s  
user    1m35.743s  
sys 0m0.917s  
$ du -h  eid_tags.vb  
 40M    eid_tags.txt.vb  

— 解凍 —

$ time ./chap6_vbdecode.py eid_tags.txt.vb > eid_tags2.txt  
real    0m29.463s  
user    0m27.269s  
sys 0m0.941s  
$ diff eid_tags2.txt eid_tags.txt  

最初は圧縮するまで2分半もかかりましたが、もろもろ最適化したら1分半になりました。

でもサンプルに付属していた Perl スクリプトだと1分かからないぐらい。

この速度差はなんだろ。。。

おもむろにいろいろ測ったところ、「数値を文字列化している部分」と「pack関数周り」が怪しげだった。
その部分だけ実行するスクリプトを回してみたところ、性能に約5倍ほど差がでた。

$ cat a.py  
#!/usr/bin/env python  
from struct import pack  
for i in xrange(19997779):  
    bytes = [1, 10, 100]  
    pack('%dB' % len(bytes), *bytes)  
$ time ./a.py  
real    0m45.475s  
user    0m45.293s  
sys 0m0.075s  
---------------------------------------------  
$ cat a.pl  
#!/usr/bin/env perl  
for($i=0; $i<19997779; $i++){  
    @bytes = (1, 10, 100);  
    pack('C*', @bytes);  
}  
$ time ./a.pl  
real    0m9.943s  
user    0m9.930s  
sys 0m0.009s  

もうすこし絞りたいと、数値を文字列化している部分を直値に直したら性能差は約2倍まで縮まった。

$ cat a.py  
#!/usr/bin/env python  
from struct import pack  
for i in xrange(19997779):  
    bytes = [1, 10, 100]  
    pack('3B', *bytes)  
$ time ./a.py  
real    0m17.557s  
user    0m17.472s  
sys 0m0.023s  

しかし、直値での実装方法は不明。
packはさらに奥が深そうなので放置。
この問題は迷宮入りです。

圧縮後ファイルサイズは、約40MBになった。

172MB → 40MBなので、圧縮率23%ぐらい。凄い。

圧縮ファイルを解凍して元ファイルと差がないことを確認し、おしまいにしました。

雑感

Variable Byte Code はアルゴリズムさえ知っていれば、実装は意外と簡単だった。

作成したソースコードはgistに貼り付けた。