読者です 読者をやめる 読者になる 読者になる

最高の気分で定時退社した(ツールがついに動いてくれた)

日記

水曜日です。


というわけで、ツールが動きました。成功体験を得たことで、最高の気分で定時退社をしました。


帰宅後はcompact bit vectorの速度改善をやりました。具体的には6bitのfixed length vectorをunsigned charのvectorに変えました。2n bitほど無駄になってしまいますが、primitiveなデータ構造であるという利点は大きく、大幅に高速化されました。

個人的にはもっと高速化したい感があるので、もうちょっといじってからrank実装に移ります。現時点で1/3のデータサイズになっているとrank/selectで補助データ構造を使ったとしてもかなりデータサイズが小さくなりそうでウキウキですね。

size of 1s: 2000
size of 0s: 499500

vector_size(naive): 15672
vector_size(compressed / fixed length vector): 4372
vector_size(compressed / unsigned char): 5888

access time(msec)(naive): 3
access time(msec)(compressed/ fixed length vector): 232
access time(msec)(compressed / unsigned char): 106

github.com


やるべきことをやったので、安心してけフ11話を見ました。すごいことになった・・・(ネタバレ配慮のためコメントはなし)。


以上です。寝ます。