圧縮プログラミングをやってみた

Web開発者のための大規模サービス技術入門
〜データ構造、メモリ、OS、DB、サーバ/インフラ〜

第6回で出てくる圧縮プログラミングの課題をやってみた。

vb.rb

def vb_encode(numbers)
    vbs = numbers.map do |n|
        bytes = []
        loop{
            d,m = n.divmod(128)
            bytes << m
            d > 0 ? n = d : break
        }
        bytes[0] += 128
        bytes.reverse.pack("C*")
    end
    vbs.join
end

def vb_decode(bytestream)
    numbers, num = [], 0
    bytestream.unpack("C*").each do |n| 
        d, m = n.divmod(128)
        num = 128 * num + m
        if d > 0
            numbers << num
            num = 0
        end
    end 
    numbers
 end

vb_encode.rb

require 'vb'

File::open(ARGV[0]).each do |line|
    tag, nums = line.split(/\t/)
    pre = 0
    bytes = (eval "[#{nums}]").sort.map do |num|
        num, pre = num - pre, num
        num
    end
    vb = vb_encode(bytes)
    print [tag.size, vb.size].pack('N2'), tag, vb
end

vb_decode.rb

require 'vb'

bytedata = File::open(ARGV[0])

until bytedata.eof?
    tag_len, vb_len = bytedata.read(8).unpack("N2")
    tag = bytedata.read(tag_len)
   
    pre = 0
    vbs = vb_decode(bytedata.read(vb_len)).map do |vb|
        vb += pre
        pre = vb
    end
    print tag, "\t", vbs.join(","), "\n"
end

エンコードにかかる時間が2分ぐらいかかるんで、もうちょっと改善の必要があるかなと思った。

eval使ってる部分が遅いのかと思ったけど、計測したらto_i使うよりもevalのほうが早かった。
んー、暇を見つけてやってみるかな。