MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介 - Preferred Networks Research & Development
どうも，実は今年から開発チームにjoinしていた中川です．可愛い犬の写真がなかったので，可愛いマスコットの画像を貼っておきます． 最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました．これはつまり，それだけ大量のデータをなんとか処理したいという要望があるからだと思います．しかし当たり前ですが，MapReduceは銀の弾丸ではありません． ということで，最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について，社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います． Bulk Sychronous Parallel このアルゴリズム自体は1990年に誕生したものです．長いのでBSPと書きます．さて，グラフから最短経路を求める時，MapReduceは使えるでしょうか？このような論文が出るくらいですから出来ないことはあ
ソート時間の比較
下のアプレットは、6種類すべてのソートアルゴリズムを同時に実行するものです。 左上から右へ、バブルソート、バケットソート、基数ソート、ヒープソート、マージソート、クイックソートです。 "Start" ボタンを押すと、すべてのソートが同時開始されます。クイックソートがもっとも速く並べ終わり、次にバケットソート、基数ソートの順で並べ終わるのがわかります。 データ数や初期並びを変えて、いろいろなデータで試してみましょう。 アプレットの並べ替えプログラムは、人間の眼で見て並べ替えの様子がわかりやすいように、データの交換が起こるたびに wait を入れて速度を遅くして表示しています。しかし、この方法では、データの交換以外に要する時間はほとんど無視されることになり、正確な意味で正しい比較をしていることにはなりません。 そこで、wait を入れずに並べ替えを行うプログラムを作成し、いろいろな個数のデータ
正規表現しちへんげ！ 第二夜
09:25 10/12/31 年末まとめ 今年何やったっけ、と日記を読み返していました。何もやってないな…。 Polemy 作りました、くらい。 言語処理系作るのはやっぱり楽しいですね。 汎用言語として使う本格的なものを作ろうとすると懲りすぎて一歩も進まなくなってしまう自分が見えるので、 来年は、そうだなあ、TopCoder/ICPC風コンテストに特化した言語というかC++へのトランスレータ、 くらいに絞って作ってみようかなあ。 書いた記事だと 最短性チェックの話 が自分では割と気に入っています。 これのもっとバグを許容するバージョン作れないか。 読んだ論文で面白かったのは "A Pearl on SAT Solving in Prolog" と "When Simulation Meets Antichains" (PDF) など。 あとは、今年読んで面白かった本ベスト５（順不同）： 『
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
w.l.o.g. ギャップバッファ
04:40 04/06/04 ピーステーブル PieceTable とも言う。文字列の Piece（小片）を繋げて、 一つの巨大な文書を表現する方式。 検索すると引っかかる文書のほとんどが AbiWord 関係なので、 このワープロソフトの主要な内部データ構造ということなのかな。 他に、MS-WordやOpenOffice.org関連の文書にも登場していて、 基本的に単なるテキストエディタよりは、文字に付加情報をくっつける系の 編集ソフトに使われる場面が今のところ多いみたいです。 余談ですがAbiWordは、綱渡り的にですがBeOS版の開発が続いている貴重なワープロソフトなのです。感謝感謝。 概要 ファイルを読み込んだとしましょう。ABCDEFG、という７文字のファイル。 とりあえず、７文字分のOrigという名前のバッファを用意して、そこに格納します。 それと別に、Addという名前の空のバ
冪乗 - Wikipedia
数学における冪乗（べきじょう、べき乗、英: 仏: 独: exponentiation）または冪演算（べきえんざん）は、底 (てい、英: base) および冪指数 (べきしすう、英: exponent) と呼ばれる二つの数に対して定まる数学的算法である。その結果は冪 (べき、英: power) と呼ばれる。表現の揺れにより同じ概念は日本語で「累乗」とも表現されており、初等教育ではこちらの表現のほうが多くなっている（本文参照）。 底（英語版） b および冪指数 e をもつ冪は、底の右肩に冪指数を乗せて be のように書かれる。 であり、bn は b の n-乗や、n-次の b-冪などと呼ばれる。 特定の冪指数に対して、固有の名前が付けられている。例えば、冪指数が 2 である冪（2 乗） b2 は「b の平方 (square of b)」または「b-自乗 (b-squared)」と呼ばれ、冪指数
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
開発メモ: トップNソートの検討
上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー
ファイルから複数の行を高速に取り出すプログラム(Pure Perl)
ファイルから複数の行を高速に取り出すプログラム(Pure Perl) 2010-08-13-2 [Programming][Algorithm] インデックスを使った指定行取り出しプログラム[2010-08-10-1] についての記事を先日公開した。 そのプログラムを作成した動機の一つが 「リードオンリーのテキストファイル（それもメモリに読み込むのがうんざりするくらいに巨大なやつ）からランダムに複数の行を取り出したい」 というもの。 この記事ではランダム複数行取り出しタスクについて、先日の記事[2010-08-10-1]に沿って先頭から走査する方法とインデックスを用いた方法を紹介する。 頭から操作する方法 ランダムに一行だけ取り出すには定番の方法がある。 詳しくは[2004-11-30-5]を参照のこと。 エッセンスだけ一行で書くとこんな感じ： rand($.) < 1 && ($line
【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
ギャップ・バッファ
説明 ギャップ・バッファは，テキスト・エディタなどで用いられる，シーケンスを扱うデータ構造です． ここで公開するプログラムはK. Inaba氏の制作されたエディタ，GreenPadにおいて使われているギャップ・バッファをC++言語に含まれるSTLのvectorを使うように改造したものです． また，それをC言語のみで書き直したものも公開しています． 両方ともNYSL（ライセンス）とします． ダウンロード C++言語版: （2003年3月26日） gapbuffer.h C言語版: （2008年9月19日）- 仮の実装なのでバグがあるかもしれません． gbuf.h gbuf.c 解説 ギャップ・バッファはテキスト・エディタのテキスト・バッファなど，長く連なるデータを保持する際に用いられるシーケンス・コンテナです． 局所的な要素の挿入，削除を頻繁にする場合に適したデータ構造です． 双方向リスト（
浮動小数点数の比較
浮動小数点数の比較アルゴリズム ホーム イントロダクション 許容値の選び方 close_at_toleranceアルゴリズム 編集 謝辞 参考 イントロダクション とても大きな数値は小さな数値では、abs(f1-f2) <= eというシンプルな解放では浮動小数点数の 等値チェックはうまくいかないことがある。そのため、operator=(...)の使用はふさわしくないと言える。 この浮動小数点数比較アルゴリズムはより信頼性の高い、Knuthの[1]の文献で紹介されている方法を元にしている。 不動小数点数 u と v 、許容値 e が与えられたとする。
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する
FLP35-C. 浮動小数点数値を比較する際には精度を考慮する C の浮動小数点演算は正確ではない。特に、浮動小数点数を比較する際は、可搬性があり計算結果が同じになる方法で行う必要がある。 違反コード c と a / b の比較の結果は、あらかじめ予測することはできず、実行するマシンやコンパイラ、最適化レベルの違いによって変わる可能性がある。 float a = 3.0; float b = 7.0; float c = a / b; if (c == a / b) { printf("Comparison succeeds\n"); } else { printf("Unexpected result\n"); } 処理系固有の詳細 このコードを、IA-32 Linux 上の GCC 3.4.4 で最適化レベル 1 以上、あるいは IA-32 Windows XP 上の Microsof
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおま
d.y.d. - 最短性をチェックする
17:31 10/01/26 言語雑談会 言語雑談会 なるものに行ってきました。 自分は主に最近のD言語の話題 [PDF] [PPTX] についてと、 最近読んだ Pattern Calculus がイマイチ心に響かなかったという話と、 これも最近読んだ Prolog で SAT ソルバ という論文が格好良すぎて卒倒しそうです、などの話題を雑談していました。 SAT の話をしていてふと突然気づいたんですが、私が今までSATソルバに落としてみたことのある問題は、 すべて割と簡単に CNF（SATソルバがそのまま食べてくれる綺麗な形式の論理式） ができあがる問題だったようです、数独とか。 任意の命題論理式をCNFに変換できる指数爆発しない方法をそういえば知らないぞ俺！としゃべってたら soutaro さんが素晴らしい解説 をして下さいました。ありがたや。 あと shinhさんの 「コンピュータ
min_heapを用いた上位r個の要素の抽出 - tsubosakaの日記
MG勉強会の発表があるため4.6ランキング検索の部分を読むついでに、最後のサブセクションの上位r個の要素を取り出す部分について実装してみた。 情報検索において、N個の候補集合から上位r個の要素を取り出すことが多い。 値が配列に格納されているとするとこれを実現するためのコードはもっとも単純に行うと以下のようになる //長さlenの配列arrayの中でトップr個の値をresultに挿入する void sort_method(int * array , int len, int r , vector<int> & result){ sort(array , array + len); copy(array + len - r , array + len , back_inserter(result)); } しかし、Nが大きいとき、MGの例だとN=100万のときにsortの処理にはおおよそ100
Depth first search と Breadth first search
ここでは、探索における代表的な２つの方法、Depth first search (DFS) とBreadth first search (BFS) とは何か、どのような利害得失があるのか、について述べます。 Depth first search （深さ優先探索） まず子を一つ調べ、次にその子のさらに子を調べ、次にその子の子の子の……というように出来る限り進んで行って、行き止まったら戻って他の子を探索する、というのが DFS です。子に対して DFS を子に再帰的に適用していく、と捉えることも出来ます。 Breadth first search （幅優先探索） 自分の子を全て探索してから、子の子を全て探索し、子の子の子の……というように、同じ深さのものを全て探索してから次の階層へ進むのが BFS です。 記憶領域の効率 DFS の場合 これ以降、木の高さを n で、ノードからどのくらいの子が
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp： ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか: ジュニア,ヘンリー・S. ウォーレン,Jr.,Henry S. Warren,滝沢 徹,赤池 英夫,藤波 順久,鈴木 貢,葛 毅,玉井 浩: 本
ゲーム木の探索問題