簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。 しかし有用性とは裏腹にまとまった教科書等がないこともあり入門者に対して敷居が高いようにも感じられる。そこで本記事では簡潔データ構造の基本であるビットベクトルに対する簡潔構造の実装方法をC/C++のコードを交えて解説してみる。 ビットベクトルに対する簡潔構造は、単純には疎ベクトルを表現するのに利用することができる。よって本記事でも簡潔ビットベクトルを実装し、疎ベクトルを実現してみようと思う。 今回は疎ベクトルとして値がint(4byte)の256次元のベクトルを考える。ただし疎ベクトルなので256次元のうちいくつかの次元にしか値が入っていないものを仮定する。例えば v[5] = 10 v[100] =
Stackを使ってQueueを作る - くまメモ
有名な話かと思ったら意外と知られていなかったのでメモ。 FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。 簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。 ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。 template<typename T> class MyQueue { std::stack<T> in, out; MyQueue(){} void enqueue(const T& v) { in.push(v); } T dequeue() { if (out.empty())
max_queue 最大値をいち早く返すデータ構造 - くまメモ
ちょっとマニアックなデータ構造を紹介 その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。 兄弟分で最小の物を返すmin queueや、両方の機能を備えたmin-max queueもあるけどmax queueが判れば自明なので割愛。 最大の値を覚えておけば良いだけに思えるけど、最大の値がdequeueされてしまった場合にO(n)の時間を掛けて再び探索してたら条件を満たせない。 max-queueでは最大の値を覚えておくため専用のqueue（以後最大値queueと呼ぶ）を内部でもう一本持つ。 この青い線がqueueに入ってるデータ列で高さがデータの大きさを表す、下に書かれている薄い線の入ったデータ列が最大値queue。 こちらの最大
スプレー木 - Wikipedia
スプレー木（スプレーき、英: splay tree）は、平衡2分探索木の一種で、最近アクセスした要素に素早く再アクセスできるという特徴がある。挿入、参照、削除といった基本操作を O(log(n)) の償却時間で実行できる。多くの一様でない一連の操作において、その順序パターンが未知の場合でも、スプレー木は他の探索木よりもよい性能を示す。スプレー木はダニエル・スレイターとロバート・タージャンが発明した。 2分探索木の通常のあらゆる操作は、「スプレー操作」という1つの基本操作と組み合わせられる。スプレー操作とは、特定の要素が木の根に位置するよう再配置を行うことである。そのためには、まず通常の2分探索木での要素の探索を行い、次にその要素がトップになるように木の回転を行う。別の方法として、トップダウンアルゴリズムで探索と木の再配置を単一フェーズに統合することもできる。 長所と短所[編集] スプレー木
ダブル配列の実装方法
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
Double-Array Construction
ダブル配列は動的に更新できるデータ構造として提案されました． しかし，キーを追加するとき，衝突（ Collision ） という厄介な問題が発生します． そこでまず，キーの追加や削除を考慮せず， 登録するキーがすべて分かっている状態からの構築方法について説明します． 更新が遅いと評判のダブル配列ですが， 登録するキーの数が 10 万件くらいであれば， 1 秒以内で構築することができます． ただし，なぜか評価実験でよく使われている郵便番号のように， 網羅性の高いキー集合を対象とする場合は時間がかかります． なお，網羅性が高いという表現は，分岐数（節から出る枝の数）の平均が 大きいことを意味しています． ダブル配列を構築する前に，マルチキークイックソート （ Multikey Quicksort ） などを使用してキー集合を整列します． マルチキークイックソートは基数ソートとクイックソートを合
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
SQLで木と階層構造のデータを扱う――入れ子集合モデル