Python で Variable Byte Code を実装 その2
ここからダウンロードしたはてなのデータを実際に圧縮してみた。
準備
ダウンロードしたやつの中に入っている 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に貼り付けた。