アルゴリズム

MapReduce

セミナーでそれなりに気持ちが盛り上がったので、dRuby版をなんとなく動くようにしてみました。 ruby examples/word_count.rb -ts # TupleSpace ruby examples/word_count.rb -m # Map ruby examples/word_count.rb -m # Map ruby examples/word_count.rb -r…

MapReduce

マルレクサブセミナーのメモ。 MapReduceの入出力単位はKey:Valueの組(ペア)のリスト 処理単位はMapとReduceに加えて、隠された処理であるSort 大まかな処理の流れは Map : 処理に適したペアに組みなおす(入出力は一対一) Sort : 出力をReduceの入力として…

凸包の高速な計算

(amazon:476490277X p.8)逐次添加法。 点列をx座標順に並び替えて、最初の3つの点の凸包(3点からなる三角形)から初めて、1点ずつ追加しながら凸包を更新して行く。詳しくはこのpdfの12ページ当たりを参考。 require 'geo_base' # 「コンピュータ・ジオメトリ…

凸包のバカ正直な計算

(amazon:476490277X p.4)GoogleでI'm feeling luckyしてみると、「点集合の凸包-数学アルゴリズム演習ノート-」 凸包とは、平面グラフ上の点(ある点集合)の中で最も「外側」にある点を直線で結んで出来る線分の集合です。つまり、凸包の直線群はその線の内…

自習開始

ちょっと興味がわいたので、amazon:476490277Xに擬似コードで書かれてるアルゴリズムを実際にRubyでちまちまと組んでいこうかなと。まずは、ベースのクラスを作っとく。 require 'sdl' class GeoBase attr_accessor :screen class Point attr_accessor :x, :…

スペル修正プログラム Ruby版 (改)

初はてぶなのに転載...。 いや、スーパーpre記法を試したくて。これのRuby版。 class SpellChecker def initialize(filename=nil) @nwords = train(word(File.read(filename))) if filename end def word(text) text.downcase.gsub(/[^a-z]/, ' ').split(' '…