ruby でマージソート

ruby でマージソートを作ってみた。

再帰あり

割と ruby っぽく書けた。

def msort1(n)
  return n if n.size <= 1
  left, right = msort1(n.first(n.size/2)), msort1(n.last(n.size-n.size/2))
  res = []
  until ( left.empty? || right.empty? ) do
    res << (left.first <= right.first ? left.shift : right.shift)
  end
  res += left + right
end

再帰なし その1

実は2分割ずつになってないけど気にしない。

def msort2(n)
  return n if n.size <= 1
  i = 1
  while ( 2**(i-1) < n.size ) do
    offset = 0
    width = 2**i
    while offset+width/2 < n.size do
      index = offset
      subset = []
      left = n[offset, width/2]
      right = n[offset+width/2, width-width/2]
      until ( left.empty? || right.empty? ) do
        subset << (left.first <= right.first ? left.shift : right.shift)
      end
      subset += left + right
      n[offset, width] = subset
      offset += width
    end
    i += 1
  end

  return n
end

再帰なし その2

その1 より泥臭くやってみた。

def msort3(n)
  return n if n.size < 2

  i = 1
  while ( 2**(i-1) < n.size ) do
    res = Array.new(n.size)
    offset = 0
    width = 2**i
    while offset < n.size do
      if ( offset + width/2 ) >= n.size then
        res[offset..-1] = n[offset..-1]
      else
        left = offset
        index = offset
        leftMax = offset + width/2 - 1
        right = leftMax + 1
        rightMax = offset + width - 1
        rightMax = n.size - 1 if rightMax >= n.size
        while ( left<=leftMax && right<=rightMax ) do
          if n[left] <= n[right] then
            res[index] = n[left]
            left += 1
            index += 1
          else
            res[index] = n[right]
            right += 1
            index += 1
          end
        end
        if leftMax-left >= 0 then
          res[index, (leftMax-left+1)] = n[left..leftMax]
          index += (leftMax-left)
        end
        if rightMax-right >= 0 then
          res[index, (rightMax-right+1)] = n[right..rightMax]
        end
      end
      offset += width
    end
    n = res
    i += 1
  end

  return n
end

速度の比較

長さ10000のランダム数列を10個作って、それぞれのソートにかかった時間の合計を比較。

require 'benchmark'

n = Array.new(10) { Array.new(10000) { rand(10000) }

Benchmark.bm(11) do |x|
  x.report("mergeSort1:") { n.each {|i| msort1(i)} }
  x.report("mergeSort2:") { n.each {|i| msort2(i)} }
  x.report("mergeSort3:") { n.each {|i| msort3(i)} }
end

結果

                 user     system      total        real
mergeSort1:  1.718000   0.016000   1.734000 (  1.750000)
mergeSort2:  8.469000   1.156000   9.625000 (  9.672000)
mergeSort3:  3.485000   0.000000   3.485000 (  3.516000)

再帰ありがもっとも高速。再帰なしの場合、泥臭くやったほうが3倍近く速い。

学んだこと

• array[0] より array.first の方が微妙に高速。
• array[0..n] より array.first(n+1) の方が微妙に高速。
• コードの美しさと速度は比例しない。

まとめ

• がんばって再帰なしで書いても遅い時は遅い。でもリソースは節約できてると思う。
• というか、Array#sort の方が 100 倍ぐらい速い。
• ruby で速度比較とかするのは無粋。
• ruby カワユス。