アルゴリズムを学んでみた感想を書いてみる

おはこんばんにちはsenehataです

今回はアルゴリズムを学んでみて思ったことを書いていこうと思います。

ちなみに私のアルゴリズムの知識は入門書を数冊読んだ程度なので、知識0の状況から少し勉強してみたらどう感じたかといった記事になるので把握お願いします

アルゴリズムって何
アルゴリズムを考えることは工学することである。
具体的にアルゴリズムを解説
アルゴリズムをどう勉強していくか

アルゴリズムって何

ある問題に対して解を求める手続きをアルゴリズムと呼びます。

従って、1+1=2という処理の手続きもアルゴリズムといえます。また、一般的にはコンピュータ上で解を求める状況をアルゴリズムを考える上では想定しますが、別に紙とペンで計算する時にも使うことができます。例えば最大公約数を求めるユークリッドの互除法もアルゴリズムです。(高校数学で一度はやってる人が多いと思います。)

アルゴリズムを考えることは工学することである。

そして、アルゴリズムを考えるにあたっては実益上の観点から処理が完了するまでにかかる時間が少ないアルゴリズムを目指します。この処理が完了するまでにかかる時間を時間計算量として扱います。

つまり、アルゴリズムの優劣を決める際は時間計算量の大小が指標となるのです。(空間計算量という指標もあるが今回は割愛)

なぜ時間計算量が低い方がいいかと言われれば、当たり前ですが同じ処理をするにあたってはかかる時間が短い方が良い製品を作れるからです。

このように実益を目指す志向がアルゴリズムを学ぶ上では求められるため、アルゴリズムは工学です。なので、アルゴリズムを勉強することによってこの世界に対する理解が深まるという視点よりかは、勉強することによってより良い製品を作る糸口が増えるという視点を持った方が良いと思います。

具体的にアルゴリズムを解説

ここでは実際に有名とされるアルゴリズムとその性質を紹介しましょう。

ところで私は普段UnityでC#を用いてゲームを制作していて、そのC#で実際に組んだアルゴリズムをすでにGitHubに挙げました。ここで組んだアルゴリズムを紹介していきます。

GitHub - senehata/hatake_of_algorithm: アルゴリズムの畑

アルゴリズムの畑. Contribute to senehata/hatake_of_algorithm development by creating an account on GitHub.

以下解説するのは探索アルゴリズムです。探索とはそのまんま見つけてほしい情報がどこにあるかを探し出すことです。

ここでソート済みの整数型の配列があると仮定しましょう。その中にある特定の値がどこにあるかを探し出してみます。

最も単純な方法は配列の一番最初から一つずつ探し出す方法です。これも歴としたアルゴリズムで、線形探索と呼びます。線形探索の時間計算量はO(n)です。(これはn個の要素があったら、最悪な場合n回計算する必要があるということです。)

線形探索は愚直で実装も簡単ですが、もっと早く探索をすることができます。それが二分探索です。二分探索の時間計算量はO(logN)です。処理は以下のようにします。

//Binary Search
//二分探索
public class BinarySearch
{
    /// <summary>
    /// 二分探索
    /// ソート済みの配列の中から、探索したい値が配列の中でどの位置にあるかを探索する。
    /// </summary>
    /// <param name="array">探索する配列を入れる</param>
    /// <param name="target">探索したい値を入れる</param>
    /// <returns></returns>
    public int BinarySearchFunction(int[] array, int target)
    {
        int left = 0; //探索する配列の最小の値の位置。探索中に動的に変化する。
        int right = array.Length - 1; //探索する配列の最大の値の位置。探索中に動的に変化する。

        while (left <= right)
        {
            int middle = left + (right - left) / 2; //真ん中の要素を計算

            if (array[middle] == target) //探索したい値の発見パターン
            {
                return middle;
            }
            else if (array[middle] < target) //探索したい値が予想より大きい
            {
                left = middle + 1;
            }
            else　　　　　　　　　　　　　　　　　//探索したい値が予想より小さい
            {
                right = middle - 1;
            }
        }

        return -1; // 要素が見つからない場合
    }
}

//Binary Search

//二分探索

public class BinarySearch

{

/// <summary>

/// 二分探索

/// ソート済みの配列の中から、探索したい値が配列の中でどの位置にあるかを探索する。

/// </summary>

/// <param name="array">探索する配列を入れる</param>

/// <param name="target">探索したい値を入れる</param>

/// <returns></returns>

public int BinarySearchFunction(int[] array, int target)

{

int left = 0; //探索する配列の最小の値の位置。探索中に動的に変化する。

int right = array.Length - 1; //探索する配列の最大の値の位置。探索中に動的に変化する。

while (left <= right)

{

int middle = left + (right - left) / 2; //真ん中の要素を計算

if (array[middle] == target) //探索したい値の発見パターン

{

return middle;

}

else if (array[middle] < target) //探索したい値が予想より大きい

{

left = middle + 1;

}

else　　　　　　　　　　　　　　　　　//探索したい値が予想より小さい

{

right = middle - 1;

}

return -1; // 要素が見つからない場合

}

線形探索よりは複雑になりますが、コードの書き方を変えるだけで処理速度が場合によっては圧倒的に早くなります(特に探索する対象のリストが大きければ大きいほど威力を発揮します。)

アルゴリズムをどう勉強していくか

アルゴリズムは計算量を削減したいというときに威力を発揮します。したがって、かなり重い処理があって、それをもっと軽量化したいなと思ったらまずはアルゴリズムについて考えてみると良いのかなと思いました。

それで使えそうだなと思ったアルゴリズムをその場で勉強していくのが良いと思います。

いつ使うか分からないけどとりあえず色んなアルゴリズム触ってみるという勉強法は僕にとっては結構なモチベーションが必要で大変だと実際に勉強していて感じました。なぜなら、実際にいつ使うか想像しづらいからですね。

けれども、超基本的なアルゴリズムくらいは使わないでも触れてみるのは有効だと思います。そもそもアルゴリズムって何?ってのが分からないと、詰まった時にアルゴリズムを改善してみるか。という着想に至らないので。

参考文献

アルゴリズム - Wikipedia