f:id:imtstmn:20210323175026p:plain

スタメンエンジニアの井本です。普段の業務ではRuby on Railsを用いた機能開発を担当しています。前職である電気回路の設計エンジニアからWebエンジニアに転身し、11月から働いています。

スタメンでは、エンジニアの技術力向上に力を入れており、社内勉強会を積極的に実施しています。今回は、私が11月〜12月に参加した「みんなのコンピュータ・サイエンス勉強会」についての記事です。

当記事のトピックは大きく2つ。 1. 勉強会のレポート 2. 勉強会の中でRubyで実装したアルゴリズムについて

1においては、エンジニアとしてスタメンで働くことで、どのような環境でどう成長できるか？イメージする一助となれば幸いです。 2は、Rubyならこう書く、といった技術寄りのコンテンツです。

勉強会レポート

テキスト

みんなのコンピュータサイエンス(翔泳社)

内容

計算量
データ構造
アルゴリズム(ソート、探索)
データベース(リレーショナル、非リレーショナル、分散データベース、データの一貫性)
コンピュータ(アーキテクチャ、コンパイラ)

所感

大学時代の専攻や前職で、アルゴリズムやデータベースについては、学ぶ機会がありましたが、あくまで知識として持っているに過ぎませんでした。今回の勉強会で何より良かったことは、先輩エンジニアに質問しながら理解を深めることができた点です。このため、今回の勉強会を通して、Webエンジニアの立場でどう実現するのか、選択していくのか等、以前よりも実務をイメージしながら学ぶことができました。

業務に活かせていること

計算量を意識できるようになった

明らかに計算量が増えるような構造に注意が向くようになりました。例えば、eachなどリストを扱うメソッドをネストする、といったコードを、Webエンジニアデビューする前には気にせず書いていたものです…。

Rubyならではの書き方に関心が向くきっかけとなった

教材の書籍においては、例で掲載されているコードは、擬似コードを用いているため、経験の浅い私には少々イメージがしづらいところがありました。そこでアルゴリズムの章では、自らRubyで実装しました。

実際に動かすことでアルゴリズムの動きを感覚的に理解ができただけでなく、コードレビューをもらうことで、Rubyらしいシンプルな実装を学ぶことができました。

Rubyで書くコードの明快さと、自身が書くコードの不明瞭さに気づくことができました。

この時に書いたコードに関するコードについては、次のトピックで実際に触れて参ります。

Rubyによる各種アルゴリズムの実装

すべて載せてしまうと、相当な文量となってしまうので、Rubyで実装することで違いが顕著だったコードのうち2つをピックアップします。

挿入ソート

テキストのコード

function insertion_sort(list)
  for i ← 2 ... list.length
    j ← i
    while j and list[j-1] > list[j]
      list.swap_items(j, j-1)
      j ← j - 1

Rubyで動作のみを再現したコード

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

def insert_sort(ary)
  for i in 1..(ary.length - 1)
    j = i
    while  j > 0 && ary[j-1] > ary[j]
      swap(ary, j-1, j)
      j = j - 1
    end
  end
end

リファクタリング後

ary = # ランダム数列

module Sortable
  def swap!(i, j)
    self[i], self[j] = self[j], self[i]
  end

  def insert_sort
    0.upto self.size-1 do |i|
      i.downto 1 do |j|
        break if self[j-1] < self[j]
        swap!(j-1, j)
      end
    end
  end
end

ary.extend Sortable
ary.insert_sort

Rubyではfor文を使わない、ということでuptoメソッドで代替しました。合わせてwhile文についてもdown_toで置き換えています。イテレータの制御をメソッド自身に任せる点でRubyらしいといえます。

他にはArrayオブジェクトにてextendして用いることで、関数ではなくメソッドとしてswapやinsert_sortを実施できるようにしました。

DFSとBFS

DFSとBFSとは

DFS(Depth First Search)=深さ優先探索、
BFS(Breadth First Search)=広さ優先探索

と呼ばれるアルゴリズムのことです。

グラフを探索するにあたって、どのような順序でノードを巡回していくか？を指すものと思っていただければ、差し支えございません。具体的には次の2つの図のような順番で探索を進めます。

DFSの場合

f:id:imtstmn:20210323175342p:plain

数字の順番に探索が行われます。

ノード0から探索を開始する
ノード1, 5, 6を発見する
ノード1が条件に合致するか確認する
ノード1に接続されたノードを探す
ノード2を発見する
ノード2が条件に合致するか確認する
ノード2に接続されたノードを探す
ノード3, 4を発見する
ノード3が条件に合致するか確認する
(以下、同様)

このように、新しく発見したノードから先に探索を進めていく方式がBFS(広さ優先探索)です。

BFSの場合

f:id:imtstmn:20210323175406p:plain

ノード0から探索を開始する
ノード1, 2, 3を発見する
ノード1が条件に合致するか確認
ノード1に接続されたノードを探す
ノード4を発見する
ノード2, 3も1と同様に、条件を確認した上で接続ノードを見つける
ノード1, 2, 3の探索を完了する
新しく発見したノード4, 5の条件を確認する
(以下、同様)

このように、先に発見したノードから先に探索を進めていく方式がBFS(広さ優先探索)です。

早速、コードを見ていきましょう。

テキストのコード

function DFS(start_node, key)
  next_nodes <- Stack.new()
  seen_nodes <- Set.new()
  
  next_nodes.push(start_node)
  seen_nodes.add(start_node)
  
  while not next_nodes.empty
    node <- next_nodes.pop()
    if node.key = key
      return node
    for n in node.connected_nodes
      if not n in seen_nodes
        next_nodes.push(n)
        seen_nodes.add(n)
  return null

function BFS
  next_nodes <- Queue.new()
  seen_nodes <- Set.new()
  
  next_nodes.enqueue(start_node)
  seen_nodes.add(start_node)
  
  while not next_nodes.empty
    node <- next_nodes.dequeue()
    if node.key = key:
      return node
    for n in node.connected_nodes
      if not n in seen_nodes
        next_nodes.enqueue(n)
        seen_nodes.add(n)
  return null

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

  alias :queue_memory :push_memory

  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
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
end

DFS

class Graph
  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
end

BFS

class Gragh
  def bfs(start_key, key)
    initialize_search_memory

    start_node = find_node start_key
    queue_memory start_node

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

実行結果

@graph = 'グラフの生成'
@gragh.dfs(0, 3)
=> #<Node:0x00007fd68e85a7e8 key: 3, value: 35, connected_nodes: [4, 5, 8, 9]>
@gragh.dfs(0, 3)
=> #<Node:0x00007fd68e85a7e8 key: 3, value: 35, connected_nodes: [4, 5, 8, 9]>

テキストのコードでは、stackやsetなど一般的なデータ構造を用いて書かれていました。 Rubyによる実装ではクラス定義を用いることで、引数を最小限に抑えることができたため、シンプルなコードで書くことができました。

おわりに

前半では、勉強会がどのように進められていたか？勉強会で何を得て、業務に活かすことができているか？について述べました。自己研鑽して食らいついていくことは前提ではありますが、スタメンには、それをサポートする環境があります。

後半では、やや技術的な内容としてテキストの疑似コードをRubyで実装したコードを紹介しました。バリエーション豊かなイテーレーションメソッドや、クラス定義を用いることで、よりシンプルに書けるRubyの良さを再確認しました。

今回は以上です。最後までご覧いただき誠にありがとうございました。

スタメンでは一緒にプロダクト開発を進めてくれる仲間を募集しています！興味を持っていただいた方は、是非下記の募集ページを御覧ください。

Webアプリケーションエンジニア募集ページ

stmn tech blog

社内勉強会レポート(コンピュータ・サイエンス)

勉強会レポート

テキスト

内容

所感

業務に活かせていること

計算量を意識できるようになった

Rubyならではの書き方に関心が向くきっかけとなった

Rubyによる各種アルゴリズムの実装

挿入ソート

テキストのコード

Rubyで動作のみを再現したコード

リファクタリング後

DFSとBFS

DFSとBFSとは

テキストのコード

Rubyによる実装

おわりに