M.Hiroi's Home Page

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

ソート

基数ソートのプログラムです。

●プログラム


# 基数ソート (32 bit 無符号整数専用)
def radix_sort(buff)
  count = Array.new(256)
  cumul = Array.new(256)
  work  = Array.new(buff.size)
  # 1 byte ずつ分布数えソート
  for i in 0 ... 4
    shift = i * 8
    count.fill(0)
    buff.each do |x|
      count[(x >> shift) & 0xff] += 1
    end
    sum = 0
    for x in 0 ... 256
      sum += count[x]
      cumul[x] = sum
    end
    x = buff.size - 1
    while x >= 0
      y = (buff[x] >> shift) & 0xff
      cumul[y] -= 1
      work[ cumul[y] ] = buff[x]
      x -= 1
    end
    temp = buff
    buff = work
    work = temp
  end
end

# 基数ソート (基数交換法1)
def radix_sort2(buff, low, high, n)
  return if low >= high || n == 0
  i = low
  j = high
  loop do
    i += 1 while i <= j && buff[i] & n == 0
    j -= 1 while i <= j && buff[j] & n > 0
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  radix_sort2(buff, low, j, n >> 1)
  radix_sort2(buff, i, high, n >> 1)
end

# 基数ソート (基数交換法2)
def radix_sort3(buff, low, high, n)
  return if n == 0
  if high - low <= LIMIT
    insert_sort2(buff, low, high)
    return
  end
  i = low
  j = high
  loop do
    i += 1 while i <= j && buff[i] & n == 0
    j -= 1 while i <= j && buff[j] & n > 0
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  radix_sort3(buff, low, j, n >> 1)
  radix_sort3(buff, i, high, n >> 1)
end

Multikey Quicksort

マルチキークイックソート (Multikey Quicksort) は 1997 年に Jon Bentley と Robert Sedgewick が発表した文字列のソートに適した高速なアルゴリズムです。マルチキークイックソートで文字列をソートする場合、普通のクイックソートと大きく異なる点が 2 つあります。ひとつは文字単位で比較を行うことです。文字列をソートする場合、一般的なソートは文字列単位で比較を行います。ところが、マルチキークイックソートは最初に 1 文字目を比較してソートを行い、ソートが完了しない場合(同じ値が複数ある場合)は、さらに 2 文字目を比較してソートを行う、というように先頭から順番に文字を比較してソートを行います。

もうひとつは区間の分け方です。普通のクイックソートは枢軸を基準にして、小さいデータと大きいデータの 2 つの区間に分割していくことでソートを行います。マルチキークイックソートは枢軸を基準にするところは同じですが、区間を 2 分割するのではなく、小さいデータ、枢軸と等しいデータ、大きいデータの 3 分割にするところが特徴です。このため、マルチキークイックソートは Ternary Quicksort とも呼ばれています。

たとえば、n 番目の文字を比較して区間を 3 分割したとしましょう。小さいデータと大きいデータの区間は n 番目の文字でソートを続行すればいいですね。これは普通のクイックソートと同じです。枢軸と等しいデータが複数ある場合、n 番目の文字ではソートが完了しないので、次は n + 1 番目の文字を比較してソートを行います。このように枢軸と等しいデータを集めることで、その区間は次の文字へ進めることができるわけです。

このアルゴリズムを疑似コードでプログラムすると、次のようになります。

# Multikey Quicksort の擬似コード

def multikey_quicksort(low, high, n)
  if 区間のデータ数が NUM 以下
    単純なソートアルゴリズムに切り替えてソート
  else
    n 番目の文字で枢軸を選択して low - high を 3 分割する
    (< : low - m1-1, = : m1 - m2-1, > : m2 - high)
    multikey-quicksort(low, m1 - 1, n) 
    if n 番目の文字 != 終端記号
      multikey-quicksort( m1, m2 - 1, n + 1 )
    end
    multikey-quick( m2, high, n )
  end
end

マルチキークイックソートは再帰呼び出しを使うと簡単にプログラムできます。区間を low と high で表し、比較する文字の位置を n で表します。区間のデータ数が一定の個数 (NUM) 以下になったら、単純なソートアルゴリズムに切り替えます。この方が少しだけ速くなります。

n 番目の文字で区間を 3 分割したら、multikey-quicksort を再帰呼び出しします。このとき、枢軸より小さい区間 (low - m1-1) と大きい区間 (m2 - high) は n 番目の文字でソートを続行します。等しい区間 (m1 - m2-1) は n + 1 番目の文字へ進めてソートを行います。もしも、等しい区間の文字 (枢軸) が終端文字であれば、文字列を最後まで比較したので再帰呼び出しは行いません。つまり、同じ文字列が複数個あるということです。

●参考文献

  1. Jon Bentley, Robert Sedgewick, "Fast Algorithms for Sorting and Searching Strings", Sorting and Searching Strings, 1977

●プログラム

文字列の比較関数 compare を用意して、クイックソートとマルチキークイックソートの実行速度を比較します。文字列の比較に時間がかかる場合はマルチキークイックソートの方が速いのですが、そうでない場合はクイックソートの方が速くなります。

#
# mqsort.rb : Multikey Quicksort
#
#            Copyright (C) 2006 Makoto Hiroi
#
LIMIT = 10

# 文字列の終端を nil で判定する
def nil.coerce(n)
  [n, -1]
end

def nil.-(n)
  -1 - n
end

# 文字列の比較
def compare(s1, s2, depth = 0)
  for x in depth .. s1.size
    r = s1[x] - s2[x]
    return r if r != 0
  end
  0
end

# 挿入ソート
def insert_sort(buff, low, high, depth = 0)
  for i in low+1 .. high
    temp = buff[i]
    j = i - 1
    while j >= low && compare(temp, buff[j], depth) < 0
      buff[j + 1] = buff[j]
      j -= 1
    end
    buff[j + 1] = temp
  end
end

# クイックソート
def quick_sort(buff)
  low_stack = []
  high_stack = []
  low = 0
  high = buff.size - 1
  loop do
    loop do
      if high - low <= LIMIT
        insert_sort(buff, low, high)
        break
      end
      p = buff[low + rand(high - low)]
      i = low
      j = high
      loop do
        i += 1 while compare(buff[i], p) < 0
        j -= 1 while compare(buff[j], p) > 0
        break if i >= j
        temp = buff[i]
        buff[i] = buff[j]
        buff[j] = temp
        i += 1
        j -= 1
      end
      if i - low > high - j
        low_stack << low
        high_stack << (i - 1)
        low = j + 1
      else
        low_stack << (j + 1)
        high_stack << high
        high = i - 1
      end
    end
    break if low_stack.empty?
    low = low_stack.pop
    high = high_stack.pop
  end
end

# マルチキークイックソート
def mqsort(buff, low, high, depth)
  if high - low <= LIMIT
    insert_sort(buff, low, high, depth)
    return
  end
  p = buff[low + rand(high - low)][depth]
  # 最初は 4 分割
  # low - m1-1 (p) | m1 - j | i - m2 | m2+1 - high (p)
  i = m1 = low
  j = m2 = high
  while true
    while i <= j
      k = buff[i][depth] - p
      break if k > 0
      if k == 0
        temp = buff[i]
        buff[i] = buff[m1]
        buff[m1] = temp
        m1 += 1
      end
      i += 1
    end
    while i <= j
      k = buff[j][depth] - p
      break if k < 0
      if k == 0
        temp = buff[j]
        buff[j] = buff[m2]
        buff[m2] = temp
        m2 -= 1
      end
      j -= 1
    end
    break if i > j
    temp = buff[i]
    buff[i] = buff[j]
    buff[j] = temp
    i += 1
    j -= 1
  end
  # 枢軸と等しいデータを中央に集める
  k = if m1 - low < i - m1 then m1 - low else i - m1 end
  for l in 0 ... k
    temp = buff[low + l]
    buff[low + l] = buff[j - l]
    buff[j - l] = temp
  end
  m1 = low + (i - m1)
  k = if high - m2 < m2 - j then high - m2 else m2 - j end
  for l in 0 ... k
    temp = buff[high - l]
    buff[high - l] = buff[i + l]
    buff[i + l] = temp
  end
  m2 = high - (m2 - j) + 1
  # m1 - m2-1 が等しいデータ
  mqsort(buff, low, m1 - 1, depth)
  if buff[m1][depth]
    mqsort(buff, m1, m2 - 1, depth + 1)
  end
  mqsort(buff, m2, high, depth)
end


if __FILE__ == $0
  4.times do |i|
    n = 2000 * (i + 1)
    a = []
    n.times do
      a << rand(0xffffffff).to_s
    end
    print n, ": " 
    b = a.dup
    s = Time.now
    mqsort(b, 0, b.size - 1, 0)
    e = Time.now
    print e - s, " "
    
    c = a.dup
    s = Time.now
    quick_sort(c)
    e = Time.now
    print e - s, "\n"
    d = a.sort
    print "error\n" if b != d || c != d
  end
end

●実行例

      mqsort  quick
--------------------
2000: 0.125   0.344
4000: 0.297   0.750
6000: 0.422   1.250
8000: 0.563   1.782

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]