【備忘録】 アルゴリズム概論
うぃろぅです。
今日はアルゴリズムについて。「ロジック研修」なるタイトルがついていましたがまぁアルゴリズムのことでしょう。多分。やっていきます。
今日のテーマ
アルゴリズムについて
アルゴリズムとは
問題を解決するための処理手順のこと。
「どのような仕事」を「どのような手順」で行うかを明確にすることが大事。
例えばカップ麺を作るのであれば
- 水を沸かす
- ふたを半分ほど開ける
- かやく等のものがあったら取り出す
- 先入れのものがあったら入れる
- お湯を入れる
- ふたを閉める
- 指定の時間待つ
- ふたを開ける
- 後入れのものがあったら入れる
- 食べる
- 美味しい!!
という手順を書き起こせる。これがアルゴリズム。
処理手順
上に書いた例で概ね説明できている気がする。
プログラムは思ったとおりには動かず、書いたとおりにしか動かない。
手順が間違っていてもそのとおりに実行するというわけである。なのでちゃんと手順を作成しようね、というお話。
表現手法
書き方は何通りもあるが、統一された書き方があれば他人に理解しやすく、自分も作業を進めやすい。毎回手法から決めるのは時間のムダになるし。
そこで統一規格を使って流れ図を書くようにすればいいよね、というお話。
基本構造
- 順次構造
- 選択構造
- 反復構造
の3つで成り立っている。
順番に見ていく。
順次構造
上から下へと順番に処理を行い、戻ることがない構造。
いわゆるウォーターフォールみたいなもの。
脱線するけれど今私は新人研修の講師を担当していて、新人くんに自分が書いたフローチャートの説明をしてもらうことがある。
その中の1人に「配列の添え字2の値、いわゆる7に対して~」と説明する人がいる。
いわゆるって「俗に言う」みたいな意味だと解釈していたため、言葉の概念が乱れてもう説明どころではなくてんやわんやになってしまうわけだけれどいわゆるって言わないよね…?
閑話休題。どんどん続けていく。
選択構造
「雨であったら傘を持っていく」「そうでなければ傘をもたない」
というように条件によって行動を出し分けること。
つまりはプログラム言語1で使うif。
反復構造
繰り返し処理。
「水が沸騰するまで」「やかんを確認する」みたいな。
C言語でのforやwhile。Rubyだとmapとかeachをよく使うかなぁ。JavaだったらStream()が便利で最近forをあまり書いていない。
アルゴリズムの考え方
大枠を捉えてから詳細をつめていく、という流れがわかりやすい。
目をめちゃくちゃ描きこんでから顔の輪郭を描く、という人はあまりいないでしょ。そういうこと。ちなみにそういう手法をとる人もいて、そういった人は私に見えていないものが見えている。ちょっと羨ましいがないものねだりをしても仕方ないため、一般的な手法に頼ることになるのである。日々妥協していこうな。
アルゴリズムの基本
よくあるフローチャートの描き方について。
データ
プログラムは処理に必要なデータを目に見えない領域に保存している。
例として電卓が挙げられていて40 + 10 =と入力するとき、10を入力したときに40の表示は消えているが、=を入力するとちゃんと結果が表示される。これは40や+といったデータを覚えておく領域を用意しているから実現できている。
領域図
上記のデータ格納よう領域をベン図のように表す。ただし領域同士は重ならない。
フローチャート
JIS(日本工業規格)に沿って描かれたものをJISフローチャートと呼び、これによって処理の流れを統一規格で表すことができる。
描いていけばそのうち覚えるため、最初から全て覚える必要はない。
アルゴリズム作成手順
- 完成した状態を考える
- フローチャートを描く
- トレースをする
実際に動かしたときの値の変化を確かめる
が基本。領域は必要なときに確保すれば良さそう。
基本的なアルゴリズム
ここでは
- 加算
- 交換
- 判断
- 繰り返し
について見ていく。
加算
領域に入っているデータを加算する。読んで字のごとく。
領域Aに入っているデータと領域Bに入っているデータを加算し、領域Cに代入する。
領域Aに入っているデータを置き換える場合必要な領域は2つ、領域Cに代入する場合必要な領域は3つ。
交換
領域Aに入っているデータと領域Bに入っているデータを入れ替える。
領域Aと領域Bを入れ替えるためには作業用領域が必要となるため、こちらも領域は3つ必要となる。
領域Aのデータを作業用領域に退避(コピー)領域Bのデータで領域Aを上書き作業用領域のデータで領域Bを上書き
という流れ。交換する領域の数より1つ多い領域を確保することがポイント。
判断
条件を判断して処理を振り分ける。選択構造の要。
領域Aと領域Bを比較する。比較する数分の領域があればOK。
繰り返し
条件を満たすまで処理を繰り返し実行する処理。反復構造の要。
ループカウンタを用意するのが大事。繰り返すかどうかで判断の処理も使われている。
あとループカウンタの加算処理(負の値の加算、乗算は指定回数の加算)も行う。
頑張れば繰り返し処理を記述しなくてもどうにかならないではない。現実的ではないが。
配列
データを複数入れる箱。プログラミング界隈ではお馴染み。
細かい解説は…いいか。わかるし。
集計
ここからはこれまでのアルゴリズムを組み合わせた応用。
集計とは
複数のデータを合計する処理。
考え方
集計対象のデータ分繰り返し処理を行い、合計領域に加算していく。かんたーん。
探索
サーチとも。調べ方によって処理時間だったり処理順序だったりが変わってくる。
探索とは
複数のデータの中から目的のデータを探す処理。
探索法
- 逐次探索法
- 2分探索法
の大きく分けて2つある。
逐次探索法
先頭のデータから順に条件を満たすデータを探す。
最初に一致した時点で探索が終了する。
2分探索法
予めソート済みのデータを対象とし、その前半 / 後半のデータを探索する。
ソート済み、という制限つきだがこちらの方が概ね短い時間で探索が終わる。
整列
ソートとも。ならべかえ。QMA的にはなべらえか。
整列とは
複数のデータを昇順 / 降順で並べ替える処理。
整列法
大きく3つらしい。
等に関しては今回は触れないっぽい。
この記事が面白い。
基本選択法
[3, 5, 1, 4, 2]という配列があったとして、昇順で並べ替える場合の処理順は以下。
3と5を比較3と1を比較 → 入れ替え
[1, 5, 3, 4, 2]1と4を比較1と2を比較1の場所が確定
[*1, 5, 3, 4, 2](*は場所が確定している要素とする)5と3を比較 → 入れ替え
[*1, 3, 5, 4, 2]3と4を比較3と2を比較 → 入れ替え
[*1, 2, 5, 4, 3]2の場所が確定
[*1, *2, 5, 4, 3]5と4を比較 → 入れ替え
[*1, *2, 4, 5, 3]4と3を比較 → 入れ替え
[*1, *2, 3, 5, 4]3の場所が確定
[*1, *2, *3, 5, 4]5と4を比較 → 入れ替え
[*1, *2, *3, 4, 5]4の場所が確定
[*1, *2, *3, *4, 5]5の場所が確定
[*1, *2, *3, *4, *5]
もう書きたくない。計算量はO(n^2)。大変そう。
単純交換法(バブルソート)
隣り合う要素同士を比較して交換する処理を繰り返す。
こちらも計算量オーダーはO(n^2)となるため遅い。
https://wa3.i-3-i.info/word14886.html
ざっくりわかる解説。
基本挿入法(インサートソート)
リストに対して値を挿入する箇所を探索する、という処理を繰り返す。
マッチング
まいっちんぐではない。疲れてるのかしら。
私もマッチングして欲しい
マッチングとは
2つのファイルのキー項目を突合せ、その結果によってデータを処理すること。
例えば「在庫ファイル」と「売上ファイル」から新しい「在庫ファイル」を作成する、といった処理。
グループトータル
要はSQLのgroup by。この前書いたからそれでいいかなって。
文字列操作
文字列に対していろいろする。
いろいろって何さ
- 圧縮
スペース削除。 - 探索
山口さんの存在箇所を探す等。 - 置換
田中を田口に置き換える等。 - 挿入
(株)を会社名の前に挿入する等。
といった感じ。
まとめ
アルゴリズムの基本と、標準的なパターンについて。
今日のは長かったので後半が雑になってしまった気しかない。まぁ大体知ってるし…ということでひとつ。
ではまた。
