IT関連
アルゴリズム
- ・アルゴリズムについて簡単にご説明します。
- ・データ分析・解析でITが関係するため記事にしております。
- ・ITの理解を深めたい方はご参照ください。
- ・不明点あれば問い合わせください。
- ※当サイトで掲載しているデータは適当に作成したものであり、実際のものではありません。
アルゴリズムとは
アルゴリズムとは、簡単に説明すると、形式的な計算の手続きのことと言えます。
通常、アルゴリズムはプログラムとして実装されており、ゆえに、アルゴリズムとプログラムが混同されることが多々あります。
確かにどちらも近い概念ではありますが、アルゴリズムとプログラムは別物です。
しいて関係を説明するならば、アルゴリズムを処理として実装したものがプログラムとなります。
そして、処理がアルゴリズムであるためには、以下のような条件を満たさなければなりません。
【条件１】実行すべき内容が明確であること
【条件２】同一な入力に対して同一な結果を出力すること
【条件３】有限回の計算で処理が完了すること
実行すべき内容が明確であれば、誰が解釈しても、どのコンピュータで実行しても、同様な処理になります。
そして、同一な入力に対して同一な結果が出力されるという点が、アルゴリズムの特徴です。
ただし、乱数生成アルゴリズムや遺伝的アルゴリズムのように、実行の度に結果が異なる手法も存在します。
加えて確率的な手法の中には、確実に終了すると言い切れない手法も存在します。
それらは上記の条件を満たしてはいませんが、アルゴリズムとして扱われます。
一般的には、手順が整っている手続きを幅広くアルゴリズムと言う傾向があります。
しかし厳密には、上記のような条件を満たしていなければなりません。
アルゴリズムの例として、人類最古のアルゴリズムである「ユークリッドの互除法」が有名です。
ユークリッドの互除法は手順が再帰的に定義されています。
そして必ず処理が完了することを、数学的に証明することができます。
一方、コンピュータの分野では、検索アルゴリズムや整列アルゴリズムが代表的なアルゴリズムです。
それらアルゴリズムは、目的や手段によって振る舞いや性能が違ってきます。
そうした点を踏まえ、以下、整列アルゴリズムのバブルソート・選択ソート・挿入ソートを例にとって説明します。
アルゴリズムの例
整列アルゴリズムとしてバブルソート・選択ソート・挿入ソートを取り上げます。
どれもデータを昇順・降順に整列するアルゴリズムです。
例えば、「1,5,3,4,2」のデータを「1,2,3,4,5」のように整列します。
どのアルゴリズムで整列しても結果は同じですが、整列のさせ方は異なります。
以下にそれぞれのアルゴリズムの手順(降順の整列を想定)を示します。
バブルソート：
【手順１】n-1番目≥n番目となるように比較・交換する
【手順２】n-2番目＆n-1番目も同様に処理し、これを1番目＆2番目まで繰り返す
【手順３】末尾に戻り、n-1番目＆n番目～2番目＆3番目まで同様な処理を繰り返す
【手順４】末尾に戻り、n番目～n番目となれば処理を終了する
選択ソート：
【手順１】1番目～n番目における最大の要素と1番目を交換する
【手順２】2番目～n番目においても同様に処理する
【手順３】この処理をn-1番目～n番目まで繰り返す
【手順４】n番目～n番目となれば処理を終了する
挿入ソート：
【手順１】1番目≥2番目となるように比較・交換する
【手順２】交換が発生した場合は、交換後もi-1番目≥i番目となるまで交換を繰り返す
【手順３】この処理をn番目まで繰り返す
【手順４】n番目が交換されなくなれば処理を終了する
まとめると、バブルソートは交換により整列し、選択ソートは選択により整列し、挿入ソートは挿入により整列します。
バブルソートでは、手当たり次第に要素同士を比較し交換するため、手間の多いアルゴリズムとなっています。
対して選択ソートでは、最大(もしくは最小)な要素を選択し交換するため、交換回数は少なく抑えられます。
もしデータサイズが大きい場合は選択ソートが有効です。
そして挿入ソートでは、先頭から部分的に整えながら全体を整列していきます。
したがって、既に部分的に整列されているデータを対象とする場合は、高速に整列することができます。
以下、これら整列アルゴリズムの実行の様子です。
バブルソートの可視化
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
選択ソートの可視化
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
挿入ソートの可視化
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
ここで取り上げたバブルソート・選択ソート・挿入ソートは、単純で低速な整列アルゴリズムです。 これに対し、より高速な整列アルゴリズムとして、クイックソート・ヒープソート・マージソートがあります。 および、その中間的なものとして、コームソート・シェルソートがあります。 当然ながら、通常は、より高速なアルゴリズムを利用します。 その上で、状況に応じてアルゴリズムを使い分けます。 以下、これらの整列アルゴリズムを方針と速度でまとめた表です。
方針 ＼ 速度 |
低速 |
中間 |
高速 |
交換 |
バブルソート |
コームソート |
クイックソート |
選択 |
選択ソート |
ヒープソート |
|
挿入 |
挿入ソート |
シェルソート |
マージソート |
分析・解析アルゴリズム
整列アルゴリズム同様に、データ分析・解析においてもアルゴリズムは存在します。
ただ、意思決定のために行うデータ分析においては、そこまで厳密な精度は求められません。
大雑把に傾向が分かりさえすればいいのです。
そして必要に応じて人為的な調整をするなど、アルゴリズムらしからぬ操作をすることも多々あります。
逆に完全にアルゴリズム化できるのであれば、プログラムとして実装することでデータ分析を自動化することができます。
近年、分析・解析の対象となるデータはビッグデータとなりつつあります。
当サイトにおいてその規模のデータを解析することはありませんが、もしデータ量が膨大な場合は、アルゴリズムの計算量も意識しなければなりません。
当サイトでは数万レコード程度のデータを対象としており、概ね数分～数十分で処理が完了するため、アルゴリズムの計算量については意識しません。
しかしもし、数億レコードのデータを解析するとなると、スペックの高いサーバを利用したとしても処理が完了するまでに何日もかかるようになります。
こうしたことからもアルゴリズムの選定は重要です。