gfxのブックマーク - はてなブックマーク

簡潔データ構造超入門〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。しかし有用性とは裏腹にまとまった教科書等がないこともあり入門者に対して敷居が高いようにも感じられる。そこで本記事では簡潔データ構造の基本であるビットベクトルに対する簡潔構造の実装方法をC/C++のコードを交えて解説してみる。ビットベクトルに対する簡潔構造は、単純には疎ベクトルを表現するのに利用することができる。よって本記事でも簡潔ビットベクトルを実装し、疎ベクトルを実現してみようと思う。今回は疎ベクトルとして値がint(4byte)の256次元のベクトルを考える。ただし疎ベクトルなので256次元のうちいくつかの次元にしか値が入っていないものを仮定する。例えば v[5] = 10 v[100] =
gfx 2019/02/24
algorithm

簡潔データ構造
リンク
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。「高速文字列解析」とは本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。キーワードは3つオビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
gfx 2013/01/09
algorithm
リンク
連想配列はトライでしょ的な話がでていたので入門記事を書いてみた - EchizenBlog-Zwei
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。トライ木が持つ機能最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
gfx 2012/01/24
associative

trie
リンク
PerlXS: sv_2mortal()やhv_store()のこと - EchizenBlog-Zwei
そろそろXSをちゃんとやろうと思ったので、メモリ周辺のことが良くわからなくて放置していたsv_2mortal()やhv_store()のことについて調べた。参考: perlguts http://www.kt.rim.or.jp/~kbk/perl5.005/perlguts.html 最初に結論を書いてしまうと [1: sv_2mortal()] - returnしない変数は常にsv_2mortal()を通す (揮発性をもたせる) - SVはreturnするときはsv_2mortal()を通してはダメ - AV, HVはreturnするときもsv_2mortal()を通す [2: newRV_inc()] - リファレンス変数(RV)を作るときはnewRV_inc()を使い参照カウントをインクリメントしておく (newRV_noinc()はダメ) - リファレンス変数もsv_2mor
gfx 2010/05/18
perl

xs
リンク
1