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

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

[みんなのコンピュータ・サイエンス](https://www.amazon.co.jp/%E3%81%BF%E3%82%93%E3%81%AA%E3%81%AE%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9-WladstonFerreiraFilho-ebook/dp/B07KXP79Y9/ref=sr_1_1?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&dchild=1&keywords=%E3%81%BF%E3%82%93%E3%81%AA%E3%81%AE%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9&qid=1607764381&sr=8-1)という書籍(５章)でソートや探索アルゴリズムについて学んだのでRubyで実装してみました。

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

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

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

# 5.1ソート
## 挿入ソート

### コード
```ruby
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.↑を新しい値が手前の値より大きい状態になるまで繰り返します。


```ruby:
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 探索
## 二分探索

```ruby
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
```

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

```ruby:
  i = items.size / 2
```
渡された配列の半分の位置を取得します

```ruby:
  return items[i] if key == items[i]
```
取得した位置=真ん中にある値が探している値かどうか確認します

```ruby:
  if key > items[i]
```
探している値が、先ほど取得した真ん中の値より大きいか小さいか判定します。

```ruby:
# 探している値のほうが大きい場合
    sliced = items[i..-1]
```
ソート済みなので、探している値は、真ん中の値より後にあるはず。
配列の後ろ半分を取得します。

```ruby:
# 探している値のほうが小さい場合
    sliced = items[0..i-1]
```
探している値は真ん中の値より前にあるはず。
配列の前半分を取得します。

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

# 実行コード
.rbファイルにコピペして、そのまま実行すると動きます。
<details>
<summary>実行コード(クリックで開く)</summary>
<div>

```ruby:
# ランダム配列の生成
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}が見つかりました！"

```

</div>
</details>

# 5.3 グラフ
## Rubyでグラフを扱う
### Nodeクラス
```ruby:
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を取り扱うメソッドも後でここに追加します。

```ruby:
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
### ベタ書きコード

```ruby
  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
### ベタ書きコード
```ruby
  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
```

### 解説
```ruby:
    next_nodes_stack = []
    seen_nodes = []
```
BFS/DFSともに下記のノードを格納する配列を用意します
- 探しているノードかどうか、これから確認するノード
- すでに確認済みのノード

```ruby:
    start_node = vertices[start_node_key]

    next_nodes_queue.push(start_node)
    seen_nodes.append(start_node)
```
始点となるノードを用意した２つの配列に格納して、ループスタート

```ruby:
# DFS
node = next_nodes_stack.pop

# BFS
node = next_nodes_queue.shift
```

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

```ruby:
      return node if node.key == key
```

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

```ruby:
      get_connected_nodes(node).each do |n|
```
探しているノードでなければ、今見たノードと接続しているノードを配列として呼び出します

```ruby:
        unless seen_nodes.include?(n)
          next_nodes_stack.push(n)
          seen_nodes.append(n)
        end
```
接続しているノードが確認済みの配列になければ、２つの配列（これから確認する/確認済み）に格納します。


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

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

```ruby:
# DFS
node = next_nodes_stack.pop

# BFS
node = next_nodes_queue.shift
```
確認リストの
- 後ろから取り出す=スタックの動き
- 先頭から取り出す=キューの動き

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

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

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

## リファクタリング後
### Nodeクラス
```ruby:
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クラス
```ruby:
 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に書けそうです。


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

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

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

### 実行コード
.rbファイルにコピペして、そのまま実行すると動きます。
<details>
<summary>実行コード(クリックで開く)</summary>
<div>

```ruby:
 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
```

</div>
</detail>


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

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