スタメンエンジニアの井本です。 普段の業務では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の場合
数字の順番に探索が行われます。
- ノード0から探索を開始する
- ノード1, 5, 6を発見する
- ノード1が条件に合致するか確認する
- ノード1に接続されたノードを探す
- ノード2を発見する
- ノード2が条件に合致するか確認する
- ノード2に接続されたノードを探す
- ノード3, 4を発見する
- ノード3が条件に合致するか確認する
- (以下、同様)
このように、新しく発見したノードから先に探索を進めていく方式がBFS(広さ優先探索)です。
BFSの場合
- ノード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の良さを再確認しました。
今回は以上です。 最後までご覧いただき誠にありがとうございました。
スタメンでは一緒にプロダクト開発を進めてくれる仲間を募集しています! 興味を持っていただいた方は、是非下記の募集ページを御覧ください。