ハーバード大学 コンピュータサイエンス講座 CS50 2020 Lecture 3 - Algorithms 受講メモ
CS50 2020 Lecture 3 - Algorithms
logとか、すごい久しぶりに見た…
ちょっと数学とかも復習したくなってきたなあ…
week2ではラップトップやデスクトップ、携帯電話に搭載されているコンピュータのメモリについて、覆いの下を見てみた。
私たちはメモリをより芸術的に、単なるバイトのグリッドとして考えた
更にメモリの連続した1つのブロック、別名「配列」に注目すると、この配列の中に様々な値を格納することができた
今日は、多くのプログラミング言語の特徴である「コンピュータのメモリに連続して物事を保存できる」という性質を引き続き活用していきましょう。
というのも、この非常にシンプルなレイアウトがあらゆる種類の強力な機能を可能にするからです。
配列の弱点
私たちは画面のグリッドをパッと見て「この配列は7つの値を格納できるんだな」、と直感的に把握することができる
コンピュータは厳密にアルゴリズムに従うことしかできない
⇒どんなに強力なコンピュータでも技術的には一度に配列の中の1つの場所しか見ることができない
私たちが画面をパッと見てすべてを把握するように、コンピュータは一度にすべてを把握することはできない
⇒右から左へ、上から下へ…というように、より整然とした方法で行わなければならない＝アルゴリズムでなければならない
今日はこの概念を公式化し、配列を一度に見ることはできず、一度に見ることができるのは配列の一箇所だけであるという事実を隠すことにする
例えばweek0で扱った電話帳の問題
最も素朴な方法は左から右に1ページずつ読み進めていくこと
単純化すると「検索」の問題
解決すべき問題として考えてみると、まず入力が与えられる。例えば数字の配列であったり、Googleの場合はウェブページの配列であったりする
目的は何らかの出力を得ること
問題の入力が値の配列であれば、出力はbool値のような単純なものになるかもしれない
＝yesかnoか。（探している値を検索して見つけることができるかどうか)
実行時間
アルゴリズムの実行時間とは、何ステップかかるか、何秒かかるか、何回反復するか、といったこと⇒単位はなんでもよく、あるアルゴリズムにどれだけ時間がかかるか？ということ
斜体のo(オーダ) コンピュータ科学者や一部の数学者はアルゴリズムの実行時間を表すのにこの記号を頻繁に使用する
nページの電話帳から検索する場合、最悪な実行時間はnになる
①1ページずつ見ていく⇒n
②1ページ飛ばし⇒n/2
③半分に割っていく⇒log_2 n
実行時間を厳密に数学的に求める必要は無い
代わりにやることは、アルゴリズムの実行時間がどのようなオーダか、大まかに速いか遅いかをnをプレースホルダとして把握すること
上の3つのアルゴリズムの実行時間をコンピュータ科学者は次のように表現する
①O(n)
②O(n)
③O(log n)
おおまかに言って、という意味でO(ビッグ・オー)
実際にかかる時間のグラフで見ると、①と②は広い視点で見ると大して変わらないように見える
⇒①と②はどちらもO(n)になる
コンピュータ科学者は細かいことは気にしない
③だけは画期的
コンピュータ科学者は、「1/2」のような定数要素を捨てて、その数式の中のどの値が最も大きく成長し、最も速く成長するのか、といったような、支配的な要素だけに注目する傾向がある
nもn/2も、支配的なのはnの大きさがどうなるか？なので、O(n)
対数の基数も2である必要はないので、O(log n)
アルゴリズムの効率性を考える時に、数学的に深く掘り下げて時間を無駄にする必要はない
時間の経過とともに支配的になる変数(この場合はn)の観点から物事を説明すれば十分
O(1)が考えられる最良のアルゴリズム＝1ステップで終わる
もう一つの表現Ω
オーダは実行時間の上限、つまりアルゴリズムが最大で何ステップ、最大でどの程度時間がかかるかを表す
Ωはその逆で、アルゴリズムの下限値を表す
「私のアルゴリズムは最小何ステップかかるか」といったように下限値を示したい場合に同じ数式のOの代わりにΩで表記
電話帳を1ページずつ検索して自分の電話番号を探す＝線形探索
今日は電話帳のページやボード上の配列を一度に見ることができる人間とは違い、もっと几帳面にもっと慎重にweek0のアイデアを擬似コードではなく実際のCコードに変換する
今学期はハーバード大学のキャンパス内にあるアメリカン・レパートリー・シアターで、私一人では到底できないようなアーティスト志向の強いチームとのコラボレーションを行っている
かつてこの劇場の様々な演劇で使われた7つの素晴らしいドアがある
7つのドアの後ろにはそれぞれ番号がある
配列の中の数字を探したいとき、それは閉じられたドアの後ろにある数字を探すのと同じだということを強く印象づけることができる
7つのドアをパッと見ただけではその中にある番号を知ることはできない
左から右へ、右から左へ、真ん中から外側へ…と扉を調べていかなければならない
アルゴリズムを考え出し、最終的にコードに変換する
例えば0という番号を7つのドアから探すにはどうすれば良い？
学生⇒0は小さそうだから一番左を開ける⇒4
次は真ん中⇒8⇒次は左に進んで⇒8…
一番右が0だった
↑これはどんなアルゴリズムだった？
あちこち飛び回っていただけ
ドアの後ろに配置された番号に規則性は無かった
⇒あちこち飛び回るのも悪くはなかった
一方で、あちこち飛び回る場合は以前に開けたドアの番号を覚えておかなければならない
⇒たくさんの変数が必要になりそう…
最もシンプルな解決策はweek0に始めた方法だったかもしれない
これらの数字について何も知らなければ、正直なところ、week0と同じ線形探索でそれぞれのドアの後ろにある値を1つずつチェックして、最終的に見つかることを期待するしかない
↑これでは時間がかかってしまう。最悪すべてのドアを開かなければならない
あちこち飛び回ったり勘をきかせることもできるが、それではアルゴリズムとは呼べない
段階を踏むことが大切
線形探索については、まず擬似コードで実装することを提案する
▼擬似コード
For i from 0 to n-1
If number behind i'th door
return true
return false
i番目のドアの後ろに数字があればtrueを返し、そうでなければ最後にfalseを返す
forループは左から右へ…のような線形探索に向いている
elseでないことが重要⇒ある数字が現在のドアの後ろに無いからといって、このアルゴリズムを早々に中断したくない
基本的にはn個のドアをすべてチェックした後、アルゴリズムの最後まで待って、それでも気になる数字が見つからなければ、その時だけfalseを返すようにしたい
よくある間違い⇒ifを使うときはelseも必要、という思い込みで考えてしまう
上記のコードの最後にあるreturn falseはキャッチオール(ガラクタ入れ)のようなもの
上記の線形探索の実行時間はどのようなものか？
最悪の場合、n個のドアからある特定の数字を見つけるのに何ステップかかる？
O(n)
n個すべてのドアを開けるまで見つからないかもしれない
実行時間の下限値Ωは？
Ω(1)
運良く最初の場所にお目当ての数字があるかもしれない
下限のΩ(1)から上限のO(n)までが線型探索の実行時間の範囲となる
我々には線形探索とは異なるツールがある
二分探索(バイナリサーチ)
電話を半分にして、また半分にして、という分割統治型の第三のアルゴリズム
7つのドアの後ろの数字をリセット⇒今度は6を探す
前回、なぜ私たちはランダムに検索する以上のことができなかった？
数字やドアの配列の何が原因で二分探索ができなかったのか？
↑数字がソートされているかどうかわからなかったから
⇒今回は数字がソートされている
①7つのドア(サイズ7の配列)の真ん中を開ける⇒5
6は5より大きい
②5より右の3つのドア(サイズ3の配列)の真ん中を開ける⇒7
6は7より小さい
③5と7の間のドア(サイズ1の配列)に6が入っていると確定
すべての数字がソートされていることがわかっていたため、二分探索により、3つのドアを開けるだけで済んだ
数字がソートされていれば、線形探索より優れた、より効率的な、より良く設計された二分探索というアルゴリズムを適用することができる
二分探索の擬似コード
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
・その数字が真ん中のドアの後ろにあったらtrueを返す
・数字が真ん中のドアの後ろにあるものより小さければ、電話帳と同じように、左に行って、配列の残りのドアの左半分を探す
・数字が真ん中のドアの後ろにあるものより大きければ、電話帳と同じように、右に行って、配列の残りのドアの右半分を探す
・何らかの理由でドアの中に6がなく、これ以上探すドアが無い場合には明確に「return false」と言えるよう、状況を処理できる必要がある
この二分探索の実行時間の上限はどう表される？
O(log n)
ある大きさのリストや配列を、探している数字が見つかるまで、あるいは最終的にその数字が無いことがわかるまで、半分ずつに分割できる最大の回数になる
二分探索の実行時間の下限は？
Ω(1)
線形探索より二分探索の方が優れたアルゴリズム
64個のドアがあって、1つのドアを開けるのに1秒かかる場合
線形探索 1つ1つ端から開けていく⇒64秒かかる
二分探索 64 32 16 8 4 2 1 ⇒6秒で終わる
線形探索のコードを書いてみる
▼numbers.c
#include <cs50.h>
#include <stdio.h>
int main(void)
{
int numbers[] = {4,6,8,2,7,5,0};
for(i = 0; i <7; i++)
{
if(numbers[i] == 0)
{
printf("Found\n");
return 0;
}
}
printf("Not found\n");
return 1;}
なぜ0や1を返している？
int mainは値を返す
0は問題なく終了したことを意味する
1は問題があったが、終了することを意味する
return 0;はループを終了させるために必要
return 1;は厳密には必要ない＝「printf("Not found\n");」でプログラムはどっちみち終了する←もし無かったら、プログラムの終了ステータスが無いので、何かが成功したのか失敗したのかをコンピュータに知らせることができない
▼名前を探すプログラム name.c
#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"))
printf("Found\n");
return 0;
}
printf("Not found\n");
return 1;}
string names[] = {"Bill","Charlie","Fred","George","Ginny","Percy","Ron"};
名前はアルファベット順に並んでいるので、二分探索も可能
⇒今回は線形探索を行う
C言語では二つの文字列を比較するのに「==」は使えない
※intやcharでは「==」を使える
Pythonでは文字列の比較に「==」を使えるが、C言語では不可←次回詳しく解説する
C言語の場合、string.hの関数strcmp「str compare」を使う
別の文字列と比較したい文字列を渡すことができる
if(strcmp(names[i] , "Ron")
↑names[i]とRonを比較⇒同じ場合は「0」を返す
最初の文字列がアルファベット順で2番目の文字列よりも前に来る場合、この関数は負の値を返す
最初の文字列がアルファベット順で2番目の文字列よりも後に来る場合、この関数は正の数を返す
0か、負の値か、正の値か、の3つの場合しかない
正・負それぞれの値が何なのかは明示されない⇒正なのか負なのかチェックするだけ
※厳密にはアルファベット順かどうかではなく、2つの文字列のすべての文字を左から右に見て、それらのASCII値をチェックし、そのASCII値を1文字ずつ比較している
質問コーナー
Ronを大文字にしても見つかる？
「RON」⇒Foundになる
？？？ ⇒実は先生が間違ってた
他の名前にしても、「Found」になってしまう なぜ？？？
strcmpの結果がちゃんと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;}
▼オリジナルのデータ型
今まではintやchar、floatなどC言語に元々あったデータ型を使ってきた
単なる数字や名前の羅列ではなく、本格的な電話帳のようなものを実装したい
電話帳は数字と名前がセットになっている⇒2つのアイデアを合わせて使いたい
数字と名前を同時に格納できるような、何らかの構造を持ったデータ型があれば良いのでは？
実際、C言語にpersonというデータ型があって、電話帳のように名前と番号の両方を持つ人を表現したい場合、person型の変数を呼び出すことで実際にそれを実装してコードを書けるようになったら良いと思わないか？
C言語の設計者はperson型まで用意してはくれなかったが、私たちがそれを作る手段は用意してくれていた
電話帳の場合、名前も番号もstring＝文字列
なぜ番号も文字列？←番号を整数として扱ったりしない(計算しない)から
アメリカの電話番号には文字や記号も含まれていたりする⇒そもそも整数だけで表現できない
社会保障番号やクレジットカード番号も整数でなく文字列として扱う
二つの異なる型の値をカプセル化した独自のデータ型を作りたい
typedef struct
{
string name;
string number;
}
person;
typedefは型を定義する⇒ある種の構造体になる
構造体とはその中に２つ以上の値を持っている
typedefを使い、さらにstrucctキーワードを使うことで、他の複数のデータ型を組み合わせた構造を持つカスタム型を作ることができる
「typedef struct」、{}の中に1行ごとに必要なデータ型とそれらのデータ型に付ける名前を指定する(nameとnumber)
{}の後に実際に作成したいデータ型の名前である「person」という言葉を入れる
まずは↑の機能の有用さを知るために、あえて間違った方法でコードを書いてみる
▼phonebook.c
#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;}
最初に二つの配列を宣言⇒namesの最初の名前がnumbersの最初の数字に対応し、二番目の名前が二番目の数字に対応しているという一種の握手のような合意をしようとしている
week0では口頭で説明していた電話帳をコードで実装することができた
2つの並列な配列を使って、名前の最初の要素と番号の最初の要素を並べるという自主管理システムを使うことで、この電話帳を実装することができる
実行すると、確かにDavidの電話番号が表示される⇒検索できた
しかし、このコードは長期的にはベストなソリューションではなさそう…
なぜ？
先ほどの「typedef struct」を使った構造体ではないので、名前と番号という二つの配列が実際にはリンクされていない⇒どちらかの配列の順番を間違えたり、誤った情報を間違えて入れたりすると成立しなくなる
自己防衛的なコードを書くことによって、自分を守ることができ、コードがより正確になり、現実世界でのプログラミングプロジェクト、研究プロジェクト、フルタイムの仕事、個人的なプロジェクトなどにおいて、必要に応じてより簡単に協力することができるようになる
一般的に、自分の事も他人の事も信用すべきではない
コードを書いている相手には、できるだけ多くの防御メカニズムで備えるべき
上のコードの場合、二つの配列に入る情報が増えるほど順番を間違える確率どんどん高くなっていく⇒関連するデータをまとめることでそれを防ぐ
二つの情報をperson型にまとめてセットにする
ファイルの先頭、mainの前で構造体をtypedefして、その中に先ほどと同じように、気になる二種類のデータ、文字列型namesと文字列型numberを入れる
typedef struct
{
string name;
string number;
}
person;
重要なのは、この時点でnameもnumberも配列ではなく、一つの名前、一つの番号、という文字列であること
コードを少し変える↓
person型のpeople配列を宣言
person people[2];
二人の人間、BrianとDavidを用意する
people配列にデータを入れていく
person[0].name = "Brian"
一人目の人間の名前にBrianを入力する
番号の入力も名前と同じ
person[0].number = "+1-617-495-1000"
一人目の人間の番号に"+1-617-495-1000"を入力する
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";if(strcmp(names[i], "Brian") == 0)
↑のnames[i]をpeople[i].nameに変更する
データ構造の中にはフィールドや変数がある
そこでドット表記を使い、people配列のi番目の人に入り、その名前を"David"と比較する
printf("Found%s\n",numbers[i]);
↑ここのnumbers[i]もpeople[i].numberに変更する
#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, "Brian") == 0)
{
printf("Found%s\n",people[i].number);
return 0;
}
}
printf("Not found\n");
return 1;}
より複雑になったが、デザインは良くなった
一つの変数の中に、例えばpeople[0]、people[1]というように、BrianやDavid、あるいはこのプログラムに入力する可能性のある他の誰かに関して、私たちが気にかけるすべての情報をカプセル化することができているから
GoogleやFacebookがアカウントを運用する方法もこのやり方と同じ
ユーザー名とパスワード、投稿履歴、友達、フォロワーなど複数のデータが関連付けられている
ユーザー名、パスワード、投稿履歴…といったデータをそれぞれ別々に管理していたとしたら、とんでもないことになっていただろう←カプセル化することによって情報を管理しやすくしている
質問のコーナー
新しいデータ構造を定義するのは、mainの外側、例えばヘッダの中で行うのが一般的なのか？
yes。今回のプログラムではmain関数一つしかなかったからそれほど意味はなかったが、これからプログラムが複雑化すれば、関数も増える⇒できればすべての関数で定義したデータ構造を使いたくなる⇒外側で定義すればすべての関数で使える
将来的には独自のヘッダファイル(cs50.hやstdio.hなど)を作り、様々な場面でオリジナルのデータ構造を応用することができる
ティアゴという学生⇒この講義はちゃんと必要な情報を与えているのか？課題を進められないので、情報が不足していると感じる…
先生⇒至極妥当な質問。week0で消火ホースの例えを出したが、この講義はとても早いスピードで進んでいるし、たくさんの情報(新しい構文、新しいアイデア)が一度に出てくる
しかし、problem setの中の個々の問題に関しては、一歩一歩進んでいかなければならないことを理解してください。
講義や例題はライブやコースのウェブサイトにあらかじめ用意されている例題を使って復讐できるようになっているが、その中には必ず小さなヒントが含まれている
labなど他のリソースを利用することで追加の構成要素も見ることができる
これは私の同僚であるダグ・ロイドが制作した短いビデオで、特定のトピックに関するもの
今日以降、線形探索や二分探索、その他の多くのアルゴリズムについてダグが異なる視点で作成したショートビデオを見ることができる
エラーで値を返すのは将来どのように役立つ？
これから複雑なコードを書くようになると、あれが上手くいかなかった、これが上手くいかなかった…というのを追跡する必要が出てくる⇒その時に役立つ
今回はBrianとDavidだけだが、もっと10人以上に増えたら？
今は一人ずつハードコーディング(直接入力)しているが、
数週間後には、同じ情報を表計算ソフトやCSVファイル(Comma Separated Values)、あるいはFacebookやGoogleが使用するような適切なデータベースに保存する方法を見ることになる
▼データのソート
ソートされていないデータでは線形探索しかできなかったが、ソートされていれば二分探索で実行時間を大幅に短縮できる
ソートはどう行うか？
いつも通りインプットとアウトプットで考えると…
インプット＝ソートされていないランダムな値の束
アウトプット＝ソートされた値の束
間で何をすればいいか？
ソートされていない入力を入力の配列という観点から考えると、結局のところ、これまで見てきた中で最も便利なメカニズムは、1つの変数名を使って一度にたくさんの値を受け渡すことだと思う
6 3 8 5 2 7 4 1 ⇒■⇒ 1 2 3 4 5 6 7 8
左右ともにサイズ8の等価な配列
そもそもソートしなくても良い、線形探索で良い場合とはどんな時？
比較的小さなデータセット(少ないデータ)を扱うのであれば、最高に効率的な二分探索を行うためにソートする時間を費やすより、単純で非効率ではあるがすぐに行える線形探索を行った方が良い
←トレードオフの問題で、線形探索を選択する方が正しい場合もある。時間、複雑さ、使用するスペースやメモリとのトレードになる。
優れたプログラマーになるための技術の一つは、そのトレードオフの境界線をどう定めるか？ということでもある。
しかしながら、線形探索で済むような小さなデータセットを扱っていれば良い、というケースはほとんど無い⇒GoogleやFacebookのように何千、何百万ものデータを扱わなければならず、しかもそれを何度も検索する必要がある
←正しいだけでなく効率的なコードを作り、その効率性から何度も恩恵を受けられるようにすべき
▼数字を並べ替える
ドアの後ろのブライアンが実際に8つの数字を並べ替える
↑どうやった？
最終結果を得るためにブライアンは段階的に行ったことは？
小さな値を探して左に移動させ、大きな値を探して右に移動させるというように、段階的に続けた。つまり、効果的に数字を一つずつ選択して、正しい場所に置くということ
配列の中で最小の値を探し、それを左端に持ってくる←配列を俯瞰できる人間だから可能なソリューション⇒コンピュータが行うには？
ドアの後ろにある数字のように、一度に一つの数字しか見られないとしたら、どうやって最小の数字を見つけて配置する？
どうやって最小の数字を見つける？
左端から1つずつ数字を見ていく⇒それを記憶し、次の数字と比較して最小の数字かどうか評価する⇒最初の数字を記憶し、右端まで同じことを続ける
どうやって配置？
左端にスペースが無いので、最小の数字以外の数字をすべて右に一つずつずらしていく…←それは仕事の量が多くなってしまうので、ほかの方法は？
⇒左端の6だけを取り外し、そこに最小の1を配置する⇒6は元1があったスペースに入れる
左端が最小の1になったと確定したので、残りのサイズ7に配列で同じことを繰り返す
最初にnの数字があった場合、本質的にはn-1回の比較をしたように見える
次にn-2の比較、次にn-3の比較…というように続く
↑「選択ソート」と呼ばれるコード
コンピュータに何度も最小の要素を選択させることで、ソートを実現する方法
いったん見つかった最小の要素はその都度取り除けるので、比較対象＝作業量はどんどん少なくなっていく
▼選択ソートの擬似コード
For i from 0 to n-1
Find smallest item between i'th item and last item
Swap smallest item with i'th item ※swap with ～と～を交換する
i番目の要素と最後までのすべての要素を比較して最小を見つける
最小の要素とi番目の要素を交換する
実行時間はどう表現できる？
n + (n-1) + (n-2) + (n-3)… + 1
⇒n(n + 1)/2
⇒展開していくと⇒ (n2 + n) / 2 ⇒ n2 / 2 + n / 2
数学的に支配的になるのはn2
O(n2) ←実行時間のリストでワースト1
⇒もっと上手くやれるはず
二つの数字を比較するという別のアイデア
「バブルソート」と呼ばれるアルゴリズムを見ることを提案したい
もう一度、8つの数字をソートされていない状態に戻してみる←数字のペアだけに焦点を絞れば、少ない数字の集まりがたくさんあるように感じる
前はすべての数字をバラバラに捉え、大きな問題を解決しようとした
⇒隣接する数字のペアだけに注目したらどうか？
少し手を加えてアルゴリズムを根本的に変えることが出来るかもしれない
例えば6 3 8 5 2 7 4 1 の左端のペア
6と3
小さな数字は左に、大きな数字は右にあるべき、というルールに従って入れ替え
6 3 8 5 2 7 4 1 ⇒ 3 6 8 5 2 7 4 1
次に6と8 ⇒問題ない
次に8と5 ⇒8は右、5は左に
3 6 5 8 2 7 4 1
次に8と2 ⇒8は右、2は左に
3 6 5 2 8 7 4 1
次に8と7 ⇒8は右、7は左に
3 6 5 2 7 8 4 1
次に8と4 ⇒8は右、4は左に
3 6 5 2 7 4 8 1
次に8と1 ⇒8は右、1は左に
3 6 5 2 7 4 1 8
↑最も大きい数字の8が右端のあるべき位置に配置された
最も小さい数字の1はあるべき位置に一歩近づいた
繰り返すごとに、一番大きい数字が右端に集まっていく
「バブルソート」の名前の由来⇒最大の数字がリストの一番上、あるいは最後、あるいは右端に向かって泡のように押し寄せてくるという事実を暗示している
たどり着く答えは同じだが、根本的に異なるアルゴリズムで達成した
最初の「選択ソート」では最小の数字を探して左端と入れ替えることを何度も繰り返した
次は、本質的に「ソートされていない」ということがどういうことか？をしっかり考えた⇒「順番になっていない」という非常に基本的な事実は、その方法で問題を解決する機会を示唆している
小さな断片的な問題をすべて解決すれば良い⇒ペアで比較していく「バブルソート」
繰り返し適用すると、ループを使って大きな問題が無くなるまで小さな問題をすべて修正することで最終的に利益を得ることが出来る
バブルソートの実行時間は？
最初はn-1回の比較⇒n-2、n-3、n-4…最後は2つまたは1つだけが残るまで比較し、その時点で終了
ところで、選択ソートの実行時間の下限は？
線形探索や二分探索ではたまたま最初のドアでクリアになることも考えられた
選択ソートでは単純に数字を検索するたびに左から始めて右にずっと行くことを繰り返した←実際、最初から数字が完璧にソートされていたとしても同じくらいの時間を無駄にしてしまう
アルゴリズムを評価するとき、しばしば最良のケースと最悪のケースを考えた方が良い事がある
ソートの最良のケースは、最初からソートされた状態で、ソートの必要が無いケース
最悪のケースは、リストが完全に逆になっていて、やるべきことが膨大になってしまうケース
選択ソートではすべての数字と最小の数字を比較する必要があるので、完全にソートされた状態でもすべての数字を確認しなければならない
⇒1が左端で最小だと確認した後も、2が最小である確認、3が最小である確認…が必要になる
選択ソートには「最初からソートされていたら途中で辞めよう」というインテリジェンスは無い⇒始めてしまったら短絡的に中止する機会が無い
バブルソートは？
▼バブルソートの擬似コード
Repeat until sorted
For i from 0 to n-2
If i'th and i+1'th elements out of order
Swap them
0からn-1は最初の要素から最後の要素までを表す(1からnと同じだから)
つまり、0からn-2は最初の要素から最後から2番目の要素までを表す
←iとi+1を比較するから終点をn-2にしないとはみ出してしまう
↑配列を扱う上では注意すべき、かなり重要なところ。しばしば配列の境界を越えてしまったり、確保していないにも関わらず配列の先にあるメモリに触れてしまったりしてしまう
最良のケース、最初からソートされた状態の場合、バブルソートはどうなる？
バブルソートの思考プロセスは、ペアを1つずつ見て、その特定のペアに交換が必要かどうかを確認すること
左端から右端へとペアを確認して行って、最終的に交換の必要が無いことがわかった
最初のパスで何の作業もせず、何の交換もしなかったのであれば、以降のパスを実行することでさえ、文字通り自分の時間を無駄にしてしまうことになる
⇒このコードには「ソートされるまで繰り返す」という条件がある
「右端まで確認したにも関わらず一度も交換しなかった」＝ソートされているという事実を確認している
C言語では下のように言い換えられる
Repeat n-1 times
For i from 0 to n-2
If i'th and i+1'th elements out of order
Swap them
If no Swaps
Quit
なぜならn個の要素のうち、左から右に向かって合計n-1個のペアを見ることができるから
1回のパスで何回交換したか？をcounterなどの変数で記録していれば、このアルゴリズムを早期に終了することができ、時間を節約することができる
バブルソートの実行時間の上限は？
擬似コードでは何かをn-1回行い、その中で何かをn-1回行っていることに気づく
forの外でn-1回繰り返し、forの中でn-1回繰り返す⇒(n-1)×(n-1)
展開すると、n2-2n+1
バブルソートの実行時間上限はO(n2)←選択ソートと同じ
上限は同じだとしても、下限は？
少なくとも1回はすべてのペアを見なければならない⇒Ω(n)
それでも、選択ソートの下限Ω(n2)よりはマシ
しかしながら、やはりO(n2)はまだまだ厳しく、実用的ではない
正直に言って、選択ソートもバブルソートも大きなデータセットには使えない(少なくとも時間に相当な余裕が無い時には)
最後にさらに優れたアルゴリズムを紹介する
「再帰」
C言語を始め、ほとんどのプログラミング言語で使える技術
再帰とは、簡単に言えば「関数が自分自身を呼び出す機能」のこと
関数が他の関数を呼ぶことは良くあった
mainがprintfを、mainがstrcmpを…など
関数を実装して、関数が自分自身を呼び出すようにすることはできる
直感的に永遠に終わらない何かを呼び出しそうで、嫌な感じがする…
実際に再帰は危険で失敗しやすい方法だが、非常に強力な技術⇒問題に対する潜在的な解決策を非常に興味深く、エレガントな方法で考えることができる
week0の擬似コード
1 Pick up phone book
2 Open to middle of phone book
3 Look at page
4 If person is on page
5 call person
6 Else if person is earlier in book
7 Open to middle of left half of book
8 Go back to line 3
9 Else if person is later in book
10 Open to middle of right half of book
11 Go back to line 3
12 Else
13 Quit
↑「Go back to line 3」という行は何かを繰り返し行うプログラミングの仕組み
純粋に反復的なもので、文字通り「この行に戻れ」、「この行に戻れ」と言っている
これによって再帰という技術を使う機会を逃している
上の7と8、10と11行を変えて、
「本の左半分の真ん中を開いてから3行目に戻る」とか、「本の右半分の真ん中を開いてから3行目に戻る」ではなく、
「本の左半分を検索」、「本の右半分を検索」とエレガントに言ってみる
1 Pick up phone book
2 Open to middle of phone book
3 Look at page
4 If person is on page
5 call person
6 Else if person is earlier in book
7 Search left half of book
8 Else if person is later in book
9 Search right half of book
10 Else
11 Quit
↑の表現で、前と全く同じアルゴリズムを実装するのに十分な情報が得られる
それ自体はループを使っているわけではなく、人間やコンピュータが何度も何度も何かをするように仕向けている
forループやwhileループ、do whileループ、repeatブロックやforeverブロックの代わりに再帰を使って何度も物事を行うことができる
この11行の擬似コードは「検索」のコード
7行目と9行目で文字通り「本の左半分を検索」と「本の右半分を検索」と言っているが、これは擬似コードの形でもすでに再帰の例になっている
ここには11行のコードで電話帳を検索するアルゴリズムや関数がある
関数が同じ入力で自分自身を呼び出すというのは馬鹿げているし、正しくないし、完全に逆効果
←同じ関数、あるいは同等のアルゴリズムを使いながら入力をどんどん小さくしていく場合、関数が自分自身を呼び出していても、少なくとも1行のコードで「ドアがなくなったら(＝電話帳のページがなくなったら)、やめてください」という非常に知的な記述があれば、おそらく問題ない
いわゆるベースケース(再帰呼び出しを行わずに完了する処理)が必要
つまり、「ちょっと待って、これ以上解決すべき問題は無いから、もうやめよう」と気付くようなコードが必要
実際にコードにどのように実装する？
▼マリオのブロック
高さ4のブロック
↑再帰的な構造＝それ自体をもとに定義されているようなもの
高さ4←高さ3のブロックに1段加える
■
■■
■■■
■■■■
高さ3←高さ2のブロックに1段加える
■
■■
■■■
高さ2←高さ1のブロックに1段加える
■
■■
高さ1←ただブロックを1つ置く
■
ベースケース、ここではある種、明白なことを述べて、ただ一度だけ何かをする
このアルゴリズムの魅力は「もう少しやって、レイヤを作って、もう少しやって、レイヤを作って…」という作業が常に行われていたこと
このような間抜けな例を紹介したのは、再帰の概念が基本的なプログラミング技術であり、それを活用することで根本的に異なる方法で問題を解決できるから
▼マージソート
数字の左半分をソートし、数字の右半分をソートし、ソートした半分をマージ(融合、合併)する
Sort left half of numbers
Sort right half of numbers
Merge sorted halves
ソートのコードなのに、その中にソートが含まれている
英語の文法では許されないが、コードでは、ちょっと違うことをする特別なステップがあって、問題がどんどん小さくなっていく限りはOK
問題を半分に分割して、それぞれを解いている
ベースケースが必要↓
If only one number
Quit
Else
Sort left half of numbers
Sort right half of numbers
Merge sorted halves
ブライアンがデモンストレーション
サイズ4の配列が2つ
左：3 5 6 8
右：1 2 4 7
↑それぞれソートされている
これをマージするとは？
左半分が小さいものから大きいものへ、右半分が同じく小さいものから大きいものへとソートされている場合、それらを統合して、同じ数字を小さいものから大きいものへと並べた新しいリストを作成したい
ここでは、結合された配列の最小の数は、左半分の最小の数か、右半分の最小の数のどちらかになる、ということから始めることができる
左の最小値：3
右の最小値：1
↑どちらかが結合された配列全体の最小値になる
1を結合された配列の先頭に配置する
左：3 5 6 8
右： 2 4 7
合：1
このプロセスを繰り返す
左の最小値：3
右の最小値：2
左：3 5 6 8
右： 4 7
合：1 2
左の最小値：3
右の最小値：4
左： 5 6 8
右： 4 7
合：1 2 3
…
左：
右：
合：1 2 3 4 5 6 7 8
…
元々ソートされた2つの配列を統合して、すべての数字をソート順に並べた1つの完全な配列を作ることができた
私たちは言葉と物理的な方法でヘルパー関数を定義している。言ってみれば独自のカスタム関数。
ブライアンは2つの配列をマージするとはどういうことか？を定義した
実際のC言語のコードで小さなタスクを実行する関数を定義したように、マージという概念を言語的、物理的に定義した
ここで気になるのは「数字の左半分をソート」と「数字の右半分をソート」がすでに実装されていること
If only one number
Quit
Else
Sort left half of numbers
Sort right half of numbers
Merge sorted halves
マージソートは今まで出てきたアルゴリズムの中でも理解しにくい
他のアルゴリズムは一瞬、一日、一週間で理解できたとしても、マージソートは魔法のように動作するので、ちょっと理解するのが難しいアルゴリズム
実際にはより知的に動作するだけ
活用することに慣れれば、より効率的に問題を解決できるようになるでしょう
今度はサイズ8の配列
6 3 8 5 2 7 4 1
マージソートでソートする
まず左半分をソート
6 3 8 5
ソートってどうすればいいかわからない…←マージソートすれば良い！
左半分のサイズ4の配列の左半分サイズ2をソート
6 3
人間の直感では答えはわかるが、コンピュータはまだわからない
↑マージソートすれば良い！
このサイズ2の配列の左半分をソート
6
ここで最初の
If only one number
Quit
↑が効果を発揮。ブライアンは作業をやめる
次にサイズ2の配列の右半分をソート
3
また
If only one number
Quit
↑が効果を発揮。ブライアンは作業をやめる
何の役にも立っていないようだが、ここで6と3というサイズ1の2つの配列ができた
⇒魔法のように
Merge sorted halves
↑が生きる
6と3をマージ⇒3 6 にソートされた！
やっていたことを巻き戻してみると、今はサイズ8の配列の左半分のさらに左半分をソートしていた⇒次に左半分の右半分を同じようにソートする
8 5 2 7 4 1
3 6
↓8と5をマージ
3 6 5 8
マージソートの実行時間の上限はO(n log n)
下限はΩ(n log n)
マージソートは2つ以上の配列を用意する必要があるため、メモリを2倍使う
選択ソートやバブルソートの方が有利な場面もある⇒トレードオフ
Θ 実行時間の上限と下限が同じ場合に使える記号
最後に選択ソート、マージソート、バブルソートでデモンストレーション
⇒マージソートが圧倒的に速い
選択ソートとバブルソートは同じくらい遅い
この記事が気に入ったらサポートをしてみませんか？