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[
プロシージャル技術ネタに関するページ収集中 - ABAの日誌
ゲームにおける自動生成技術、いわゆるプロシージャルに関するページをいまさらのように収集している。 次世代ゲームにおける自動生成技術 (http://www.t-pot.com/program/144_GameAISeminar6/index.html) 「ゲームAI連続セミナー第6回」のレポート記事。プロシージャルに関する概観をつかむのに良い記事。 Procedural generation (wikipedia:en:Procedural_generation) WikipediaのProcedural generation項。プロシージャルを使ったゲームの実例についてよくまとまっている。 Procedural Content Generation Wiki (http://pcg.wikidot.com/) Procedural content generation (PCG)に関する
PythonでA*(A-Star)アルゴリズム - Pashango’s Blog
今回はA*アルゴリズムをPythonでやってみます。 ゲームプログラマの間では、もはや常識となりつつある最短経路問題解決アルゴリズムです。 A*は、古典的手法である「ダイクストラ法」を改良したものです。 スタート地点からノードnを通ってゴールに辿り付くとき、最短距離をf(n)とすると、 f(n) = g(n) + h(n) とすることができます、g(n)は「スタートからノードnまでの最短距離」、h(n)は「ノードnからゴールまでの最短距離」です。 でも、最初から適切なg(n)とh(n)が判ってるなら苦労しませんよね。 だから、テキトーな予測値を使って、最短経路をある程度予測して効率的に経路探索をしてみようという事です。 テキトーな予測値を使った最短経路距離をf*(n)とすると f*(n) = g*(n) + h*(n) となります、f*(n)を求めるためにテキトーなg*(n)とh*(n)を
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
グラフ理論ライブラリの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"));
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
DirectX技術編
ホーム < ゲームつくろー！ < DirectX9技術編 DirectX９技術編 Direct Graphics その１ 初期化なんて怖くないぜ！ 2013. 1. 11 改正 サンプルプログラム その２ 座標変換済み頂点で2D板ポリゴンを描画 2006. 5. 15 加筆改正 サンプルプログラム その３ テクスチャ作成あれこれ 2005. 12. 3 改正 サンプルプログラム その４ もう悩まないテクスチャブレンディング 2005. 12. 3 改正 その５ 高速フォント表示 2006. 5. 12 加筆改正 サンプルプログラム その６ 板ポリゴンに写る3Dオブジェクト 2005. 12. 3 改正 その７ 3Dオブジェクト描画のおさらい 2006. 7. 11 加筆改正 サンプルプログラム その８ キーフレームアニメーションで動きを制御 2005. 12. 3 改正 その９ Xファイル
マニュアル(インストール方法および取り扱い説明書)
1999年8月4日 文責： 青木 淳 マニュアル (インストール方法および取り扱い説明書) インストールについて 「GHL: Geometry Handling Library」をご用意の上、「じゅん」に「けいじょう」の最新バージョンをファイルイン(file in)してください。 「けいじょう(Kjo)」 ベクトル 座標値(point) ベクトル(vector) パラメトリック形状とパラメータ値による座標 (point on entity) 形状曲線 折線(polyline) 直線(line) ベジエ曲線(bezier curve) 有理ベジエ曲線(rational bezier curve) Bスプライン曲線(B-spline curve) 有理Bスプライン曲線(rational B-spline curve) 円錐曲線(conical curve) トリム曲線(trimmed cur
wavelet tree - 明日ではないから
圧縮検索で使われる技術wavelet treeをテンプレートライブラリとして書いてみました。 →を参考にしてみました。高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」 元となる記事が大変興味深かったのだけど、どうもサンプルコードが複雑すぎるのと、僕の解釈が悪いのか、記事中の説明がコードとつじつまが合わないところがあったので、自分で実装してみたしだい。 記事中ではハフマンコード化の話があるのだけど、あくまでそれは最適な圧縮率を出すための理論にしか過ぎなくて、 頻度の順番で文字をソートしておいて、文字ごとにその文字を１にしたビット列を格納していったほうが素直だろう。(元記事中は該当文字を0としたが1としたほうが操作しやすいと思う) たとえば、文字列T = "abccbbabca"があったときその頻度は'b','c','a'の順番になる。このとき各文字ごとにビット列を作ってい
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
はじめに 大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するのは2003年に提案されたデータ構造、wavelet tree（以下「WT」と表記）です。WTは圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。WTは文字列T[0...n-1]が与えられた時、次の2つの操作を定数時間でサポートします。 rank(p, c)――T[0...p]中のcの出現回数を返す select(i, c)――(i+1)番目のcの位置を返す WTの作業領域量は、文字列をそのまま保存した時の約2倍程度です。 対象読者 C++の
ビット演算について
ビット演算について考える機会があったので、結果をまとめておきます。 複数バイトの飽和加算 a と b は それぞれ 32 bit の unsigned long の変数で、これに 1 byte の 整 数が 4つまとめて入っているとします。これらについて、飽和加算をすることを 考えます。飽和加算とは、和が 0xff を越えたら結果を 0xff にするものです。 結果から先に出すと、次のような式になります。 tmp = ((a & b) + (((a ^ b) >> 1) & 0x7f7f7f7f)) & 0x80808080; // (1) mask = (tmp << 1) - (tmp >> 7); // (2) result = ((a + b) - mask) | mask; // (3) なぜこうなるのかについて解説します。 mask とは、オーバーフローしたバイトは 0xff
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
LZ法再び - DO++
可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法（Lemple Ziv法）ですが、他のデータ圧縮法（BWT法、PPM法、CM法）に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。 "On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf] まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現（マッチング）したら、その文字列を前回出現した（相対）位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データ
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
協調フィルタリングのグラフィカルモデル - nokunoの日記
協調フィルタリングとはAmazonのお勧めのように「この商品を購入した人はこんな商品も購入しています」という情報を用いて推薦をする手法です。グラフィカルモデルはベイジアンネットワークとも呼ばれ、最近一部で流行している機械学習の手法です。今回は、協調フィルタリングをグラフィカルモデルで表現したらどのようになるだろう、と考えて思いついたアイデアを紹介します。 今、ユーザuとアイテムiの組{u,i}のデータが大量に与えられているとします。例えばソーシャルブックマークならユーザとブックマークしているページの組み合わせ、E-commerseならユーザと購入した商品の組み合わせ、などです。ここではSBMを例に考えるので、はてブと同様にユーザはマイナスの評価を付けることはできないものとします。 このときユーザuに対してお勧めのページを推薦することを考えると、ユーザuがまだブックマークしていないページiに
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GC¥¢¥ë¥´¥ê¥º¥à¾ÜºÙ²òÀâ ÆüËܸì¤Î»ñÎÁ¤¬¤¹¤¯¤Ê¤¤GC¥¢¥ë¥´¥ê¥º¥à¤Ë¤Ä¤¤¤Æ¾ÜºÙ¤Ë²òÀ⤷¤Þ¤¹ ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼ÊÔ½¸ GC ºÇ½ª¹¹¿·¡§ author_nari 2010ǯ03·î14Æü(Æü) 20:47:11ÍúÎò Tweet ¤³¤ÎWiki¤¬Ìܻؤ¹½ê GC¤È¤Ï¡© GC¤ò³Ø¤ÖÁ°¤ËÃΤäƤª¤¯»ö ¼Â¹Ô»þ¥á¥â¥ê¹½Â¤ ´ðËÜ¥¢¥ë¥´¥ê¥º¥àÊÔ Reference Counter Mark&Sweep Copying ±þÍÑ¥¢¥ë¥´¥ê¥º¥àÊÔ IncrementalGC À¤ÂåÊÌGC ¥¹¥Ê¥Ã¥×¥·¥ç¥Ã¥È·¿GC LazySweep TwoFinger Lisp2 Pa
DO : Bep: 最小完全ハッシュ関数を用いた連想配列
Bepという連想配列のライブラリを公開しました。BSDライセンスです． キーは文字列限定で，前もって大量のキーと値のペアが前もって分かっている場合（１千万個とか）、使ってもらえるよう最適化しています。（一応、アドホックな方法で一個ずつキーを登録する方法もサポートしています） 特徴は内部に最小完全ハッシュ関数を利用しており少ない作業領域量でありながらそこそこ高速に動くところです．今のところ１千万キーぐらいで動作するのは確認しています．１キーあたり必要な作業領域量は大体3bit + キー自体の長さになります． 最小完全ハッシュ関数の構築自体も面白い問題です．最小完全ハッシュ関数はキー同士が衝突せず、さらにキーの数がn個のときハッシュ値は[0...n-1]が返されるもので、ぎっしり詰まった連番が返されると思ってもよいです。この実現には以下の論文での手法を使いました．3-ハイパーグラフの頂点割り当
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
