こんにちは!
CYBIRD Advent Calendar 2022 25日目担当の@S_onizawaです。
24日の記事は@min1osさんの「Nuxt3を0から勉強した学習フローをまとめてみた」でした。
1 自己紹介
私は今年で社会人2年目のサーバーサイドエンジニアです。
主にPHPを使って仕事をしておりますが、最近はGO言語も使った開発に携わらせていただいています。
2 概要
まず大前提に、アルゴリズムとは。
「問題を解決するための手順や計算方法」のことを言います。
アルゴリズムを知るにはどうすればいいのか、知ることのメリットなどを記載します。
書いてあることは結構基本的なことだと思いますが、初心に帰って見てもらえればと思います。
3 アルゴリズムを知る
実際アルゴリズムを知るには、直接調べてみたり、私が今回phpで書いたようにコードにしたりすると良いと思います。
アルゴリズムの教科書や情報技術者試験などでよく出てくる、ソートのアルゴリズムを例に出したいと思います。
今回はバブルソートとマージソートについて記載したいと思います。
3.1 バブルソート
このソート方法が最もオーソドックスだと思います。
隣り合う要素の大小を比較しながら整列させるソートアルゴリズムです。
wikipedia参照
phpで書いたコードがこちらです。
<?php
//1-10の配列を作成
$arr = range(1, 10);
//配列をランダムに並べ替える
shuffle($arr);
var_dump($arr);
var_dump(bubbleSort($arr));
function bubbleSort($arr) {
for($i = 0; $i < count($arr); $i++) {
for($j = 1; $j < count($arr); $j++) {
//隣接した箇所を比較し入れ替える
if($arr[$j-1] > $arr[$j]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $temp;
}
}
}
return $arr;
}
?>
3.2 クイックソート
クイックソートが他のソート法に比べて一般的に最も高速と言われています。
大きい値のグループと小さい値のグループの二分割を行い、二分割した中心の値より大きい値を右側に、小さい値を左側に交換していきます。
それぞれのグループで同じように、二分割を行って交換していき、整列できるまで行うソート方法になっています。
phpで書いたコードがこちらです。
<?php
//1-10の配列を作成
$arr = range(1, 10);
//配列をランダムに並べ替える
shuffle($arr);
$arr_count = count($arr);
var_dump($arr);
quickSort($arr, 0, $arr_count-1);
var_dump($arr);
function quickSort(&$arr, $first, $last) {
$f_pointer = $first;
$l_pointer = $last;
//配列の中央の値
$center_value = $arr[($first + $last) / 2];
//分割ができなくなるまで回す
do {
//並び替えを行う中央より高い左側の値を特定
while ($arr[$f_pointer] < $center_value) {
$f_pointer++;
}
//並び替えを行う中央より低い右側の値を特定
while ($arr[$l_pointer] > $center_value) {
$l_pointer--;
}
//中央の値より、「高く左側にあるもの」、「低く右側にあるもの」と入れ替える
if($f_pointer <= $l_pointer) {
$temp = $arr[$l_pointer];
$arr[$l_pointer] = $arr[$f_pointer];
$arr[$f_pointer] = $temp;
$f_pointer++;
$l_pointer--;
}
}
while ($f_pointer <= $l_pointer);
//左側で分割を行えるならさらに分割
if($first < $l_pointer) {
quickSort($arr, $first, $l_pointer);
}
//右側で分割を行えるならさらに分割
if($f_pointer < $last) {
quickSort($arr, $f_pointer, $last);
}
}
?>
3.3 phpで使用できるsort関数
phpにはライブラリとして簡単に並べ替えられる「sort」があります。
ライブラリとして用意されてある「sort」はどのアルゴリズムを使って作られているでしょうか。
phpの公式で公開されている「sort」のマニュアルを確認すると
注意: PHP の大半のソート関数と同様、sort() は » Quicksort でそれを実装しています。 ピボットは、既にソート済みの部分に対して時間的に最適なところを選択します。 しかしこれはあくまでも内部の実装の話なので、これに依存したコードを書いてはいけません。
こちらのサイト
と、このようにクイックソートのアルゴリズムを用いて実装されてあります。
現在、便利に使っているライブラリも、アルゴリズムを使って実装したものだと言えます。
4 まとめ
3.3で紹介したように「sort」関数を使ってしまえばソートのアルゴリズムを知らなくても誰でも簡単に並び替えをすることができると思います。
ただ、このようなソートのようにライブラリがない場合は、自分で考えないといけないわけです。
しかし、便利な「sort」などの関数はたくさんありますので、アルゴリズムを直接考えたりすることは多くないと思います。
また、仕事などに活かせる場面があるとは言い切れませんが、アルゴリズムを学ぶことで「効率よくするためには、どうすれば良いか」「どのように改善すれば、処理速度が速くなるのか」といったアルゴリズム的な考え方になれればと思います。
探索アルゴリズム、ソートアルゴリズム、暗号化アルゴリズムなど、今では多くのアルゴリズムが存在します。
全部を学ぶことは大変だと思うので、今回紹介したアルゴリズムだったり、有名なアルゴリズムを調べてみたりして見てはどうでしょうか。
また、使っているライブラリがどんなアルゴリズムを使っているかなど調べるのもいいかもしれません。
実際に手を動かしてコードを作ってみたり、同じアルゴリズムでも違いなどを調べることで、より深く理解できるようになると思います。
5 最後に
CYBIRD Advent Calendar 2022はいかがだったでしょうか。
２５日間、色々な記事が記載されているので、ぜひ見てみてください！
今年のCYBIRD Advent Calendar 2022は、これにて終了となります。
来年もよろしくお願いいたします！みなさま、良いお年をお迎えください！