こんにちは!
システム開発グループ プログラマーのFです。
今回はプログラマーの業務には欠かせない「アルゴリズム」について、実際の例に触れながら紹介します!
専門的な内容になりますが、プログラマーの仕事内容について興味がある方の参考になれば嬉しいです。
「アルゴリズム」とは問題を解決するための手順や計算方法のことを指します。
プログラマーはある機能や動作を達成するためにコードを記述します。
プログラムは記述した内容に沿って動いてくれるのですが、問題解決にあたっての手順(アルゴリズム)はプログラマーが考える必要があります。
このアルゴリズムを考えるのもプログラマーの仕事の一つです。
ファーストでは工場などの生産現場において、生産管理を行うシステムを開発しています。
このシステムでは、タブレット端末でWebアプリを操作することにより、作業の開始時刻、終了時刻、作業時間等の生産作業の記録が行われます。便利ですね!
さて、上記の記録から、
①生産に要したすべての作業者の合計作業時間(以下、「総作業時間」と表現します。)
②生産に要した生産設備の利用時間(以下、「設備使用時間」と表現します。) を集計計算する必要が生じました。
この集計計算を行うアルゴリズムを考えてみます。
物事を考えるには、まず前提です。前提大事。
今回の前提は以下の通りです。
<前提>
- 生産物は生産設備を使った作業者の作業により生産される
- 生産物の生産作業を行う作業者は複数人存在する場合がある
- 一人の作業者が複数回の作業を行う場合がある
- 複数の作業者が同時に生産作業を行う場合がある
- データベースには、生産物を生産するにあたり作業者が1回の作業で行った作業時間が1データとして保存されている
例えば次のような生産作業です。
<ケース1>
- 作業者Aは10:00～12:00の2時間作業を行った(作業データa1)
- 作業者Aは13:00～14:00の1時間作業を行った(作業データa2)
- 作業者Bは12:00～13:00の1時間作業を行った(作業データb1)
-----------------------------------------------------------------------------------------------
時刻 09:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00
作業者A <------- a1 -------> <-- a2 -->
作業者B <-- b1 -->
-----------------------------------------------------------------------------------------------
まずは「総作業時間」を求めるアルゴリズムを考えます。
単純にすべての作業者の作業データの作業時間を足せば良さそうです。これは助かりました。 上記のケース1での総作業時間は [a1] + [a2] + [b1] = 2 + 1 + 1 = 4 時間になります。
この4時間という答えを算出するアルゴリズムを上記の<前提>を踏まえて記述します。
<総作業時間を求めるアルゴリズム>
① 生産物に対する作業一回をデータベースから検索する
② ①で定まった作業の作業時間を集計する
③ ①～②を生産物に対するすべての作業について繰り返す
アルゴリズムを考え、さらにそれをコード上で実現できればプログラムとして機能させることができます。
(※実際の業務では様々なケースでテストを行い、このアルゴリズムの正当性を確認する必要があります!)
次に「設備使用時間」を求めるアルゴリズムを考えますが、これは総作業時間ほど簡単ではありません。助からなかった。
上記のケース1でいえば、設備使用時間は
- 10:00～12:00の2時間(作業データa1)
- 12:00～13:00の1時間(作業データb1)
- 13:00～14:00の1時間(作業データa2)
ですので、2 + 1 + 1 = 4 時間になりますが、このケースは作業に休憩等の切れ目がなく、複数人が同時に作業を行うこともない単純なケースでした。
今度は以下のような生産作業を考えてみます。
<ケース2>
- 作業者Aは10:00～12:00の2時間作業を行った(作業データa1)
- 作業者Aは14:00～15:00の1時間作業を行った(作業データa2)
- 作業者Bは13:00～16:00の3時間作業を行った(作業データb1)
- 作業者Cは15:00～16:00の1時間作業を行った(作業データc1)
-----------------------------------------------------------------------------------------------
時刻 09:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00
作業者A <------- a1 -------> <-- a2 -->
作業者B <------------ b1 ------------>
作業者C <-- c1 -->
-----------------------------------------------------------------------------------------------
このケースでは12:00～13:00は誰も作業を行っていません。
また、14:00～15:00には作業者AとBが同時に作業を行っており、15:00～16:00には作業者BとCが同時に作業を行っています。大変だ。
この場合の設備使用時間は、
- 10:00～12:00の2時間(作業データa1)
- 13:00～16:00の3時間(作業データa2、作業データb1、作業データc1)
ですので、2 + 3 = 5 時間になります。
このくらいのケースであれば、上記の図を見て人間はなんとなく設備使用時間を算出することができます。
しかし、アルゴリズムとしてはどのように考えればよいのでしょうか。
アルゴリズムを導き出すには物事を整然とした順番で捉えていくことが大切です!
そのため、上記の図を作業データa1, a2, b1, c1の順で捉えていくことを考えてみます。
- 作業データa1は全時間を設備使用時間に集計できる
- 作業データa2も全時間を設備使用時間に集計できる
- 作業データb1は13:00～14:00、15:00～16:00は設備使用時間に集計できる。しかし、14:00～15:00は前出の作業データa2で集計済みなので集計できない
- 作業データc1は前出の作業データb1で集計済みなので集計できない
結局のところ、
- すべての作業データの作業時間を順に集計していく
- ただし、それまでの作業データで集計済みの作業と重複する時間帯に相当する作業時間については除外する
ということを行えばよいことが分かります。
これが既にアルゴリズムです。
<前提>を踏まえて記述してみます。
<設備使用時間を求めるアルゴリズム1>
① 生産物に対する作業一回をデータベースから検索する
② ①で定まった作業の作業時間を集計する。その際、それまでに集計済みの作業と重複する時間帯に相当する作業時間は除外する
③ ①～②を生産物に対するすべての作業について繰り返す
アルゴリズムを導き出すことができました。
これをコード上で実現すれば、プログラムとして機能させることができます。めでたし。
さて、上記のアルゴリズムで問題はありませんが、一つの問題に対するアルゴリズムは他にも考えられます。
例えば、設備使用時間を求めるアルゴリズムには次のようなものもあります。
<設備使用時間を求めるアルゴリズム2>
① 生産物に対する作業一回をデータベースから検索する
② ①で定まった作業の開始時刻と終了時刻をポイントp(p1, p2, …)として記憶する
③ ①～②を生産物に対するすべての作業について繰り返し、全てのポイントを記憶する
④ ③までに記憶したポイントとポイントを時刻の早いものから順に繋ぎ、繋いだ時間帯を区間s(s1, s2, …)として記憶する
⑤ ④で記憶した全区間のうち、区間一つを時間帯が早い区間から検索する
⑥ ⑤で定まった一つの区間の時間帯について、これを時間帯的に包含する作業データが一つでも存在する場合、この区間に相当する時間を集計する
⑦ ⑤～⑥をすべての区間について繰り返す
上記のケース2で試してみると、
-----------------------------------------------------------------------------------------------
時刻 09:00 10:00 11:00 12:00 13:00 14:00 15:00 16:00 17:00
作業者A <------- a1 -------> <-- a2 -->
作業者B <------------ b1 ------------>
作業者C <-- c1 -->
-----------------------------------------------------------------------------------------------
p1 p2 p3 p4 p5 p6
ポイント * * * * * *
区間 <------- s1 -------><-- s2 --><-- s3 --><-- s4 --><-- s5 -->
-----------------------------------------------------------------------------------------------
- 区間s1(10:00～12:00)は包含する作業データa1が存在するので集計できる
- 区間s2(12:00～13:00)は包含する作業データが存在しないので集計できない
- 区間s3(13:00～14:00)は包含する作業データb1が存在するので集計できる
- 区間s4(14:00～15:00)は包含する作業データa2, b1が存在するので集計できる
- 区間s5(15:00～16:00)は包含する作業データc1が存在するので集計できる
となります。
これでたしかに2 + 1 + 1 + 1 = 5 時間になります。
アルゴリズム1は作業データを集計の軸としていますが、アルゴリズム2は区間(時刻)を集計の軸とするような発想に変わっていますね。
理解しやすさという点では、アルゴリズム1のほうが優位であるかのように思えます。
しかし、最終的にアルゴリズムはコード上で実現しなければなりません。
コード上での実現の難易度は、アルゴリズム2のほうが簡単で優位である可能性もあります。
また、計算速度や処理に必要な記憶領域の点ではどちらのほうが良いか、といったことも重要です。
このように一つの問題に対するアルゴリズムは一つとは限りません。
複数のアルゴリズムを頭の中で検証しながら、最終的に採用するアルゴリズムを決定し、プログラムを組み立てていくのです。
とはいえ、実際には、上記の設備使用時間を求めるアルゴリズムのように複雑で発想が極端に異なるものをあえて扱う場面は多くありません。
大半の場合、もっと簡単です。よかった。
少しだけ異なる複数の選択肢(アルゴリズム)の中から、少しだけより良いものを選ぶといったぐらいの感覚ですね。
以上、アルゴリズムについてでした!
この記事のサムネイルは社内のデザイナーさんに作っていただきました。
とてもかわいく素敵に作っていただいて本当に感謝です。
ありがとうございました!!