この問いには、そう簡単に答えることはできない。だが、それを十分に考えさせられる講義だった。そして、それがどれだけ重要なのかも。あまり効率的ではない探索アルゴリズムを用いた場合はメモリに負荷がかかるだけでなく、検索結果が分かるまでに非常に時間がかかってしまう。では、最適な探索アルゴリズムとは？これを数学的に示しながら解いて行く内容だ。また面白い内容だった。

　

　

Searching（探索）

  • 人間の目は良くできていて俯瞰して同時に色々なものを見ることができるが、コンピューターは一つずつしか読み込めない。この章では、ある値を探すための探索アルゴリズムを学ぶ。

　

Big O

第0週目の講義で、異なるアルゴリズムによって、処理速度が変わることが分かった。

chart with: "size of problem" as x–axis; "time to solve" as y–axis; red, steep straight line from origin to top of graph labeled "n"; yellow, less steep straight line from origin to top of graph labeled "n/2"; green, curved line that gets less and less steep from origin to right of graph labeled "log_2 n"

赤い線は、線形的で、言い換えると一つずつ探索し、黄い線は2ページ同時に探索でき、緑の線は、調べる度に、問題が半分に減っていくということだった。この処理速度を数学的に表したい場合は、big O notation という表現で表す。Oは、”on the order of” の略で、約、だいたいという意味だ。なので、赤い線も黄色の線もだいたい O(n) の処理ステップが必要。ここで、黄色の線は、実際は n/2 だが、だいたいなので、/2 は省略できる。なぜなら n が十分大きくなった場合には誤差になるので。緑の線は、O(log⁡n) となる。

  • big O notation には以下が存在する:
    • O(n2)
    • O(nlog⁡n)
    • O(n) ー (順番に1ページずつ探索する)
    • O(log⁡n) ー (電話帳を毎回半分にして探索する)
    • O(1) ー 定数回数でプログラムは終了するもの
  • また、同じアルゴリズムを使った場合に、最小ステップで探索できる場合のことを big Ω, big Omega notation を使って表す。それに対して、big O notation は最悪シナリオ。
  • big O notationと同様に big Omega notation も以下の種類がある:
    • Ω(n2)
    • Ω(nlog⁡n)
    • Ω(n)
    • Ω(log⁡n)
    • Ω(1) ー (電話帳の先頭ページに目的のデータがある場合)

　

Linear search, binary search（線形探索・順次探索, 二分探索・バイナリサーチ）

7つのドアが並んでいて、ドアを開けると数字が隠れているというステージが用意されている。この状況で線形探索を用いる場合、左のドアから順に一つずつ開けていき、目的のデータを見つけるまで続けることになる。これを仮に、pseudocodeで表すと次のようになる。

For i from 0 to n–1
    If number behind i'th door
        Return true
Return false

このプログラムでは、big O 処理時間は、O(n), big Omega は、 Ω(1) となる。

仮に、ドアの後ろの数字が綺麗に並び替えられているとしたら、ドアの真ん中を開けて問題を半分にできる。

If no doors
    Return false
If number behind middle door
    Return true
Else if number < middle door
    Search left half
Else if number > middle door
    Search right half


最大処理時間は O(log⁡n)、最小処理時間は Ω(1) となる。

　

Searching with code（コードを使った探索）

これをコードで記すと次のようになる。int numbers [] = {4, 6, 8, 2, 7, 5, 0}; のように配列に初期値を代入可能。この場合、[] の中に配列の大きさを指定する必要はない。

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int numbers[] = {4, 6, 8, 2, 7, 5, 0};

    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

次の例では、配列に入っている名前はアルファベット順に並び替えられている。C言語では他の言語とは違って、基本機能に文字列を比較するという機能が装備されていない。よって、strcmp() 関数が用意されていて、文字列の比較ができる。strcmp(names[i], "Ron") == 0 のように比較する2つの引数を与えてあげると、マッチしている場合は、0 を返してくれる。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"Bill", "Charlie", "Fred", "George", "Ginny", "Percy", "Ron"};

    for (int i = 0; i < 7; i++)
    {
        if (strcmp(names[i], "Ron") == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Structs（構造体）

仮にiPhoneに入っている電話帳アプリのように、名前と電話番号、その他諸々を紐付けたプログラムを書きたい場合、struct を用いてデータ型を作ることができることができる。

typedef struct
{
    string name;
    string number;
}
person;

もし、これを使わないとすると、次のようになるが、この場合だとそれぞれの配列でデータが上書きされたり、ソートされた場合に、連動して動く保証はない。なので、自分で型を作ることが有益ということらしい。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string names[] = {"Brian", "David"};
    string numbers[] = {"+1-617-495-1000", "+1-949-468-2750"};

    for (int i = 0; i < 2; i++)
    {
        if (strcmp(names[i], "David") == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Person というデータ型を作った場合に、以下のようになる。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
}
person;

int main(void)
{
    person people[2];

    people[0].name = "Brian";
    people[0].number = "+1-617-495-1000";

    people[1].name = "David";
    people[1].number = "+1-949-468-2750";

    for (int i = 0; i < 2; i++)
    {
        if (strcmp(people[i].name, "David") == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

　

　

Sorting（並び替え）

6 3 8 5 2 7 4 1

上の8桁の数字を並び替えるアルゴリズムを考えてみる。

Selection sort（選択ソート）

左から順にソートすると…

6 3 8 5 2 7 4 1
–             –
1 3 8 5 2 7 4 6

左端の6 と一つなりの数字（3）を比較、6の方が大きければひっくり返すという作業を続けると、一番右に6が来る。そして、一番左に 1 が移動する。

1 3 8 5 2 7 4 6
  –     –
1 2 8 5 3 7 4 6

これを繰り返す。

1 2 8 5 3 7 4 6
    -   -
1 2 3 5 8 7 4 6

これを何回か繰り返すと、綺麗に並び替えられる。このアルゴリズムをSelection sort（選択ソート）と呼ぶ。Pseudocodeで記すと、

For i from 0 to n–1
    Find smallest item between i'th item and last item
    Swap smallest item with i'th item

少し理解しづらいかもしれないので、ここのリンクからどのように動くのか視覚的に分かるプログラムが用意されている。

このアルゴリズムを数学的に表すと… 処理時間は O(n2)となる。

　　

Bubble sort（バブルソート）

バブルソートでは、右端に大きい数字を追いやる（Bubbling）ことからバブルソートと呼ばれている。左2つの数値を比較し、大きい数字を右に置く。

6 3 8 5 2 7 4 1
– –
3 6 8 5 2 7 4 1

6 と 8 を比較した場合は、順になっているためひっくり返す必要はない。

次の 8 と 5 は、ひっくり返す必要がある。

3 6 8 5 2 7 4 1
    – –
3 6 5 8 2 7 4 1

と続けると、ようやく一番大きい8が右端に来る。

3 6 5 2 8 7 4 1
        – –
3 6 5 2 7 8 4 1
          – –
3 6 5 2 7 4 8 1
            – –
3 6 5 2 7 4 1 8
              -

そしたら、また最初から続ける。

3 6 5 2 7 4 1 8
– –
3 6 5 2 7 4 1 8
  – –
3 5 6 2 7 4 1 8
    – –
3 5 2 6 7 4 1 8
      – –
3 5 2 6 7 4 1 8
        – –
3 5 2 6 4 7 1 8
          - –
3 5 2 6 4 1 7 8
            - -

処理時間がなかなかかかってしまう。

Pseudocodeでバブルソートを記述すると、次のようになる。

Repeat until sorted
    For i from 0 to n–2
        If i'th and i+1'th elements out of order
            Swap them

今まで出てきたアルゴリズムの処理時間を比較すると、最長処理時間は、

  • O(n2) ー 選択ソート, バブルソート
  • O(nlog⁡n)
  • O(n) ー 線形探索
  • O(log⁡n) ー バイナリサーチ
  • O(1)

最短処理時間は、

  • Ω(n2) ー 選択ソート
  • Ω(nlog⁡n)
  • Ω(n) ー バブルソート
  • Ω(log⁡n)
  • Ω(1) ー 線形探索、バイナリサーチ

　

Recursion（再帰関数）

再帰関数は、今いる関数を再度呼ぶことができる関数。一歩間違えれば無限ループに陥りそうだが、うまく行けばかなりエレガントにプログラムが書ける。

1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If Smith is on page
5      Call Mike
6  Else if Smith is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if Smith is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit

このプログラムが以下のように短縮できる。

1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If Smith is on page
5      Call Mike
6  Else if Smith is earlier in book
7      Search left half of book
8
9  Else if Smith is later in book
10     Search right half of book
11
12 Else
13     Quit

　

Merge sort（マージソート）

この再帰関数を用いたアルゴリズムがマージソート。

If only one number
  Return
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

先程の8桁の数字が並んでいる例を使って見てみると、

3 5 6 8 | 1 2 4 7

左と右に半分ずつ分け、それぞれをソートした後に、マージ（結合）する。

左と右の先頭の数字を比較し、小さい方を取る。この場合だと、3 と 1 を比較したら 1 の方が小さいので、これを最小値とする。

3 5 6 8 | _ 2 4 7

1

3 と 2 なら、2といった具合に繰り返す。

3 5 6 8 | _ _ 4 7

1 2

数回続ける。

_ 5 6 8 | _ _ 4 7

1 2 3
_ 5 6 8 | _ _ _ 7

1 2 3 4
_ _ 6 8 | _ _ _ 7

1 2 3 4 5
_ _ _ 8 | _ _ _ 7

1 2 3 4 5 6
_ _ _ 8 | _ _ _ _

1 2 3 4 5 6 7
_ _ _ _ | _ _ _ _

1 2 3 4 5 6 7 8

完成。Pseudocodeを見てみると、

If only one number
  Return
Else
    Sort left half of number
    Sort right half of number
    Merge sorted halves

もう一例。

6 3 8 5 2 7 4 1

左半分をソートする。

6 3 8 5
6 3
_ _ 8 5 2 7 4 1
3 6
_ _ _ _ 2 7 4 1
3 6 5 8
_ _ _ _ 2 7 4 1
_ _ _ _
3 5 6 8

続いて右半分。

_ _ _ _ _ _ _ _
_ _ _ _ 2 7 1 4
3 5 6 8
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
3 5 6 8 1 2 4 7

そして、結合する。

_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
_ _ _ _ _ _ _ _
1 2 3 4 5 6 7 8

他のアルゴリズムに比べてかなり効率的にソートできたことが分かる。よって、マージソートは O(nlog⁡n)、Ω(nlog⁡n) となる。

そして、マージソートは、ベストシナリオもワーストシナリオも同じ結果となったため、Θを用いてまとめて表せる。Θ(nlogn)

　

感想

今回の例では、8桁の数字の並び替えるだけだったが、これがグーグル検索の中からユーザーが調べるキーワードに当てはめる結果を返すプログラムとなると、膨大なデータの中からソートをしてヒットする検索結果を返さなければならない。よって、効率的に計算できるアルゴリズムが重要になる。一方で、多くの場合、そこまでデータがないのにエレガントなコードを書くことに執着するあまり、時間ばかりが過ぎていき、コストがかかってしまうということも発生する。よって、これらのトレードオフがあることを考えながらプログラムをすることも重要らしい。

早く膨大なデータを分析するアルゴリズムを書けるようになりたい…