マージソートとクイックソートの比較(Ruby)

自分の実装で、マージソートクイックソートベンチマークをしてみました。
マージソートの実装はこれクイックソートのはこれ(いちばん下の実装)です。
 
マージソート

クイックソート

これを見ると、クイックソートの方が速いが実行時間はバラついている感じ。


ベンチマーク
bench_sorts.rb

require 'benchmark'

100.times do
  ar = (0..10_0000).to_a.shuffle
  Benchmark.bm 12 do |x|
    x.report("merge sort") {ar.merge_sort}
    x.report("quick sort") {ar.qsort}
  end
end

実行は $ ruby bench_sorts.rb > bench_sorts.txt

Gnuplot でグラフ化。

require 'histogram/array'
require 'numo/gnuplot'

ar = open("bench_sorts.txt", &:readlines)
m = []
q = []
ar.each_slice(3) {|x| m << x[1]; q << x[2]}

pick_up = proc do |ar|
  ar.each_with_object([]) {|i, a| a << i.split(" ")[6].to_f}
end

mb, mf = pick_up.call(m).histogram
qb, qf = pick_up.call(q).histogram

Numo.gnuplot do
  set title: "merge sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_m.png'
  set style: [:fill, :solid, {border: -1}]
  plot mb, mf, w: :boxes, lc: {rgb: "orange"}
end

Numo.gnuplot do
  set title: "quick sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_q.png'
  set style: [:fill, :solid, {border: -1}]
  plot qb, qf, w: :boxes, lc: {rgb: "orange"}
end

エイト・クイーン(8 queen)問題を Ruby で解いてみる

エイト・クイーン - Wikipedia

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

 
チェスの盤面は 8×8 であり、クイーンのコマは前後左右斜めにどれだけでも進むことができます。盤面上に 8つのクイーンを置くとき、どのクイーンも他のいずれにも取られないような配置を考えるわけです。


最初の駒は任意に与えられるものとしましょう。また、ひとつでも解が見つかれば終了することにします。考え方としては、人間がやる場合と似て、適当に一駒ずつ置いていき、失敗すればひとつ前に戻って置き直していくという方法を取ります。いわゆる「バックトラック法」というやつです。Ruby で解いてみました。下は回答のひとつです。

$ time ruby eight_queen.rb
@.......
......@.
....@...
.......@
.@......
...@....
.....@..
..@.....

real	0m0.077s
user	0m0.044s
sys	0m0.000s

 

eight_queen.rb

N = 8

class EightQueen
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
      @depth = 0
    end
    attr_accessor :x, :y, :parent, :depth
  end
  
  def initialize(x, y)
    @stack = [Step.new(x, y)]
  end
  
  def solve
    while (a = @stack.pop)
      y = a.y + 1
      board = get_board(a)
      N.times do |x|
        next if board[y][x] == 1
        nxt = Step.new(x, y)
        nxt.parent = a
        nxt.depth = a.depth + 1
        finish(nxt) if nxt.depth == N - 1
        @stack.push(nxt)
      end
    end
    raise "No answer."
  end
  
  def get_board(a)
    board = Array.new(N) {Array.new(N, 0)}
    begin
      N.times do |i|
        board[i][a.x] = 1
        board[i] = Array.new(N, 1) if i == a.y
        d = (i - a.y).abs
        next if d.zero?
        x1 = a.x - d
        x2 = a.x + d
        board[i][x1] = 1 if x1 >= 0
        board[i][x2] = 1 if x2 < N
      end
    end while (a = a.parent)
    board
  end
  
  def finish(a)
    bd = Array.new(N) {"." * N}
    while a
      bd[a.y][a.x] = "@"
      a = a.parent
    end
    bd.map {|x| puts x}
    exit
  end
end

EightQueen.new(rand(N), 0).solve


※追記(7/24)
コードを多少修正しました。また、すべてのパターン(92通り)も求めてみました。コードと結果は下の Gist に。実行時間は 0.1秒程度です。コードは上のものにほんの少し修正を加えただけです。
eight_queen_all.rb · GitHub

与えられた迷路の最短経路を求める(Ruby)

人材獲得作戦・4 試験問題ほか: 人生を書き換える者すらいた。

さて試験問題です。
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。

 
おもしろそうなので Ruby で解いてみました。もともとはここで知ったものです。
僕はまだまだ不勉強で A* も dijkstra も知りませんが(そのうちお勉強する予定)、ふつうに幅優先探索ですよね。

というわけでやってみました。先に出力を載せておきます。

$ time ruby solve_maze.rb
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

real	0m0.164s
user	0m0.072s
sys	0m0.012s

こんな感じで解けました。


コードは以下。上に書いたとおり、単純な幅優先探索です。もちろん幅優先探索は最短経路を与えます。
solve_maze.rb

class SolveMaze
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
    end
    attr_accessor :x, :y, :parent
    
    [:up, :down, :left, :right].each_with_index do |mt, i|
      define_method(mt) do
        a = [Step.new(x, y - 1), Step.new(x, y + 1),
             Step.new(x - 1, y), Step.new(x + 1, y)][i]
        a.parent = self
        a
      end
    end
  end
  
  def initialize
    @map = DATA.readlines
  end
  
  def get(st)
    @map[st.y][st.x]
  end
  
  def set(st, ch)
    @map[st.y][st.x] = ch
  end
  
  def go
    stack = [Step.new(1, 1)]
    
    while (a = stack.shift)
      [a.up, a.down, a.left, a.right].each do |nxt|
        case get(nxt)
        when "G" then finish(a)
        when " "
          set(nxt, "@")
          stack.push(nxt)
        end
      end
    end
  end
  
  def finish(a)
    @map.map! {|x| x.gsub(/@/, " ")}
    while a.parent
      set(a, "$")
      a = a.parent
    end
    @map.each {|x| puts x}
    exit
  end
end

SolveMaze.new.go

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

メインループは SolveMaze#go の while 文です。SolveMaze#finish は回答を出力して終了します。それぞれのステップをクラス(Step クラス)にするまでもなかったかも知れませんが、まあいいんじゃないでしょうか。

DRY原則を満たすためにちょっとだけメタプログラミングを使っている以外は、素直なコードではないかと思います。

僕などがいうまでもないのですが、幅優先探索が気になる方は、while (a = stack.shift)stack.push(nxt) の部分に特に気をつけてコードを読んでみて下さい。ちなみに、この shiftpop に替えるだけで深さ優先探索になりますよ。これでも解は求められますが、一般に最短経路になりません。一行替えるだけでのちがい、やってみるとおもしろいと思います。


なお、Ruby コミッターの「まめめも」さんのコードはすごいです。え、こんなに短いの、という感じ。自分などはまだまだですね。

マージソート(Ruby)

アルゴリズムの基本

アルゴリズムの基本

マージソートアルゴリズムだけ勉強して、自力で Ruby で実装してみました。

merge_sort.rb

class Array
  def merge_sort
    return [] if empty?
    each_slice(1).to_a.merge
  end
  
  def merge
    ar0 = []

    each_slice(2) do |x|
      ar = []
      if x.size == 1
        ar = x[0]
      else
        while x[0].any? and x[1].any?
          ar.push((x[0][0] < x[1][0]) ? x[0].shift : x[1].shift)
        end
        ar += x[0] + x[1] 
      end
      ar0 << ar
    end
    
    return ar0[0] if ar0.size == 1
    ar0.merge
  end
  protected :merge
end

a = (0..10).to_a.shuffle
a.merge_sort

Array#merge は分割されたソート済みの配列を2つずつ選んで結合します。結合をしているのは while 以下の 4行で、配列 x[0] と x[1] から値の小さい順に要素を選んで配列 ar に push します(値の小さい順に選んでいるので、配列 ar もソート済になります)。そしてそれを再帰的に繰り返し、すべて結合したら終了となります。
 
 
ここでの実装(これは本を参考にした)の方がすっきりしていますかねえ。でも、自力の実装もアルゴリズムに素直だという利点があると思います。

Ruby でたらいまわし関数を遅延評価する

Haskell が遅延評価で「たらいまわし関数」を高速に実行できるなら、Ruby でも Proc で遅延評価できるので、Ruby でも「たらいまわし関数」を高速化できるのではないかと思った。でぐぐってみたら、そのものズバリの記事を発見。
 
おお、きちんとまとまったわかりやすい記事である。このリンクだけで充分なのだが、やはり自分でやってみないとということでやってみました。基本的に上記事のコードと同じ内容です(多少好みに書き換えました)。

tarai_lazy.rb

class Proc
  def -(lmd)
    ->{self.call - lmd.call}
  end
end


def tak_lazy(x, y, z)
  ->{
    xval = x.call
    yval = y.call
    if xval <= yval
      yval
    else
      tak_lazy(tak_lazy(x - ->{1}, y, z),
               tak_lazy(y - ->{1}, z, x),
               tak_lazy(z - ->{1}, x, y)).call
    end
  }
end

x, y, z = 12, 6, 0
tak = tak_lazy(->{x}, ->{y}, ->{z}).call
puts "tak(#{x}, #{y}, #{z}) = #{tak}"

数値まで lambda で包んでしまう。実行結果。

$ time ruby tarai_lazy.rb
tak(12, 6, 0) = 12

real	0m0.096s
user	0m0.036s
sys	0m0.020s

おお、圧倒的に速い!(Linux Mint 18.2 @ Core i5 4210U 1.70GHz; Ruby 2.3.3)

なんと、過去記事での C言語より速いではないか! 遅延評価を使わない Ruby 版と比べると、約20倍の高速化になっている(以上 user で比較)。なるほど、「たらいまわし関数」は遅延評価と相性がいいのだなと納得。まあ、Haskell 版にはさすがに敵いませんが。

Haskell でたらいまわし関数

まだ Haskell は全然わかりませんが、Haskell では「たらいまわし関数」がすごいということなのでやってみました。「たらいまわし関数」については、このブログにも簡単な記事があって、Ruby などでやってみております。簡単にいうと、これは関数呼び出しのベンチマークに使われる関数です。竹内関数とも呼ばれます。


で、Haskell のコードです。面倒な部分(つまり入出力)ははしょって、超初心者らしく書いております(他人のコードを参考にして、というかもろパクっています)。

tarai :: Int -> Int -> Int -> Int
tarai x y z
    | x <= y    = y
    | otherwise = tarai
                    (tarai (x - 1) y z)
                    (tarai (y - 1) z x)
                    (tarai (z - 1) x y)
                    
main = putStrLn $ show $ tarai 12 6 0

 
実行結果。

$ ghc tarai.hs
$ time ./tarai
12

real	0m0.003s
user	0m0.000s
sys	0m0.000s

なんというか…、言葉も出ません。

これはどういうことかというのですが、何なんでしょうね。詳しくは
で色いろ調べられております(自分にはよくわかりませんが)。遅延評価のためということなのでしょう。カリー化は? これも自分にはよくわかりませんが、もちろん関係しているのでしょうな。たらいまわし関数に関しては Haskell 最強という話であります。


※追記
インタプリタでやっても速いので、これはやはり遅延評価自体の威力なんだろうなあ。

$ time runghc tarai.hs
12

real	0m0.192s
user	0m0.148s
sys	0m0.036s

GTK+ で落書き 9(Ruby)

自作の Gem 'oekaki' で落書きしてみました。蚊取り線香? 何だか目が回ります。
 

 
コードは以下。何も考えずにテキトーにいきあたりばったりでコーディングしました。

require 'oekaki'

R = 7
Width, Height = 500, 500

Oekaki.app width: Width, height: Height do
  draw do
    color(0, 0, 0)
    rectangle(true, 0, 0, Width, Height)
  end
  
  p = Vector[0, 0]
  np = p.dup
  deg = 90
  r = 0
  step = 1.5
  
  b_line = lambda do |p1, p2|
    l = (p2 - p1).r
    pt = p1.dup
    0.upto(l) do
      color(0, 65535, 0)
      arc(true, Width / 2 + pt[0] - R, Height / 2 - pt[1] - R,
          R * 2, R * 2, 0, 64 * 360)
      pt += (p2 - p1) / l
    end
  end
  
  id = timer(50) do
    b_line.call(p, np)
    
    p = np
    θ = PI * deg / 180
    np = Vector[cos(θ), sin(θ)] * r
    r += step
    step_d = 20 - r / 35
    deg -= step_d
    Gtk.timeout_remove(id) if r > 220
    true
  end
end

関数 b_line は点 p1 から p2 へ太い線を引きます(円を動かしてやっています)。
お絵かきするのに標準添付ライブラリの Vector クラスや(ここでは使っていませんが)Matrix クラスは役立ちます。計算がだいぶ楽になりますよ。
 
Gen 'oekaki' については以下。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた(Ruby) - Camera Obscura