ずっと君のターン

MapReduce

Ruby, アルゴリズム, Products | 02:22 |

セミナーでそれなりに気持ちが盛り上がったので、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 # Reduce

ruby examples/word_count.rb -r # Reduce

ruby examples/word_count.rb -r # Reduce

って感じでいっぱい立ち上げておいて

ruby examples/word_count.rb -d # Driver

と実行すると、結果が

[ ["", 3], ["But", 1], ["GET", 3], ["HTTP", 2], ["POST", 3], ["RESTful", 1], ["Rails", 1], ["a", 2], ["almost", 1], ["and", 3], ["are", 2], ["be", 1], ["browsers", 1], ["by", 1], ["can", 1], ["consider", 1], ["days", 1], ["developers", 1], ["do", 1], ["fact", 1], ["forgotten", 1], ["from", 1], ["if", 1], ["is", 1], ["many", 1], ["maybe", 1], ["more", 1], ["of", 2], ["often", 1], ["only", 1], ["requests", 2], ["shouldn\201ft", 1], ["support", 1], ["surprise", 1], ["that", 3], ["the", 1], ["then", 1], ["these", 1], ["this", 1], ["transmitted", 1], ["two", 1], ["types", 1], ["web", 1], ["you", 1] ]

こんな感じに。

なんとなくちゃんと動いてる気がする。

ユーザーコードは

require 'lib/rmapreduce'

module WordCount
  class Mapper < RMapReduce::Mapper
    def map(lines)
      result = Hash.new {0}
      lines.each do |line|
        line.split(/[\s.,:;]/).each do |word|
          result[word] += 1
        end
      end
      result.to_pair
    end
  end

  class Reducer < RMapReduce::Reducer
    def reduce(pairs)
      result = Hash.new {0}
      pairs.each do |pair|
        result[pair.key] += pair.value
      end
      result.to_pair
    end
  end
end

大体こんな感じ。(一部省略)

どうなんだろ。これMapReduceなんだろうか・・・。

元論文読まずにセミナー資料だけで適当に実装してるからよく分からん・・・。

もう少し確認用のexampleを追加して、ソースを整理したらRubyForgeかどっかで恥を晒そう。そのあとはSawzallっぽいDSLもつくってみようかな・・・。

MapReduce

Ruby, アルゴリズム | 00:32 |

マルレクサブセミナーのメモ。

• MapReduceの入出力単位はKey:Valueの組(ペア)のリスト
• 処理単位はMapとReduceに加えて、隠された処理であるSort
• 大まかな処理の流れは
  1. Map ： 処理に適したペアに組みなおす(入出力は一対一)
  2. Sort ： 出力をReduceの入力として渡した際に処理を分散できるような形(同じキーごと)に並び替え
  3. Reduce ： 同じキーの組をまとめて処理して結果として一対のペアを生成(入出力は多対一)
• MapとReduceはいくらでも分散可能
• Sortが一番重い
• MapにはCombineと言う処理も含まれる？
• ReduceにSortが含まれる？
• Shuffle ＝ Sort ＋ Partitioning？（三つの使い分けはよく分かりませんでした）

まだいろいろあったけど、とりあえずこの辺まででなんとなく感じたアルゴリズムをものっそ適当に、分散する代わりにThread使って表現してみる。オレオレメモなのでいろいろ嘘。コメントもなし。あとでまたdRb使ってもう少し真面目に書いて考える。

文章に含まれるアルファベットの登場回数を数える。

require 'thread'

def key(ary)
  ary.nil? or ary.empty? ? 0 : ary[0]
end

module MapReducePpoi
  class Mapper
    def exec(input)
      combine map(input)
    end

    def combine(input)
      input.sort{|i1, i2| key(i1) <=> key(i2)}
    end

    def map(input)
      input.map{|i| [i, 1]}
    end
  end

  class Shuffler
    def initialize(num_of_reducers)
      @reducer_inputs = Array.new(num_of_reducers){Array.new}
    end

    def exec(input)
      sort partition(input)
    end

    def partition(input)
      input.each do |i|
        @reducer_inputs[key(i).hash % @reducer_inputs.size] << i
      end
     @reducer_inputs
    end

    def sort(input)
      # do nothing in this case
      input
    end
  end

  class Reducer
    def exec(input)
      reduce sort(input)
    end

    def sort(input)
      input.sort{|i1, i2| key(i1) <=> key(i2)}
    end

    def reduce(input)
      cur = input.shift
      input.inject([cur]) do |sum, e|
        if key(sum.last) == key(e) then sum.last[1] += 1 else sum << e end
        sum
      end
    end
  end

  NUM_MAPPERS = 4
  NUM_REDUCERS = 3
  def self.start(sentence)
    # initialize
    sentence.gsub! /\s/, ''
    mappers = Array.new(NUM_MAPPERS){Mapper.new}
    reducers = Array.new(NUM_REDUCERS){Reducer.new}
    shufflers = Array.new(mappers.size){Shuffler.new(reducers.size)}

    # map
    map_inputs = sentence.split(/(#{'.' * mappers.size})/).reject{|e| e.empty?}.map{|e| e.split ''}
    map_results = []
    m_mapper = Mutex.new
    mappers.each do |mapper|
      Thread.start do
        result = mapper.exec map_inputs.pop
        m_mapper.synchronize {map_results << result}
      end
    end

    # shuffle
    shuffle_inputs = map_results
    tmp_shuffle_results = []
    shufflers.each do |shuffler|
      tmp_shuffle_results << shuffler.exec(shuffle_inputs.pop)
    end
    shuffle_results = Array.new(NUM_REDUCERS){[]}
    tmp_shuffle_results.each do |s|
      s.each_with_index do |ss, i|
        shuffle_results[i] += ss
      end
    end

    # reduce
    reduce_inputs = shuffle_results
    reduce_results = []
    m_reducer = Mutex.new
    reducers.each do |reducer|
      Thread.start do
        result = reducer.exec reduce_inputs.pop
        m_reducer.synchronize {reduce_results << result}
      end
    end

    # show result
    puts reduce_results.inspect
  end
end

if $0 == __FILE__
  MapReducePpoi.start 'to be or not to be, that is the question.'
end

結果

$ ruby mapreduce_ppoi.rb

[ [ [".", 1], ["e", 2], ["h", 1], ["n", 1], ["q", 1], ["t", 3] ], [ ["a", 1], ["s", 2] ], [ ["i", 2], ["o", 1], ["u", 1] ] ]

凸包の高速な計算

Ruby, アルゴリズム, 計算幾何学 | 00:59 |

(amazon:476490277X p.8)

逐次添加法。

点列をx座標順に並び替えて、最初の3つの点の凸包(3点からなる三角形)から初めて、1点ずつ追加しながら凸包を更新して行く。

詳しくはこのpdfの12ページ当たりを参考。

require 'geo_base'

# 「コンピュータ・ジオメトリ 計算機科学:アルゴリズムと応用」 p.8
class ConvexHull < GeoBase
  def setup_points
    100.times do
      (@points ||= []) << p(rand(200)+50, rand(200)+50)
    end
    @points
  end
  
  def points
    @points || setup_points
  end

  def signed_dimension(a, b, c)
    ((a.x - c.x) * (b.y - c.y) + (b.x - c.x) * (c.y - a.y)) / 2
  end
  
  def clockwise?(list)
    return false if list.size < 3
    signed_dimension(*(list[-3..-1])) < 0
  end
  
  # GeoBaseクラスを変更して、startメソッドの代わりにクラス名を
  # 小文字にした名前のメソッドが最初に呼ばれるようになりました
  def convex_hull
    # 点列をx座標順にソート
    points.sort! {|p1, p2| p1.x <=> p2.x}
    
    # 上部凸包
    upper_list = [points[0], points[1]]
    (3...points.size).each do |i|
      upper_list << points[i]
      while 3 <= upper_list.size and not clockwise?(upper_list)
        upper_list.delete_at -2
      end
    end
    
    # 下部凸包
    lower_list = [points[-1], points[-2]]
    (3..points.size).each do |i|
      lower_list << points[-i]
      while 3 <= lower_list.size and not clockwise?(lower_list)
        lower_list.delete_at -2
      end
    end
    
    # 上部凸包と下部凸包を連結
    lower_list.pop
    lower_list.unshift
    list = upper_list + lower_list
    
    # 結果表示
    draw *points
    draw *lines(list, true)
  end
end

ConvexHull.start

結果

点が100個でも余裕で表示できるようになった。

ときどき凸包の外に点が表示されるのでなんかバグがあると思うけど、放置。

凸包のバカ正直な計算

Ruby, アルゴリズム, 計算幾何学 | 03:12 |

(amazon:476490277X p.4)

GoogleでI'm feeling luckyしてみると、

「点集合の凸包-数学アルゴリズム演習ノート-」

凸包とは、平面グラフ上の点（ある点集合）の中で最も｢外側」にある点を直線で結んで出来る線分の集合です。つまり、凸包の直線群はその線の内側にすべての点が含まれるような、いわばその点集合の最短の「境界線」と言えるでしょう。

今回実装するアルゴリズムでは、与えられた点の組み合わせで可能な全ての線分を求めて、それぞれの線分に対して、それに含まれない点が全てその線分の片側にあるかどうかを確認。もしそうならその線分は凸包の辺の一つ、そうじゃなかったら凸包の内部に含まれるので無視、と言うやり方で凸包を求めます。

想像通りむちゃくちゃ重くて、点の数を100にしたら帰ってこなかった。

require 'geo_base'

# 「コンピュータ・ジオメトリ 計算機科学:アルゴリズムと応用」 p.4
class SlowConvexHull < GeoBase
  def setup_points
    20.times do
      (@points ||= []) << p(rand(200)+50, rand(200)+50)
    end
    @points
  end
  
  def points
    @points || setup_points
  end
  
  def sort(edges)
    sorted_edges = [edges.pop]
    until edges.empty?
      edges.each do |ll|
        if sorted_edges.last.p2 == ll.p1
          sorted_edges << edges.delete(ll)
        end
      end
    end
    sorted_edges
  end
  
  def start
    # 辺集合
    edges = []
    
    # 可能な全ての線分
    lines = []
    points.each do |pp1|
      points.each do |pp2|
        lines << l(pp1, pp2) if pp1 != pp2
      end
    end
    
    lines.each do |ll|
      valid = true
      points.select{|pp| ll.p1 != pp and ll.p2 != pp}.each do |pp|
        valid = false if ll.left? pp
      end
      edges << ll if valid
    end
    
    # 結果の辺集合を時計回りにソート
    sorted_edges = sort edges
    
    # 結果表示
    puts sorted_edges.inspect
    draw *points
    draw *sorted_edges
  end
end

SlowConvexHull.start

結果

自習開始

Ruby, アルゴリズム, 計算幾何学 | 03:07 |

ちょっと興味がわいたので、amazon:476490277Xに擬似コードで書かれてるアルゴリズムを実際にRubyでちまちまと組んでいこうかなと。

まずは、ベースのクラスを作っとく。

require 'sdl'

class GeoBase
  attr_accessor :screen
  
  class Point
    attr_accessor :x, :y
    def initialize(x, y); @x, @y = x, y end
    def to_s; "(#{x}, #{y})" end
    def inspect; to_s end
    def ==(p1); x == p1.x and y == p1.y; end
  end
  
  class Line
    attr_accessor :p1, :p2
    def initialize(p1, p2); @p1, @p2 = p1, p2 end
    def to_s; "[#{p1.to_s}, #{p2.to_s}]" end
    def inspect; to_s end
    def ==(l1); p1 == l1.p1 and p2 == l1.p2; end
    
    # 「計算幾何学入門 幾何アルゴリズムとその応用」p.27
    def left?(p)
      0 < (p1.x-p.x)*(p2.y-p.y)+(p2.x-p.x)*(p.y-p1.y)
    end
  end

  def default_color; [255, 255, 255] end
  
  def point(x, y)
    Point.new x, y
  end
  alias p point
  
  def line(x1, y1, x2=nil, y2=nil)
    if x2
      x1 = p x1, y1
      y1 = p x2, y2
    end
    Line.new x1, y1
  end
  alias l line
  
  def draw_point(p1)
    @screen.drawFilledCircle p1.x, p1.y, 3, default_color
  end

  def draw_line(x1, y1=nil, x2=nil, y2=nil)
    if x2
      x1 = l x1, y1, x2, y2
    elsif y1
      x1 = l x1, y1
    end
    @screen.drawLine x1.p1.x, x1.p1.y, x1.p2.x, x1.p2.y, default_color
  end
  alias l line
  
  def draw(*targets)
    targets.each do |target|
      case target
      when Point
        draw_point target
      when Line
        draw_line target
      end
    end
  end
  
  def start
    raise 'subclass responsibility'
  end

  def update
    @screen.updateRect 0, 0, 0, 0
  end
  
  def self.wait
    loop do
      while event = SDL::Event2.poll
        case event
        when SDL::Event2::Quit, SDL::Event2::KeyDown
          exit
        end
      end
    end
  end
  
  def self.start
    SDL.init SDL::INIT_VIDEO
    geo = self.new
    geo.screen = SDL.setVideoMode 640, 480, 16, SDL::SWSURFACE
    geo.start
    geo.update
    wait
  end
end

今後は上のクラスを継承してstartメソッドだけ上書きすれば大丈夫。

例えばこんな感じ。

↓

class GeoBaseTest < GeoBase
  def start
    draw p(10, 10)
    draw l(100, 100, 400, 200)
    draw p(100, 80), l(80, 80, 200, 400)
  end
end

GeoBaseTest.start

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

Ruby, アルゴリズム | 15:44 |

初はてぶなのに転載...。

いや、スーパー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(' ')
  end

  def train(features)
    model = Hash.new(1)
    features.each{|f| model[f] += 1}
    model
  end

  def edits1(w, a='abcdefghijklmnopqrstuvwxyz'.split(''))
    n = w.size
    [(0...n).map{|i| w[0...i] + w[i+1...n]},                             # deletion
     (0...n-1).map{|i| w[0, i] + w[i+1].chr + w[i].chr + w[i+2, n-i-2]}, # transposition
     a.map{|c| (0...n).map{|i| w[0...i] + c + w[i+1...n]}},              # alteration
     a.map{|c| (0..n).map {|i| w[0...i] + c + w[i...n]}}].flatten.uniq   # insertion
  end

  def known_edits2(word, known_words=@nwords.keys)
    edits1(word).map{|s1| edits1(s1)}.flatten & known_words
  end

  def known(words, known_words=@nwords.keys)
    words & known_words
  end

  def correct(word, nwords=@nwords)
    @nwords = nwords
    candidates = known([word]) | known(edits1(word)) | known_edits2(word) | [word]
    candidates.max{|c1, c2| @nwords[c1] <=> @nwords[c2]}
  end
end

if __FILE__ == $0
  checker = SpellChecker.new 'big.txt'
  if ARGV.empty?
    puts 'Ctrl+c to stop'
    while gets
      puts checker.correct($_)
    end
  else
    puts checker.correct(ARGV[0])
  end
end