M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

二分探索

二分探索 (binary search) はデータ数を N とすると log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめソートしておく必要があります。

 [11 22 33 44 55 66 77 88 99]        key は 66
              ↑                     66 > 55 後半を探す

 11 22 33 44 55 [66 77 88 99]        88 > 66 前半を探す
                       ↑

 11 22 33 44 55 [66 77] 88 99        77 > 66 前半を探す
                    ↑

 11 22 33 44 55 [66] 77 88 99        66 = 66 発見
                 ↑

                  図 : 二分探索の動作

二分探索は探索する区間を半分に分けて調べます。キーが 66 の場合を考えてみます。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索します。あとは、これと同じことを後半部分に対して行います。最後には区間の要素がひとつしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。

●プログラム1

#
# bsearch.rb : 二分探索
#
def bsearch(x, buff)
  low = 0
  high = buff.size - 1
  while low <= high
    mid = (low + high) / 2
    if x == buff[mid]
      return true
    elsif x > buff[mid]
      low = mid + 1
    else
      high = mid - 1
    end
  end
  false
end

# テスト
if __FILE__ == $0
  a = (1 ... 5).to_a
  for x in [0, 1, 2.5, 3, 4, 5]
    print x, " ", bsearch(x, a), "\n"
  end
end

●実行例1

0 false
1 true
2.5 false
3 true
4 true
5 false

●プログラム2

#
# sortary.rb : ソート済み配列
#
#              Copyright (C) 2006 Makoto Hiroi
#
class SortedArray
  include Enumerable
  
  def initialize(ary = [])
    @ary = ary.sort
  end
  
  private
  def bsearch(x, buff)
    low = 0
    high = buff.size - 1
    while low <= high
      mid = (low + high) / 2
      if x == buff[mid]
        return mid
      elsif x > buff[mid]
        low = mid + 1
      else
        high = mid - 1
      end
    end
    low
  end
  
  public
  # 参照
  def [](n)
    @ary[n]
  end
  
  # 探索
  def search(data)
    if @ary != []
      n = bsearch(data, @ary)
      data if data == @ary[n]
    end
  end
  
  # 挿入
  def insert(data)
    if @ary == []
      @ary[0] = data
    else
      n = bsearch(data, @ary)
      if @ary[n] != data
        @ary.insert(n, data)
        data
      end
    end
  end
  
  # 削除
  def delete(data)
    if @ary != []
      n = bsearch(data, @ary)
      @ary.delete_at(n) if data == @ary[n]
    end
  end
  
  # Enumberable 用
  def each(&block)
    @ary.each(&block)
  end
end

# テスト
if __FILE__ == $0
  a = SortedArray.new
  10.times do |x|
    puts a.insert(x)
  end
  10.times do
    n = rand(10)
    if a.search(n)
      print "found ", n, "\n"
      a.delete(n)
    else
      print "not found ", n, "\n"
    end
  end
end

●実行例2

0
1
2
3
4
5
6
7
8
9
found 5
found 7
found 0
not found 7
found 8
not found 8
found 6
not found 0
not found 7
not found 0

二分木

「木構造 (tree structer) 」は「木 (tree) 」とも呼ばれるデータ構造で、節 (ノード) と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート) 」と呼ばれる節が存在します。

          (root)
            A    ────────  レベル0
          /|\                ↑
        /  |  \
      B    C    D            木  レベル1
    /|\        |\          の
  /  |  \      |  \        高
E    F    G    H    I      さ  レベル2
          /  \
        /      \              ↓
      J          K    ─────  レベル3


        図 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。

木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。

ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J, K の親で、J は G の子になります。J は子を持っていないので葉となります。

子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「 n 分木」と呼びます。とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。

                    (root)
                      18
                    /  \
                  /      \
                /          \
              /              \
            /                  \
          14                      22
        /  \                  /  \
      /      \              /      \
    12          16          20          24
  /  \      /  \      /  \      /  \
11      13  15      17  19      21  23      25


             図 : 二分木の一例

上図に二分木の例を示します。二分木では、節にひとつのデータを格納します。そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配置されるように木を構成します。

この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。

二分探索木の探索は二分探索と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。

データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log 2 N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。

ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。有名なところでは AVL 木、2 色木 (赤黒木)、2-3 木、B 木、B* 木などがあります。

●参考文献

  1. A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
  2. 近藤嘉雪, 『Cプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998

●プログラム

#
# bintree.rb : 二分木
#
#              Copyright (C) 2006 Makoto Hiroi
#

# 節の定義
class Node
  attr_accessor :data, :left, :right
  
  def initialize(data, left = nil, right = nil)
    @data = data
    @left = left
    @right = right
  end
end

# 二分木
class BinTree
  include Enumerable
  def initialize
    @root = nil
  end

  private
  # 探索
  def _search(node, data)
    while node
      if node.data == data
        return node
      elsif data < node.data
        node = node.left
      else
        node = node.right
      end
    end
    nil
  end

  # 挿入
  def _insert(node, new_node)
    if node == nil
      new_node
    else
      if new_node.data < node.data
        node.left = _insert(node.left, new_node)
      elsif new_node.data > node.data
        node.right = _insert(node.right, new_node)
      end
      node
    end
  end

  # 最小値を求める
  def _search_min(node)
    if node.left == nil
      node.data
    else
      _search_min(node.left)
    end
  end

  # 最小値を削除
  def _delete_min(node)
    if node.left == nil
      node = node.right
    else
      node.left = _delete_min(node.left)
    end
    node
  end

  # 削除
  def _delete(node, data)
    if node
      if data < node.data
        node.left = _delete(node.left, data)
      elsif data > node.data
        node.right = _delete(node.right, data)
      else
        if node.left == nil
          return node.right
        elsif node.right == nil
          return node.left
        else
          node.data = _search_min(node.right)
          node.right = _delete_min(node.right)
        end
      end
    end
    node
  end

  # 右回転
  def _rotate_right(node)
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    lnode
  end

  # 左回転
  def _rotate_left(node)
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    rnode
  end
  
  # 巡回
  def _traverse(node, &block)
    if node
      _traverse(node.left, &block)
      yield node.data
      _traverse(node.right, &block)
    end
  end

  public
  # 挿入
  def insert(data)
    @root = _insert(@root, Node.new(data))
  end
  
  # 探索
  def search(data)
    x = _search(@root, data)
    x.data if x
  end
  
  # 削除
  def delete(data)
    @root = _delete(@root, data)
    nil
  end
  
  # Enumerable 用
  def each(&block)
    _traverse(@root, &block)
  end
  
  # 文字列に変換
  def to_s
    if @root
      str = "("
      _traverse(@root) do |x|
        str << x.to_s
        str << ","
      end
      str[-1] = ")"
    else
      str = "()"
    end
    str
  end
end

# テスト
if __FILE__ == $0
  a = BinTree.new
  10.times do
    a.insert(rand(100))
  end
  puts a
  for x in a.to_a
    print "search ", x, " ", a.search(x), "\n"
    print "delete ", x, " "
    a.delete(x)
    print a.search(x), "\n"
    puts a
  end
end

●実行例

(5,25,27,30,73,79,94,95,97)
search 5 5
delete 5 nil
(25,27,30,73,79,94,95,97)
search 25 25
delete 25 nil
(27,30,73,79,94,95,97)
search 27 27
delete 27 nil
(30,73,79,94,95,97)
search 30 30
delete 30 nil
(73,79,94,95,97)
search 73 73
delete 73 nil
(79,94,95,97)
search 79 79
delete 79 nil
(94,95,97)
search 94 94
delete 94 nil
(95,97)
search 95 95
delete 95 nil
(97)
search 97 97
delete 97 nil
()

ヒープ

「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きい、という関係を満たすように作ります。「半順序木」の場合、親は子より小さいか等しい、という関係を満たすように作ります。したがって、木の根(配列の添字 0)には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。

            0  1  2  3  4  5  6
    TABLE [10 20 30 40 50 60 70]

         (root)
           10 (0)
         /   \            親の添字を k とすると
       /       \          その子は 2*k+1, 2*k+2 になる。
     20 (1)       30 (2)    親の値 < 子の値 の関係を満たす。
   /  \       /  \
 40     50   60      70
 (3)    (4)  (5)     (6)

    図 : ヒープと配列の対応関係

ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (n) の対数 (log2 n) に比例する程度の時間で済みます。

●参考文献

  1. A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
  2. 近藤嘉雪, 『Cプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998

●プログラム

#
# heap.rb : ヒープ
#
#           Copyright (C) 2006 Makoto Hiroi
#
class Heap
  def initialize(ary = [])
    @buff = ary.dup
    (@buff.size / 2 - 1).downto(0) do |n|
      reheap_to_leaf(@buff, n)
    end
  end
  
  private
  def reheap_to_leaf(ary, n)
    loop do
      c = 2 * n + 1
      break if c >= ary.size
      if c + 1 < ary.size
        c += 1 if ary[c] > ary[c + 1]
      end
      break if ary[n] <= ary[c]
      temp = ary[n]
      ary[n] = ary[c]
      ary[c] = temp
      n = c
    end
  end
  
  def reheap_to_root(ary, n)
    loop do
      p = (n - 1) / 2
      break if p < 0 || ary[p] <= ary[n]
      temp = ary[n]
      ary[n] = ary[p]
      ary[p] = temp
      n = p
    end
  end
  
  public
  # 最小値を取り出す
  def delete_min
    return nil if @buff.empty?
    value = @buff[0]
    last = @buff.pop
    if @buff.size > 0
      @buff[0] = last
      reheap_to_leaf(@buff, 0)
    end
    value
  end
  
  # データの挿入
  def insert(data)
    @buff << data
    reheap_to_root(@buff, @buff.size - 1)
  end
end

# テスト
if __FILE__ == $0
  a = Array.new(20)
  a.map! do rand(1000) end
  b = Heap.new(a)
  while (c = b.delete_min)
    print c, " "
  end
  print "\n"
  20.times do b.insert(rand(1000)) end
  while (c = b.delete_min)
    print c, " "
  end
  print "\n"
end

●実行例

72 88 160 180 181 232 263 333 346 468 516 526 534 554 651 666 717 835 913 919 
27 35 36 39 60 72 127 163 199 320 582 686 719 743 831 834 873 907 911 981 

ハッシュ法

ハッシュ法 (hashing) は高速なデータ検索アルゴリズムです。ハッシュ法はハッシュ表 (hash table) と呼ばれるデータを格納する配列と、データを数値に変換するハッシュ関数 (hash function) を用意します。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値をハッシュ値 (hash value) と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性があります。これをハッシュ値の衝突 (collision) といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

第 1 の方法はハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納する工夫が必要になります。このときよく利用されるデータ構造が連結リストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。これをチェイン法といいます。

第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。新しい場所を探すといっても、ハッシュ表の先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。これをオープンアドレス法といいます。

●参考文献

  1. A.V. Aho, J.E. Hopcroft, J.D. Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
  2. 近藤嘉雪, 『Cプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998

●プログラム1

#
# hash1.rb : チェイン法
#
#            Copyright (C) 2006 Makoto Hiroi
#
class MyHash1
  include Enumerable
  
  HASH_SIZE = 8191  # 素数
  def initialize
    @hash_table = Array.new(HASH_SIZE)
  end
  
  private
  # ハッシュ関数(適当です)
  def hash_func(key)
    value = 0
    for x in 0 ... key.size
      value = (value << 3) ^ key[x]
    end
    value % HASH_SIZE
  end
  
  public
  # 探索 (key は sequence のみ)
  def search(key)
    value = hash_func(key)
    if @hash_table[value]
      pair = @hash_table[value].assoc(key)
      return pair[1] if pair
    end
  end
  
  # 挿入
  def insert(key, data)
    value = hash_func(key)
    if @hash_table[value]
      pair = @hash_table[value].assoc(key)
      if pair
        pair[1] = data
      else
        @hash_table[value] << [key, data]
      end
    else
      @hash_table[value] = [[key, data]]
    end
  end
  
  # 削除
  def delete(key)
    value = hash_func(key)
    data = nil
    if @hash_table[value]
      @hash_table[value].delete_if do |x|
        if key == x[0] then data = x[1] end
      end
    end
    data
  end
  
  # Enumerable 用
  def each
    @hash_table.each do |x|
      if x
        x.each do |y| yield y.dup end
      end
    end
  end
end

# テスト
if __FILE__ == $0
  a = MyHash1.new
  10.times do
    key = sprintf("%d", rand(100000))
    value = rand(100)
    a.insert(key, value)
  end
  for x in a.to_a
    key, value = x
    print "search ", key, " ", a.search(key), "\n"
    print "delete ", key, " ", a.delete(key), " ", a.search(key), "\n"
  end
end

●実行例1

search 6053 80
delete 6053 80 nil
search 45270 61
delete 45270 61 nil
search 82708 85
delete 82708 85 nil
search 42176 79
delete 42176 79 nil
search 59791 67
delete 59791 67 nil
search 60950 81
delete 60950 81 nil
search 35202 53
delete 35202 53 nil
search 48760 38
delete 48760 38 nil
search 9475 88
delete 9475 88 nil
search 31204 34
delete 31204 34 nil

●プログラム2

#
# hash2.rb : オープンアドレス法
#
#            Copyright (C) 2006 Makoto Hiroi
#
class MyHash2
  include Enumerable
  
  # :_my_hash_empty  空き
  # :_my_hash_delete 削除
  HASH_SIZE = 8191  # 素数
  def initialize
    @hash_key_table = Array.new(HASH_SIZE, :_my_hash_empty)
    @hash_data_table = Array.new(HASH_SIZE)
  end
  
  private
  # ハッシュ関数
  def hash_func(key)
    value = 0
    for x in 0 ... key.size
      value = (value << 3) ^ key[x]
    end
    value % HASH_SIZE
  end
  
  # 再ハッシュ (1 次ハッシュ法)
  def next_func(value)
    (value + 1) % HASH_SIZE
  end
  
  public
  # 探索 (key は sequence のみ)
  def search(key)
    value = hash_func(key)
    count = 0
    begin
      key1 = @hash_key_table[value]
      if key1 == key
        return @hash_data_table[value]
      elsif key1 == :_my_hash_empty
        return nil
      end
      value = next_func(value)
      count += 1
    end while count < HASH_SIZE
  end
  
  # 挿入
  def insert(key, data)
    value = hash_func(key)
    count = 0
    begin
      key1 = @hash_key_table[value]
      if key1 == :_my_hash_empty || key1 == :_my_hash_delete
        @hash_key_table[value] = key
        @hash_data_table[value] = data
        return data
      end
      count += 1
      value = next_func(value)
    end while count < HASH_SIZE
  end
  
  # 削除
  def delete(key)
    value = hash_func(key)
    count = 0
    begin
      key1 = @hash_key_table[value]
      if key1 == key
        @hash_key_table[value] = :_my_hash_delete
        return @hash_data_table[value]
      elsif key1 == :_my_hash_empty
        return nil
      end
      value = next_func(value)
      count += 1
    end while count < HASH_SIZE
  end
  
  # Enumerable 用
  def each
    for x in 0 ... HASH_SIZE
      key = @hash_key_table[x]
      if key != :_my_hash_empty && key != :_my_hash_delete
        yield [key, @hash_data_table[x]]
      end
    end
  end
end

# テスト
if __FILE__ == $0
  a = MyHash2.new
  10.times do
    key = sprintf("%d", rand(100000))
    value = rand(100)
    a.insert(key, value)
  end
  for x in a.to_a
    key, value = x
    print "search ", key, " ", a.search(key), "\n"
    print "delete ", key, " ", a.delete(key), " ", a.search(key), "\n"
  end
end

●実行例2

search 6333 74
delete 6333 74 nil
search 42146 76
delete 42146 76 nil
search 63436 66
delete 63436 66 nil
search 40190 29
delete 40190 29 nil
search 1261 7
delete 1261 7 nil
search 1364 70
delete 1364 70 nil
search 1174 85
delete 1174 85 nil
search 55810 20
delete 55810 20 nil
search 29378 90
delete 29378 90 nil
search 70959 69
delete 70959 69 nil

●実行例3

#
# ソート済み配列、二分木、ハッシュ法のテストプログラム
#
require "hash1"
require "hash2"
require "sortary"
require "bintree"

class MyHash1
  alias []  search
  alias []= insert
end

class MyHash2
  alias []  search
  alias []= insert
end

class Array
  def <(b)
    self.<=>(b) < 0
  end
  def >(b)
    self.<=>(b) > 0
  end
end

def test1(a)
  count = 0
  srand(0)
  s = Time.now
  while count < 5000
    b = [rand(256), rand(256), rand(256)]
    unless a[b]
      a[b] = true
      count += 1
    end
  end
  e = Time.now
  print e - s, "\n"
end

def test2(a)
  count = 0
  srand(0)
  s = Time.now
  while count < 5000
    b = [rand(256), rand(256), rand(256)]
    unless a.search(b)
      a.insert(b)
      count += 1
    end
  end
  e = Time.now
  print e - s, "\n"
end

def test3(a)
  count = 0
  srand(0)
  s = Time.now
  while count < 5000
    b = [rand(256), rand(256), rand(256)]
    unless a.member?(b)
      a << b
      count += 1
    end
  end
  e = Time.now
  print e - s, "\n"
end

test1({})
test1(MyHash1.new)
test1(MyHash2.new)
test2(BinTree.new)
test2(SortedArray.new)
test3([])
# 実行時間
# (単位;秒, Windows XP, Celeron 1.40 GHz, Ruby 1.8.3)
Hash   MyHash1  MyHash2  BinTree  SArray  Array
0.052  0.141    0.188    0.610    0.672   7.953

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]