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[
グラフ理論ライブラリのJGraphTを使ってみた - kaisehのブログ
JGraphT JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。 無向グラフ UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>( DefaultEdge.class); g.addVertex("a"); g.addVertex("b"); g.addVertex("c"); g.addEdge("a", "b"); g.addEdge("b", "c"); System.out.println(g.vertexSet()); System.out.println(g.edgeSet()); System.out.println(g.edgesOf("c"));
DO : Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです． キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています） 特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります． 最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
