O(1)のrank実装やりました(データサイズも圧縮された)

土曜日です。


今日は来客があり(リア充っぽい)(しかし性的ではない)(性の諦め)、定型業務はお休みでした。

その後はFEエコーズを無限にやりました。楽しすぎる・・・。今回は鍛冶を活用すれば武器が豊富に得られるので、外伝のように武器不足の苦しみがなくてよいですね。育成が楽しいゲームなのでFE的ではないかも。でも楽しい・・・。


Navarro本のコード書きをやりました。compressed bit vectorのrank実装ができました。以下に数値をはりました。ベクトルの疎密によってサイズと速度が変わってくるので、あくまで参考情報です(今回は13の倍数だけbitが立ってる)(これは10倍くらい遅くなってるけど5倍くらいで収まるケースもある)。compressed bit vector + rankは普通のbit vectorよりも小さいサイズでrankが実装されています。この表だとわかりませんが、定数時間で動きます。

# bit vector #
vector size: 15625
access time(msec): 13

# compressed bit vector #
vector size: 11986
access time(msec): 257

# bit vector + rank #
vector size: 19781
access time(msec): 21
rank time(msec): 48

# compressed  bit vector + rank #
vector size: 12239
access time(msec): 254
rank time(msec): 429

github.com


社運の特番を視聴し、ロゼリアのつよさを感じました。

ツインエンジェルBREAKを見ました。男は男同士、女は女同士で恋愛する感じのあれでした。最高でした。思わずBD-BOX(20,000円)(12+12+2=26話収録でこの値段は格安)を予約しました(労の場での高評価によってマネーを得られたので円盤を購入することさえ可能となったのだ!)(長い注釈)(前職で同じくらいの圧倒的成果を出したときは報酬は1200円だった)(1200円でカレーを食べた)(美味しかった)(そういう問題ではない)(わるい社はわるいし、よい社はよい)。


以上です。寝ます。