[B! C++][アルゴリズム] rti7743のブックマーク

rti7743 id:rti7743

C++とアルゴリズムに関するrti7743のブックマーク (3)

wat-array : wavelet木を利用した高速配列処理ライブラリ - Preferred Networks Research & Development
こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。 wat-arrayというC++ライブラリを公開しました。 google code:wat-array wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます． wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。例えば、 – 任意の連続した範囲内にある最大値 /最小値 / k番目に大きい値, またそれらの出現位置、頻度 – 任意の連続した範囲内にある指定した文字cの出現回数、c未満/より大きい文字の出現回数 – 任意の文字のi番目の出現位置といったものを求めることが全て範囲長、入力長に対して定数時間で行うことができます。例えば長さ10億、値の範囲が0から1000万であるような配列A中のA[
rti7743 2010/12/21
アルゴリズム

c++
リンク
LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ - EchizenBlog-Zwei
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済
rti7743 2010/10/16
こーゆー分かりやすいまとめは助かる。あえて言うなら、select() や rank() を簡単に説明しないで、手で展開させてみて、こうなりますねって説明するといいと思う。

c++

アルゴリズム
リンク
インテルTBBによる選択ソートの高速化（1/3）：CodeZine
CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。
rti7743 2010/04/19
C++

マルチスレッド

アルゴリズム

並列処理
リンク
1