ソート・探索・計算量 ― プログラムとアルゴリズムの基礎を身につける【データサイエンスを支える情報工学入門②】

前回は、コンピュータの基本的な仕組みとデータベースについて紹介しました。第2回となる今回は、データを扱うための基礎技術として、「アルゴリズム」と「プログラミング」の基本を見ていきます。地味に思えるかもしれませんが、この2つは「アルゴリズムとデータ構造をどうするか」がプログラミングの本質だと言われるくらい、コンピュータサイエンスの土台になる考え方です。

---

アルゴリズムとは何か

アルゴリズムとは、問題一般に対して、指示通りに実行すれば有限回数で解が得られる(解がない場合は、解がないことが示される)手順のことです。ちなみにこの「アルゴリズム」という言葉自体、9世紀のペルシャの数学者アル・フワーリズミー(al-Khwarizmi)という人名が語源になっているそうです。

もっとも古いアルゴリズムの一つとされるのが、紀元前300年ごろに登場したとされる「ユークリッドの互除法」です。これは、2つの整数の最大公約数(GCD)を求めるアルゴリズムで、手順は次の通りです。

入力を数 m, n とする

もし n = 0 ならば、解は m として停止

m を n で割った余りを a とすると、m を n に、n を a に更新し、1に戻る

この手順のポイントは、「任意の数に対して動作する」「必ず停止する」という2点です。実際に、48と18の最大公約数を求めてみましょう。

m=48, n=18 → 48÷18の余りは12 → m=18, n=12に更新

m=18, n=12 → 18÷12の余りは6 → m=12, n=6に更新

m=12, n=6 → 12÷6の余りは0 → m=6, n=0に更新

n=0になったので停止。答えはm=6

たしかに、48=6×8、18=6×3なので、最大公約数は6で正解です。2000年以上前に考案された手順が、今でも寸分違わず正しく動く、というのはアルゴリズムのおもしろいところだと思います。

---

ソートアルゴリズム ― データを並べ替える

アルゴリズムの中でも特によく使われるものの一つが「ソート(並び替え)」です。データをある規則に沿って並び替えること、たとえば数字の大小や辞書順で、小さい方から並べるのを昇順、大きい方から並べるのを降順と呼びます。

ソート自体は単純な操作に思えますが、「どういう手順でやれば素早く確実に仕事を終えられるか」を考えると、実は奥が深いテーマです。

バブルソートの仕組みを実際に動かしてみる

もっとも基本的なソートアルゴリズムの一つが「バブルソート」です。名前の由来は、データが泡(バブル)のように少しずつ移動していく様子から来ています。手順は次の通りです。

i を見ているデータの位置、j を何巡目か、とする。i=0, j=0 で開始

i番目のデータとi+1番目のデータを比較し、i+1番目の方が小さければデータを入れ換える

iの値を1つ増やす。iの値がデータ数 n-j に達したら手順4へ、そうでなければ手順2に戻る

jの値を1つ増やし、iの値を0に戻す。j=nに達したら終了、そうでなければ手順2に戻る

言葉だけだとイメージしづらいので、6人の学生の成績「83, 72, 80, 94, 76, 89」を昇順に並び替える例で、実際に動かしてみます。

1巡目:隣り合う2つの数を、左から順に比較していきます。

83と72を比較 → 83>72なので交換 → [72, 83, 80, 94, 76, 89]

83と80を比較 → 83>80なので交換 → [72, 80, 83, 94, 76, 89]

83と94を比較 → 83<94なので交換なし → [72, 80, 83, 94, 76, 89]

94と76を比較 → 94>76なので交換 → [72, 80, 83, 76, 94, 89]

94と89を比較 → 94>89なので交換 → [72, 80, 83, 76, 89, 94]

1巡した結果、もっとも大きい94が、一番右の正しい位置に「確定」しました。これがバブルソートの大事な性質で、1巡するごとに、その時点でまだ確定していない範囲の中の最大値が、必ず右端に押し出されていきます。

2巡目(94は確定済みなので、その手前までを比較):

72と80を比較 → 交換なし

80と83を比較 → 交換なし

83と76を比較 → 83>76なので交換 → [72, 80, 76, 83, 89, 94]

83と89を比較 → 交換なし

2巡した結果、[72, 80, 76, 83, 89, 94] となり、89も確定しました(94, 89が1番目、2番目に大きい数として決定)。

3巡目:同様に、72と80(交換なし)、80と76(交換して[72, 76, 80, 83, 89, 94])、80と83(交換なし)と進み、[72, 76, 80, 83, 89, 94] になります。この例ではここでソートが完了していますが、データによっては3巡では終わらないので、アルゴリズム自体はまだ終了と判定しません。実際に4巡目・5巡目と進めても、比較の結果は「交換なし」が続くだけで、最終的に6巡目まで確認して初めて、どんなデータであっても必ずソートが完了していることが保証されます。

最終的な結果 [72, 76, 80, 83, 89, 94] を氏名に戻すと、佐藤さん(72) 、鈴木さん(76) 、高橋さん(80) 、田中さん(83) 、渡辺さん(89) 、伊藤さん(94)の順に、無事成績の低い順に並び替えられました。

---

計算量という考え方

バブルソートで、6個のデータを並び替えるのに何回の比較が必要だったかを数えてみると、1巡目は5回、2巡目は4回、3巡目は3回、4巡目は2回、5巡目は1回で、合計 5+4+3+2+1=15回の比較が必要でした。これを一般化すると、n個のデータに対して、バブルソートはおよそ n(n-1)/2 回、つまりデータ数nの2乗にほぼ比例する回数の比較が必要になることがわかります。これを、計算量の考え方で「O(n²) 」(オーダーn二乗)と表現します。

これに対して、「クイックソート」などのより工夫されたアルゴリズムを使うと、平均的には「O(n log n) 」というオーダーで並び替えを終えることができます。nが小さいうちはn²もn log nもそれほど差がありませんが、nが大きくなればなるほど、この2つの間の差はどんどん開いていきます。バブルソートは仕組みがシンプルで理解しやすく、並列処理もしやすいという利点がある一方、大量のデータを扱う実務では、より計算量の少ないアルゴリズムが選ばれることが一般的です。

---

指数関数的爆発 ― 計算機で解けない領域

計算量がn²やn log nで済む問題はまだ「マシ」な部類です。世の中には、必要な計算量がeⁿ(指数関数)のオーダーになってしまうアルゴリズムも存在し、こうなると実用的な時間では計算が終わらなくなってしまいます。nが少し増えるだけで、計算量が爆発的に増えていくためです。さらに、階乗n!や、二重指数関数e^(eⁿ)になると、その爆発ぶりはもっと深刻です。

こうした「指数関数よりも速く解けるアルゴリズムが存在しない」問題は、事実上コンピュータで解けない問題として扱われます。裏を返せば、この「解くのに膨大な時間がかかる」という性質を逆手に取って、暗号技術などに応用されている、というのは興味深いポイントです(たとえば、大きな数の素因数分解が困難であることを安全性の根拠にしている暗号方式があります)。

---

(おまけ)選択ソート

バブルソートとは異なるアプローチのソートとして、「選択ソート」も簡単に紹介されていました。これは、まだ並び替えが済んでいない範囲の中から最小値(あるいは最大値)を探し出し、それを先頭(あるいは末尾)に移動する、という操作を繰り返すアルゴリズムです。バブルソートが「隣同士をこまめに比較・交換する」のに対し、選択ソートは「範囲内の最小値を1回で見つけて、1回の交換で確定位置に送り込む」というイメージの違いがあります。

---

データの検索(探索)

データを並べ替えるのと並んで基本的な操作が、データの中から目的のものを見つけ出す「検索(探索)」です。データの列の中から条件を満たすものを見つける(なかったら「ない」と答える)、という操作です。

もっとも単純な方法が「線形探索」です。データの列を左から(前から)順に、1つずつ調べていき、等しいものがあれば探索終了、最後まで見つからなければ「存在しない」と出力します。データの数がn個のとき、運が悪ければn回すべてを調べる必要があるため、計算コストはO(n)になります。

---

2分探索 ― ソート済みデータなら圧倒的に速い

線形探索よりもずっと効率的な方法が「2分探索」です。ただし2分探索を使うには、データがあらかじめ昇順(または降順)に並び替えられていることが前提になります。

手順は次の通りです。

データ列の真ん中(あたり)の数字を見て、目的のデータが左にあるか右にあるかを判別する

データがある方の範囲で、同じことを繰り返す

先ほどソートした「72, 76, 80, 83, 89, 94」という6個のデータの中から「76」を探す例で見てみます。

全体(72, 76, 80, 83, 89, 94)の真ん中あたりの値「80」と比較 → 76 < 80なので、左側「72, 76」を探索

「72, 76」の真ん中あたりの値「72」と比較 → 76 > 72なので、右側「76」を探索

残った「76」と比較 → 一致、見つかった!

たった3回の比較で見つけることができました。線形探索であれば最悪6回かかるところ、2分探索なら毎回探索範囲が半分になっていくため、データが大きくなればなるほど、その差は圧倒的になっていきます。データ数nが1,000,000(100万)の場合、log₂1,000,000 ≒ 20なので、2分探索を使えば線形探索と比べておよそ5万倍速く見つけられる、という計算になります。

---

アルゴリズムとデータ構造は「セット」で考える

アルゴリズムという考え方自体は古くから研究されており、「エラトステネスの篩(ふるい)」(素数を効率よく見つける古代のアルゴリズム)などもその代表例です。コンピュータ上でアルゴリズムを実装する際には、アルゴリズムだけでなく「データ構造」(データをどんな形でメモリ上に持たせるか)もセットで考える必要があります。さらに、並列処理(複数の計算を同時に行うこと)まで考慮に入れると、設計は非常に頭を使うものになります。

---

プログラムとは何か

ここまで見てきたアルゴリズムを、実際にコンピュータに実行させるための指示書が「プログラム」です。プログラムとは、計算機に指示を与えるための(人工)言語で書かれたもので、最終的にはプロセッサへの命令(機械語)に翻訳されます。曖昧さなく厳密に解釈できるように設計された人工言語であり(それでも解釈が一意に定まらない書き方ができてしまうことはあります)、用途に応じて様々な言語が存在します。プログラムを記述したものを、コード(ソースコード)とも呼びます。

代表的なプログラミング言語をいくつか紹介します。

C言語:手続き型言語で、多くの言語の基礎となりました。コンパイラによって、実行前にすべて機械語コードに変換される方式を取ります。

Java:オブジェクト指向の言語で、仮想マシン上で動作することで、プラットフォームに依存しない動作を実現しています(実行中に、プログラムの一つ一つを機械語に翻訳しながら実行する方式)。

Python:オブジェクト指向の軽量言語(スクリプト言語)で、強力なライブラリにより少ないコード量で書けることから、データサイエンスの分野で主流の言語になっています。

---

プログラムに共通する4つの制御構造

言語ごとの文法は違っても、プログラムには共通して次の4つの「制御構造」があります。

逐次処理:プログラムは上から順にコード(文)が実行される

条件分岐:条件に従って、処理を分けることができる

反復:同じ処理を何回も行うよう指示することができる

サブルーチン:処理の流れを保ちつつ、機能を分けることができる(メインの処理から、サブの処理を呼び出す形)

実際にC言語で書かれた、成績データをソートするプログラムの例では、この4つの構造がそれぞれ次のように使われています。

int score[] = {83, 72, 80, 94, 76, 89};

printf("-- before sort --\n");

for(int i=0; i<6; i++){ ← 反復処理:全データを表示

    printf("%d\n", score[i]);

}

for(int i=0; i<5; i++){ ← 反復処理(外側のループ)

    for(int j=(i+1); j<6; j++){ ← 反復処理(内側のループ)

        if(score[i]>score[j]){ ← 条件分岐:大小を比較

            int tmp = score[i]; ← 逐次処理:データの交換

            score[i] = score[j];

            score[j] = tmp;

        }

    }

}

printf("-- after sort --\n");

for(int i=0; i<6; i++){

    printf("%d\n", score[i]);

}

(なお、プログラム中の「=」の記号は、数学の「等しい」という意味ではなく、「代入する」という意味で使われている点に注意してください。)

この短いプログラムの中に、配列の全要素を順番に処理する「反復」、大小を比較する「条件分岐」、そして上から下へ実行が進んでいく「逐次処理」がすべて詰まっており、まさに「アルゴリズムとデータ構造の設計がプログラミングの本質」であることがよくわかる例になっています。

---

まとめ

今回は、アルゴリズムの定義とユークリッドの互除法という古典的な例から、ソートアルゴリズム(バブルソート・選択ソート)の具体的な動き、計算量(O記法)という考え方、線形探索と2分探索の効率の違い、そしてプログラムの基本的な仕組みと4つの制御構造まで、プログラミングとアルゴリズムの基礎を一通り見てきました。

「ビッグデータ(nが大きい)を扱うにはアルゴリズムの設計が重要で、eⁿのような指数関数的な計算量は実用的ではない」という点、そして「プログラミング言語はいろいろあっても、本質はアルゴリズムとデータ構造の設計にある」という点は、これからIT エンジニアとして学んでいくうえでも、繰り返し立ち返ることになりそうな、大事な視点だと感じました。

次回は、こうしたアルゴリズムの考え方をさらに発展させて、「最適化」という、膨大な選択肢の中から最良のものを見つけ出す技術について紹介していきます。