Week 3 アルゴリズム

ようこそ！

• 第0週では、アルゴリズムという概念を紹介しました。これは、入力を受け取り、出力を生成するブラックボックスのようなものです。

• 今週は、擬似コードから実際のコードへと進み、アルゴリズムへの理解を深めていきます。

• また、これらのアルゴリズムの効率性についても考えていきます。実際には、先週学んだいくつかの概念を、アルゴリズムの構築にどのように活用できるかという理解を深めていきます。

コースの序盤で紹介した以下のグラフを思い出してください。

• 今週進めるにあたって、アルゴリズムが問題に対してどのように機能するかが、問題を解くのにかかる時間をどのように決定するのかを考えてみてください。アルゴリズムは、限界までどんどん効率的になるように設計することができます。

• 今日は、アルゴリズムの設計と、その効率の測定方法に焦点を当てます。

線形探索（Linear Search）

• 先週、*配列（array）*という概念を紹介したのを覚えているでしょうか。これは、メモリ上の連続したブロックが隣り合わせに並んだものです。

比喩的に、配列を以下のような7つの赤いロッカーの並びとして想像してみてください。

• 一番左の列は 位置0 または 配列の先頭 と呼ばれます。一番右の列は 位置6 または 配列の末尾 と呼ばれます。

• 「配列の中に50という数字はあるか？」という本質的な問題を考えてみましょう。コンピュータは、50が入っているかどうかを確認するために、各ロッカーの中を見る必要があります。このように、特定の数値、文字、文字列、その他の項目を見つけるプロセスを 探索（searching） と呼びます。

この配列をアルゴリズムに渡し、アルゴリズムがロッカーの中を探索して、50という数字がドアの向こうにあるかどうかを確認し、true（真）またはfalse（偽）という値を返すようにすることができます。

このタスクを実行するためにアルゴリズムに与えるさまざまな指示を、次のように想像できます。

For each door from left to right
    If 50 is behind door
        Return true
Return false

上記の指示は 擬似コード（pseudocode） と呼ばれるものであることに注意してください。これは、コンピュータに提供できる指示を人間が読める形にしたものです。

コンピュータ科学者は、その擬似コードを次のように翻訳することができます。

For i from 0 to n-1
    If 50 is behind doors[i]
        Return true
Return false

上記はまだコードではありませんが、最終的なコードがどのようになるかをかなり正確に近似していることに注目してください。

二分探索（Binary Search）

二分探索（Binary search） は、50を見つけるというタスクに採用できるもう一つの 探索アルゴリズム です。

ロッカー内の値が小さい順に並んでいると仮定すると、二分探索の擬似コードは次のようになります。

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

コードの用語を使って、アルゴリズムをさらに次のように修正できます。

If no doors left
    Return false
If 50 is behind doors[middle]
    Return true
Else if 50 < doors[middle]
    Search doors[0] through doors[middle - 1]
Else if 50 > doors[middle]
    Search doors[middle + 1] through doors[n - 1]

このコードの近似を見ることで、実際のコードがどのようになるか、ほぼ想像できることに注目してください。

実行時間（Running Time）

• アルゴリズムが問題を解くのにどれくらいの時間がかかるかを考えることができます。

実行時間（running time） には、ビッグオー（big O） 記法を用いた分析が含まれます。次のグラフを見てください。

• コンピュータ科学者は、アルゴリズムの数学的な効率性を極めて具体的に述べるのではなく、さまざまな実行時間の オーダー（次数） という観点から効率性を議論します。

• 上のグラフでは、最初のアルゴリズムは \(O(n)\)、つまり nのオーダー です。2番目も \(O(n)\) です。3番目は \(O(\log n)\) です。

アルゴリズムの効率を示すのは、曲線の形状です。よく見かける実行時間には以下のようなものがあります。

• \(O(n^2)\)

• \(O(n \log n)\)

• \(O(n)\)

• \(O(\log n)\)

• \(O(1)\)

• 上記の実行時間のうち、\(O(n^2)\) が最も遅い実行時間と考えられています。\(O(1)\) が最も速いです。

• 線形探索は、最悪の場合に実行に n ステップかかる可能性があるため、\(O(n)\) のオーダーでした。

• 二分探索は、最悪の場合でも実行にかかるステップ数がどんどん少なくなっていくため、\(O(\log n)\) のオーダーでした。

• プログラマーは、最悪の場合、すなわち 上界（upper bound） と、最善の場合、すなわち 下界（lower bound） の両方に関心があります。

• \(\Omega\) 記号は、アルゴリズムの最善の場合を表すのに使われます（例：\(\Omega(\log n)\)）。

• \(\Theta\) 記号は、上界と下界が同じである場合、つまり最善の場合と最悪の場合の実行時間が同じである場合を表すのに使われます。

漸近的記法（Asymptotic notation） は、入力が大きくなるにつれてアルゴリズムがどの程度うまく機能するかを示す尺度です。

• コンピュータサイエンスの知識を深めるにつれて、将来のコースでこれらのトピックをより詳細に探究することになります。

search.c

ターミナルウィンドウで code search.c と入力し、次のようなコードを書くことで、線形探索を実装できます。

// Implements linear search for integers

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

int main(void)
{
    // An array of integers
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

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

int numbers[] で始まる行により、配列の各要素の値を、配列の作成時に定義できることに注目してください。そして、for ループの中で線形探索を実装しています。return 0 は成功を示してプログラムを終了するために使用されます。return 1 はエラー（失敗）を伴ってプログラムを終了するために使用されます。

• これで、自分たちで C 言語を使って線形探索を実装できました！

配列の中から文字列を検索したい場合はどうすればよいでしょうか？コードを次のように修正してください。

// Implements linear search for strings

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

int main(void)
{
    // An array of strings
    string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};

    // Search for string
    string s = get_string("String: ");
    for (int i = 0; i < 6; i++)
    {
        if (strcmp(strings[i], s) == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

このプログラムの前のバージョンのように == を利用することはできないことに注意してください。代わりに、string.h ライブラリに含まれる strcmp を使用します。strcmp は、文字列が同じであれば 0 を返します。また、文字列の長さ 6 がハードコードされていますが、これは良いプログラミングの習慣ではありません。

• 実際、このコードを実行すると、この文字列の配列を反復処理して、特定の文字列が含まれているかどうかを確認できます。ただし、プログラムがアクセスすべきでないメモリの一部に触れた場合に発生する セグメンテーション違反（segmentation fault） が表示された場合は、上記の i < 6 が i < 7 になっていないか確認してください。

• strcmp については、CS50 マニュアルページで詳しく知ることができます。

phonebook.c

数値と文字列の両方のアイデアを一つのプログラムにまとめることができます。ターミナルウィンドウに code phonebook.c と入力し、次のようなコードを書きます。

// Implements a phone book without structs

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

int main(void)
{
    // Arrays of strings
    string names[] = {"Yuliia", "David", "John"};
    string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"};

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(names[i], name) == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Yuliia の番号は +1-617 で始まり、David の電話番号も +1-617 で始まり、John の番号は +1-949 で始まっていることに注目してください。したがって、names[0] は Yuliia であり、numbers[0] は Yuliia の番号です。このコードにより、電話帳から特定の人物の番号を検索することができます。

このコードは機能しますが、多くの非効率性があります。実際、名前と電話番号が互いに対応しなくなる可能性があります。人物と電話番号を関連付けることができる独自のデータ型を作成できれば素晴らしいと思いませんか？

構造体（Structs）

• C 言語では、struct（構造体）を介して独自のデータ型を作成できることがわかりました。

内部に name（名前）と number（番号）を持つ person という独自のデータ型を作成できれば便利ではないでしょうか？以下を考えてみてください。

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

これが、name という文字列と number という別の文字列を持つ person という独自のデータ型をどのように表現しているかに注目してください。

電話帳プログラムを次のように修正することで、以前のコードを改善できます。

// Implements a phone book with structs

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

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

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

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

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

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

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(people[i].name, name) == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

コードが typedef struct で始まり、person という新しいデータ型が定義されていることに注目してください。person の中には、name という文字列と number という文字列があります。main 関数では、まず、サイズが 3 の person 型の people という名前の配列を作成します。次に、people 配列内の人々の名前と電話番号を更新します。最も重要なのは、people[0].name のような ドット記法 により、0番目の位置にある person にアクセスし、その人物に名前を割り当てることができる点に注目してください。

ソート（Sorting）

ソート（sorting） とは、未整列の値のリストを受け取り、このリストを整列されたリストに変換する行為です。

• リストがソートされていると、そのリストの探索はコンピュータにとって負荷がはるかに少なくなります。二分探索はソートされたリストには使用できますが、未整列のリストには使用できないことを思い出してください。

• ソートアルゴリズムには、さまざまな種類があることがわかっています。

選択ソート（selection sort） は、そのようなソートアルゴリズムの一つです。

配列を次のように表すことができます。

擬似コードによる選択ソートのアルゴリズムは次のとおりです。

For i from 0 to n–1
    Find smallest number between numbers[i] and numbers[n-1]
    Swap smallest number with numbers[i]

これらのステップをまとめると、リストの最初の反復処理には n - 1 ステップかかりました。2回目は n - 2 ステップかかりました。この論理を進めると、必要なステップ数は次のように表せます。

(n - 1) + (n - 2) + (n - 3) + ... + 1

• これは n(n-1)/2、あるいはもっと単純に \(O(n^2)\) と簡略化できます。最悪の場合、つまり上界において、選択ソートは \(O(n^2)\) のオーダーです。最善の場合、つまり下界において、選択ソートは \(\Omega(n^2)\) のオーダーです。

バブルソート（Bubble Sort）

バブルソート（bubble sort） もソートアルゴリズムの一つで、要素の入れ替えを繰り返して、より大きな要素を末尾へと「泡（bubble）」のように移動させることで機能します。

バブルソートの擬似コードは次のとおりです。

Repeat n-1 times
    For i from 0 to n–2
        If numbers[i] and numbers[i+1] out of order
            Swap them
    If no swaps
        Quit

• 配列をさらにソートしていくと、配列のより多くの部分がソート済みであることがわかってくるため、まだソートされていない数値のペアだけを見ればよくなります。

バブルソートは次のように分析できます。

  (n – 1) × (n – 1)
  n2 – 1n – 1n + 1
  n2 – 2n + 1

あるいは、もっと単純に \(O(n^2)\) です。

• 最悪の場合、つまり上界において、バブルソートは \(O(n^2)\) のオーダーです。最善の場合、つまり下界において、バブルソートは \(\Omega(n)\) のオーダーです。

• これらのアルゴリズムの比較を 視覚化（visualize） することができます。

再帰（Recursion）

• ソートの効率をどのように改善できるでしょうか？

再帰（recursion） は、プログラミングにおける概念で、関数が自分自身を呼び出すことを指します。これは、以前に以下のようなものを見たときに登場しました。

If no doors left
    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

この問題の、より小さく、より小さな繰り返しに対して search を呼び出していることに注目してください。

同様に、第0週の擬似コードでも、再帰が実装されている箇所が見て取れます。

1  電話帳を手に取る
2  電話帳の真ん中を開く
3  ページを見る
4  その人がページにいれば
5      その人に電話する
6  そうでなく、その人が本の前の方にいれば
7      本の左半分の真ん中を開く
8      3行目に戻る
9  そうでなく、その人が本の後ろの方にいれば
10     本の右半分の真ん中を開く
11     3行目に戻る
12 そうでなければ
13     あきらめる

このコードは、再帰的な性質を強調するために、次のように簡略化できたはずです。

1  電話帳を手に取る
2  電話帳の真ん中を開く
3  ページを見る
4  その人がページにいれば
5      その人に電話する
6  そうでなく、その人が本の前の方にいれば
7      本の左半分を探索する
9  そうでなく、その人が本の後ろの方にいれば
10     本の右半分を探索する
12 そうでなければ
13     あきらめる

第1週で、次のようなピラミッド構造を作りたいと考えたことを思い出してください。

  #
  ##
  ###
  ####

ターミナルウィンドウに code iteration.c と入力し、次のようなコードを書きます。

// Draws a pyramid using iteration

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

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // Draw pyramid of height n
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

このコードがループを使ってピラミッドを構築していることに注目してください。

これを再帰を使って実装するには、ターミナルウィンドウに code recursion.c と入力し、次のようなコードを書きます。

// Draws a pyramid using recursion

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

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // If nothing to draw
    if (n <= 0)
    {
        return;
    }

    // Draw pyramid of height n - 1
    draw(n - 1);

    // Draw one more row of width n
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

ベースケース（base case） が、コードが永久に実行されないようにしていることに注目してください。if (n <= 0) という行は、問題が解決されたため、再帰を終了させます。draw が自分自身を呼び出すたびに、n-1 を指定して自分自身を呼び出します。どこかの時点で n-1 は 0 に等しくなり、draw 関数が返され（return）、プログラムが終了します。

マージソート（Merge Sort）

• ここで、より効率的なソートアルゴリズムを求めて再帰を活用し、マージソート（merge sort） と呼ばれる非常に効率的なソートアルゴリズムを実装してみましょう。

マージソートの擬似コードは非常に短いです。

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

次の数値のリストを考えてみましょう。

  6 3 4 1

まず、マージソートは「これは一つの数字か？」と尋ねます。答えは「いいえ」なので、アルゴリズムは続行します。

  6 3 4 1

次に、マージソートは数値を真ん中で分割し（またはできるだけ真ん中に近く）、数値の左半分をソートします。

  6 3 | 4 1

第三に、マージソートは左側のこれらの数値を見て、「これは一つの数字か？」と尋ねます。答えはいいえなので、左側の数値を真ん中で分割します。

  6 | 3

第四に、マージソートは再び「これは一つの数字か？」と尋ねます。今回は答えは「はい」です！したがって、このタスクを終了し、この時点で実行していた最後のタスクに戻ります。

  6 3 | 4 1

第五に、マージソートは左側の数値をソートします。

  3 6 | 4 1

ここで、左側のソートが完了したので、擬似コードの中断した場所に戻ります。右側の数値に対しても、ステップ3から5と同様のプロセスが発生します。その結果、次のようになります。

  3 6 | 1 4

これで両方の半分がソートされました。最後に、アルゴリズムは両側をマージ（併合）します。左側の最初の数字と右側の最初の数字を見ます。小さい方の数字を最初に置き、次に2番目に小さい数字を置きます。アルゴリズムはすべての数値に対してこれを繰り返し、結果は次のようになります。

  1 3 4 6

• マージソートが完了し、プログラムは終了します。

• マージソートは非常に効率的なソートアルゴリズムで、最悪の場合は \(O(n \log n)\) です。最善の場合も依然として \(\Omega(n \log n)\) です。なぜなら、アルゴリズムは依然としてリストの各場所を訪れる必要があるからです。したがって、最善の場合と最悪の場合が同じであるため、マージソートは \(\Theta(n \log n)\) でもあります。

• 最後に 視覚化（visualization） が共有されました。

まとめ

このレッスンでは、アルゴリズム的思考と独自のデータ型の構築について学びました。具体的には、以下について学びました。

• アルゴリズム

• ビッグ O 記法

• 二分探索と線形探索

• バブルソート、選択ソート、マージソートを含む、さまざまなソートアルゴリズム

• 再帰

それでは、また次回！