再帰をQueueで

IPSJのつづき。RWikiのスタートアップのように、再帰を待ち行列に変形してタスク並列（？）にする。まず、都合により特別なQueueを用意。requestで処理を投入、take_requestで取り出して、求めた値（0か1）をresponseで戻す。requestの回数とresponseの回数が一致したらvalueがとれるようにする。@done.broadcastがなんか微妙な感じだけど、今回には十分だと思う。たぶん。

require 'monitor'
require 'thread'

class NQueenQueue
  include MonitorMixin
  def initialize
    super
    @queue = Queue.new
    @request = 0
    @response = 0
    @value = 0
    @done = new_cond
  end
  
  def request(size, board)
    synchronize do
      @queue.push([size, board])
      @request += 1
    end
  end

  def response(v)
    synchronize do
      @response += 1
      @value += v
      @done.broadcast if @request == @response
    end
  end
  
  def take_request
    @queue.pop
  end
  
  def value
    synchronize do
      while true
        next if @request == 0
        return @value if @request == @response
        @done.wait
      end
    end
  end
end

んで先日のNQueenを変形する。あとでdRuby化する都合により、queueをパラメータとしてもらうことにする。

class NQueen
  def initialize(queue)
    @queue = queue
  end

  def concat(board, row)
    board.each_with_index do |v, col|
      return nil if v == row
      return nil if (v - row).abs == board.length - col
    end
    board + [row]
  end

  def nq(size, board=[])
    size.times do |row|
      fwd = concat(board, row)
      next unless fwd
      return 1 if fwd.size == size
      @queue.request(size, fwd)
    end
    return 0
  end

  def worker
    while true
      size, fwd = @queue.take_request
      @queue.response(nq(size, fwd))
    end
  end
end

んでmainはこんな感じ。わざわざスレッドを起動しているところが次の展開へのご都合を感じさせる。

if __FILE__ == $0
  size = (ARGV.shift || '5').to_i
  queue = NQueenQueue.new
  nq = NQueen.new(queue)
  nq.nq(size)
  t = Thread.new do
    nq.worker
  end
  p queue.value
end