LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@ShotaImoto1(翔太 井本)in株式会社スタメン

アルゴリズムの勉強したので、Rubyで実装してみた

Posted at

対象読者は"ruby BFS"とか"ruby 二分探索"とかで検索してたまたまたどり着いた方向け。

みんなのコンピュータ・サイエンスという書籍(５章)でソートや探索アルゴリズムについて学んだのでRubyで実装してみました。

実装したのアルゴリズムは次の通り

  • 挿入ソート(Insert Sort)
  • 二分探索(Binary Search)
  • 幅優先探索(BFS)
  • 深さ優先探索(DFS)

どんなアルゴリズムなのか？については他のネット記事に筆を譲るとして、今回はrubyでどう実装したのか？ どのように動くのか？について書いてみようと思います。

5.1ソート

挿入ソート

コード

def insert_sort(ary)
  (0..ary.size-1).each do |i|
    (1..i).each.reverse_each do |j|
      break if ary[j-1] < ary[j]
      swap(ary, j-1, j)
    end
  end
end

慣習として、for文はrubyで使われないということなのでループはすべてeachに変更しました。
数字の大きさが順番通りになるまで、入れ替え続ける、という直感的な理解とも一致しているかと思います。

解説

大雑把には、一気にすべてソート対象にせず、最小の範囲からはじめて、
1.ソートする
2.ソート対象を1つ分、広げる
を繰り返すイメージです。

またソート自体は
1.一番新しい値がその一つ手前の値より小さければ、新しい値を一つ前にずらす
2.↑を新しい値が手前の値より大きい状態になるまで繰り返します。

def insert_sort(ary)
  # 配列の前から一定の範囲をソート対象に含めるループ
  (0..ary.size-1).each do |i|
    # 実際にソートするループ
    (1..i).each.reverse_each do |j|
      # 新しい値が手前の値より大きければ、今与えられた範囲でのソートは完了
      break if ary[j-1] < ary[j]
      # 入れ替え操作
      swap(ary, j-1, j)
    end
  end
end

5.2の後に実行ファイルを添付しているので、putsメソッド駆使しながら実際に動かして確認してみてください。

5.2 探索

二分探索

def binary_search(items, key)
  i = items.size / 2
  return items[i] if key == items[i]
  
  if key > items[i]
    sliced = items[i..-1]
  else
    sliced = items[0..i-1]
  end
  binary_search(sliced, key)
end

解説

前提としては、検索対象がソート済みであること。

  i = items.size / 2

渡された配列の半分の位置を取得します

  return items[i] if key == items[i]

取得した位置=真ん中にある値が探している値かどうか確認します

  if key > items[i]

探している値が、先ほど取得した真ん中の値より大きいか小さいか判定します。

# 探している値のほうが大きい場合
    sliced = items[i..-1]

ソート済みなので、探している値は、真ん中の値より後にあるはず。
配列の後ろ半分を取得します。

# 探している値のほうが小さい場合
    sliced = items[0..i-1]

探している値は真ん中の値より前にあるはず。
配列の前半分を取得します。

  binary_search(sliced, key)

取得した配列＝半分になった配列を再度、再帰的に呼び出した二分探索メソッドに渡します。
求める値が見つかるまで、真ん中の値と求める値が一致しているか確認→配列を半分にする、を繰り返します。

実行コード

.rbファイルにコピペして、そのまま実行すると動きます。

実行コード(クリックで開く) 
# ランダム配列の生成
base_ary = (1..100).to_a
ary = base_ary.sample(21)


# 挿入ソート

puts "ソート前：#{ary}\n\n"

def swap(ary, x, y)
  ary[x], ary[y] = ary[y], ary[x]
end

def insert_sort(ary)
  (0..ary.size-1).each do |i|
    (1..i).each.reverse_each do |j|
      break if ary[j-1] < ary[j]
      swap(ary, j-1, j)
    end
  end
end

insert_sort(ary)

puts "\nソート後：#{ary}"


# 二分探索

puts "\n探索(binary_search)"

def binary_search(items, key)
  return "#{key}は存在しません。" if items.size == 0

  i = items.size / 2

  return items[i] if key == items[i]

  if key > items[i]
    sliced = items[i..-1]
    print "検索中...右半分に存在すると判定： "
  else
    sliced = items[0..i-1]
    print "検索中...左半分に存在すると判定： "
  end
  puts "探索中の配列: #{sliced}"

  binary_search(sliced, key)
end

print "探したい数字を入力してください："
key = gets.chomp.to_i

result = binary_search(ary, key)
puts "#{result}が見つかりました！"

5.3 グラフ

Rubyでグラフを扱う

Nodeクラス

class Node
  attr_accessor :key, :value, :connected_nodes

  def initialize(key, value)
    @key = key
    @value = value
    @connected_nodes = [] # Nodeオブジェクトのkeyを格納する
  end

  def connect(key)
    connected_nodes.push(key)
  end
end

Graphクラス

Nodeクラスの集合を格納するためのクラス。
BFSやDFSなどNodeを取り扱うメソッドも後でここに追加します。

class Graph
  attr_accessor :vertices
  def initialize(vertices = [])
    @vertices = vertices
  end

  def self.random_factory(node_amount = 10)
    ary = Array.new(node_amount){ |i| Node.new(i, rand(100)) }
    new(ary)
  end

  def connect(key1, key2)
    if (v1 = find_nodes(key1)) &&  (v2 = find_nodes(key2))
      v1.connect(key2)
      v2.connect(key1)
    else
      false
    end
  end

  def find_nodes(key)
    vertices.find{|v| v.key == key }
  end

  def get_connected_nodes(node)
    keys = node.connected_nodes
    nodes = keys.map{|k| find_nodes(k)}
  end
end

DFS

ベタ書きコード

  def dfs(start_node_key, key)
    next_nodes_stack = []
    seen_nodes = []

    start_node = vertices[start_node_key]

    next_nodes_stack.push(start_node)
    seen_nodes.append(start_node)

    while next_nodes_stack.any?
      node = next_nodes_stack.pop
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        unless seen_nodes.include?(n)
          next_nodes_stack.push(n)
          seen_nodes.append(n)
        end
      end
    end
    return nil
  end

BFS

ベタ書きコード

  def dfs(start_node_key, key)
    next_nodes_stack = []
    seen_nodes = []

    start_node = vertices[start_node_key]

    next_nodes_stack.push(start_node)
    seen_nodes.append(start_node)

    while next_nodes_stack.any?
      node = next_nodes_stack.shift
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        unless seen_nodes.include?(n)
          next_nodes_stack.push(n)
          seen_nodes.append(n)
        end
      end
    end
    return nil
  end

解説

    next_nodes_stack = []
    seen_nodes = []

BFS/DFSともに下記のノードを格納する配列を用意します

  • 探しているノードかどうか、これから確認するノード
  • すでに確認済みのノード
    start_node = vertices[start_node_key]

    next_nodes_queue.push(start_node)
    seen_nodes.append(start_node)

始点となるノードを用意した２つの配列に格納して、ループスタート

# DFS
node = next_nodes_stack.pop

# BFS
node = next_nodes_queue.shift

これから確認するノードを配列から取り出します

      return node if node.key == key

ノードのキーが探しているキーと一致しているか確認

      get_connected_nodes(node).each do |n|

探しているノードでなければ、今見たノードと接続しているノードを配列として呼び出します

        unless seen_nodes.include?(n)
          next_nodes_stack.push(n)
          seen_nodes.append(n)
        end

接続しているノードが確認済みの配列になければ、２つの配列（これから確認する/確認済み）に格納します。

以下、これから確認する配列からノードを取り出すところから、繰り返し。

実装面におけるBFSとDFSの違い

キューかスタックか、これに尽きます
コードでいうと次に確認するノードを配列から取り出すところのみ。

# DFS
node = next_nodes_stack.pop

# BFS
node = next_nodes_queue.shift

確認リストの

  • 後ろから取り出す=スタックの動き
  • 先頭から取り出す=キューの動き

後ろに格納されているのは、先程確認したばかりのノードと接続されているノード。
つまりノードを見たら更にその奥のノードを見ようとする動き＝深さ優先

先頭に格納されているのは、その逆＝広さ優先

どっちの探索方法だと、どういうグラフ構造のときに早い、とかは添付のコードで色々と試してみてください。

リファクタリング後

Nodeクラス

class Node
  attr_accessor :key, :value, :connected_nodes

  def initialize(key, value)
    @key = key
    @value = value
    @connected_nodes = [] # Nodeオブジェクトのkeyを格納する
  end

  def connect(key)
    connected_nodes.push(key)
  end

  # 標準出力用
  def shown_as_search_result
    puts self ? "発見しました！ #{self} { key: #{key}, connected: #{connected_nodes} }" : "見つかりませんでした"
  end
end

Graphクラス

 class Graph
  attr_accessor :nodes
  def initialize(nodes = [])
    @nodes = nodes
  end

  def initialize_search_memory
    @next_nodes = []
    @seen_nodes = []
  end

  def push_memory(node)
    @next_nodes.push(node)
    @seen_nodes.push(node)
  end

  def pop_next_nodes
    @next_nodes.pop
  end

  def dequeue_next_nodes
    @next_nodes.shift
  end

  def saw?(node)
    @seen_nodes.include?(node)
  end

  def next_nodes_exist?
    @next_nodes.any?
  end

  def connect(key1, key2)
    if (v1 = find_node(key1)) && (v2 = find_node(key2))
      v1.connect(key2)
      v2.connect(key1)
    else
      false
    end
  end

  def find_node(key)
    nodes.find{|v| v.key == key }
  end

  def get_connected_nodes(node)
    keys = node.connected_nodes
    nodes = keys.map{|k| find_node(k)}
  end

  # 検索メソッド
  def dfs(start_key, key)
    initialize_search_memory

    start_node = find_node(start_key)
    push_memory(start_node)

    while next_nodes_exist?
      node = pop_next_nodes
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        push_memory(n) unless saw?(n)
      end
    end
  end

  def bfs(start_key, key)
    initialize_search_memory

    start_node = find_node(start_key)
    push_memory(start_node)

    while next_nodes_exist?
      node = dequeue_next_nodes
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        push_memory(n) unless saw?(n)
      end
    end
  end

  # ランダムにグラフを生成するメソッド
  def self.random_factory(node_amount = 10)
    ary = Array.new(node_amount){ |i| Node.new(i, rand(100)) }
    new(ary)
  end

  # ランダムにノードを接続する一連のメソッド
  def node_keys
    nodes.map{|v| v.key}
  end

  def random_connectors
    node_keys.combination(2).to_a
  end

  def generate_random_connection(connection_amount)
    random_ary = random_connectors.sample(connection_amount)
    random_ary.each {|c| connect(c[0], c[1])}
  end
end

※DFSとBFS別々に書いていますが、先述の通り、popかdequeueかだけ変えられるようにすればDRYに書けそうです。

実行

# グラフの生成とノード間の接続
@gragh = Graph.random_factory(10)
@gragh.generate_random_connection(20)

# DFS実行
@gragh.dfs(0, 3)

# BFS実行
@gragh.dfs(0, 3)

実行コード

.rbファイルにコピペして、そのまま実行すると動きます。

実行コード(クリックで開く) 
 class Graph
  attr_accessor :nodes
  def initialize(nodes = [])
    @nodes = nodes
  end

  def initialize_search_memory
    @next_nodes = []
    @seen_nodes = []
  end

  def push_memory(node)
    @next_nodes.push(node)
    @seen_nodes.push(node)
  end

  def pop_next_nodes
    @next_nodes.pop
  end

  def dequeue_next_nodes
    @next_nodes.shift
  end

  def saw?(node)
    @seen_nodes.include?(node)
  end

  def next_nodes_exist?
    @next_nodes.any?
  end

  def connect(key1, key2)
    if (v1 = find_node(key1)) && (v2 = find_node(key2))
      v1.connect(key2)
      v2.connect(key1)
    else
      false
    end
  end

  def find_node(key)
    nodes.find{|v| v.key == key }
  end

  def get_connected_nodes(node)
    keys = node.connected_nodes
    nodes = keys.map{|k| find_node(k)}
  end

  # 検索メソッド
  def dfs(start_key, key)
    initialize_search_memory

    start_node = find_node(start_key)
    push_memory(start_node)

    while next_nodes_exist?
      node = pop_next_nodes
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        push_memory(n) unless saw?(n)
      end
    end
  end

  def bfs(start_key, key)
    initialize_search_memory

    start_node = find_node(start_key)
    push_memory(start_node)

    while next_nodes_exist?
      node = dequeue_next_nodes
      return node if node.key == key
      get_connected_nodes(node).each do |n|
        push_memory(n) unless saw?(n)
      end
    end
  end

  # ランダムにグラフを生成するメソッド
  def self.random_factory(node_amount = 10)
    nodes = Array.new(node_amount) do |i|
      Node.new(i, rand(100))
    end
    new(nodes)
  end

  # ランダムにノードを接続する一連のメソッド
  def node_keys
    nodes.map{|v| v.key}
  end

  def random_connectors
    node_keys.combination(2).to_a
  end

  def generate_random_connection(connection_amount)
    random_ary = random_connectors.sample(connection_amount)
    random_ary.each {|c| connect(c[0], c[1])}
  end

  # 標準出力用メソッド
  def show_nodes
    puts "<ノード一覧>"
    nodes.map{|v| puts "key: #{v.key}, connected: #{v.connected_nodes}"}
  end
end

class Node
  attr_accessor :key, :value, :connected_nodes

  def initialize(key, value)
    @key = key
    @value = value
    @connected_nodes = [] # Nodeオブジェクトのkeyを格納する
  end

  def connect(key)
    connected_nodes.push(key)
  end

  # 標準出力用
  def shown_as_search_result
    puts self ? "発見しました！ #{self} { key: #{key}, connected: #{connected_nodes} }" : "見つかりませんでした"
  end
end

@gragh = Graph.random_factory(10)
@gragh.generate_random_connection(20)

puts "\n"
@gragh.show_nodes
puts "\n"

puts "DFS実行\n-------------------------------"
found_node = @gragh.dfs(0, 3)
found_node.shown_as_search_result

puts "\n"
@gragh.show_nodes
puts "\n"

puts "BFS実行\n-------------------------------"
found_node = @gragh.bfs(0, 3)
found_node.shown_as_search_result

感想

自分の勉強も兼ねて、書籍に例示されていたものをrubyで書きました。
実際に動かすことで、動きを感覚的につかめるのもあるし、rubyナイズして書くことでruby自体のメソッドの勉強にもなりました。
気が向いたらまた、やってみようとおもいます。

書籍自体もおすすめなのでぜひ。

2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?