※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです. さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます. 玉入れとリレー まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう. 運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです. ただし, 同じ団体競技でもその性質は違います. 玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしている
今日の Hadoop ソースコードリーディングで Dijkstra アルゴリズムの知名度が低かったので, 解説を書いてみたぜ. このアルゴリズムを一言で説明すると? グラフ上のある始点からあるノードへの最短経路とその距離を求めるアルゴリズム. 用語が分かんないんだけど... グラフというと y = 2x とかを思い浮かべるかもしれないが, この場合の「グラフ」というのは「いくつかの丸 (= ノード, 節) を線 (= エッジ, 辺) でつないだもの」で, 状態遷移図もグラフの一種. 状態遷移図は「有向グラフ」と呼ばる. 丸と丸とをただの線ではなく矢印でつなぐので「有向」=「向きが付いている」と言う. "DAG" は "Directed Acyclic Graph" の略で「非循環有向グラフ」と訳される. "Directed" と "Acyclic" の順序が逆になってるのは気にせんでくれい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
