簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ

2018/10/17 271 users Hackarade mametter log ＭＲＩ Ruby

技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言う... 続きを読む

文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った - EchizenBlog-Zwei

2014/03/25 39 users EchizenBlog-Zwei github.com

計算機科学@marugorithmさんの文法圧縮の解説資料(http://research.preferred.jp/2014/03/nlp2014_grammar/)があまりにも有益すぎて感動したので、文法圧縮を使った完備辞書(簡潔ビットベクトル)を作った。文法圧縮の部分は実装の簡単さからRe-Pairアルゴリズムを使った。https://github.com/echizentm/GCFID 作... 続きを読む

完備辞書（簡潔ビットベクトル）の解説 - アスペ日記

2014/02/01 66 users trie LOUDS ウェーブレット行列 アスペ日記 完備辞書

以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。この「簡潔ビットベクトル」「... 続きを読む

Javaで簡潔ビットベクトル(28) - 気ままなブログ

2013/03/17 10 users RANK select ACCESS Java log

2013-03-17 Javaで簡潔ビットベクトル(28) Java 疎なビットベクトルのaccessとrankとselectをサポートしようとして、久しぶりに実装しようとしていたら、かなり追加しにくい感じになってたので、ソースをリファクタリングして、メソッドを整理しました。定数時間のselectですが、 0のみの定数時間(1は、log(n)) 1のみの定数時間(0は、log(n)) 0と1の定数... 続きを読む