CS50 2020 Week5 Data Structures　ハーバード大学　コンピュータサイエンス講座

たぬき

CS50 2020 Week5 Data Structures

久しぶりの投稿。
ホントの受講者しかできないと思ってたProblem Set(課題)をネットで見てできることを知って、それをweek1からずっとやってたので、期間が開いてしまいました。
Problem Setの方はブライアンが仕切っているので、デイヴィッド先生と会うのが久しぶりな感じ。
しかし、いよいよ今回で長かったCともお別れか…感慨深い…が、イマイチまだよくわかった気がしない…まだまだ奥は深いんだろうなあ…
しかし、今回最後だってのに、一回もコード実行しなかったな…

先週week4では、ポインタを紹介し、コンピュータのメモリを操作してより低いレベルで物事を行う方法について説明した
今日はこれらの基本的な要素を使って、コンピュータのメモリにデータ構造と呼ばれるものを作る
コンピュータのメモリ内の様々な場所を参照できるようになると、独自の形状、データ構造と呼ばれるものをつなぎ合わせることができるようになる
Week2で初めてデータ構造を見たときのことを思い出しながら、データ構造の作成を始めてみましょう
Week2では配列という概念を紹介した
配列とは、メモリ上の連続した領域のことで、そこに整数の束を前後に並べて格納したり、文字の束を前後に並べて格納したりすることができる
絵で表現するとグリッドのようになる

例えば、サイズ3の配列にもう1つ数字を追加したいが、サイズ3の配列を作ることしか考えていなかったとする
C言語の配列の問題点はサイズを簡単に変更できないこと
配列の大きさはあらかじめ決めておかなければならない→後で気が変わったり、プログラムの実行時間が長くなってもっと多くの値を格納しなければならなくなったりすると、困ったことになる
1、2、3という配列に4を追加したいとすると、理想的には配列の最後に4を配置する
しかし、配列の問題点は、そのメモリの塊が空の状態では存在しないこと
コンピュータのメモリ全体を拡大して見てみると、それぞれのバイトは他の変数やプログラムの他の部分によって使用されている可能性がある
1、2、3のすぐ隣には「hello,world」という文字列があるかもしれない…
しかし同時に「ゴミのような値」(中身がわからないもの)で埋め尽くされた使用可能なメモリも存在する
問題は、追加したい値を正しい位置に置くためのスペースが無いということ
1、2、3のすぐ隣に「hello,world」があったら、「h」を犠牲にすることなく「4」を置くことはできない
どうすればいい？
サンティアゴ
「元の配列の要素をコピーして新しい配列(よりサイズの大きいもの)を作ればいいのでは？」
↑その通り。使用可能なスペースのどこでも良いから新たにスペースを確保すれば良い
この場合は新たにサイズ4のスペースを確保→元の配列から1、2、3をコピーして、4を追加すれば良い
配列の唯一の定義＝メモリが連続していなければならない
配列ならば、既存のメモリ領域のすぐ後である必要がある

配列を挿入するときの実行時間は？
(配列は検索と関係していると前に説明した)
アンケート→80%の人が配列に挿入するにはO(n)の線形時間が必要であり、実際にはn個のステップが必要であると感じている
↑興味深い結果。過去に配列や検索について話したとき、通常O(log n)を達成することができていた
残念ながらサンティアゴが提案したように、古い配列から新しい配列に全ての要素をコピーしなければならないとしたら元の要素である1、2、3をそれぞれ新しい配列にコピーしなければならないので、配列はn+1のサイズになる＝実行時間はnステップ、O(n)になる
潜在的にすべての要素のコピーを行う必要がある
しかし、配列への挿入の実行時間の下限を考えるとまた違った印象を受けるかもしれない
配列に値を挿入するのに最良のケースでは何ステップかかる？
ブライアン(生徒)
「最良のシナリオは、配列に要素が1つしか無い場合。つまり、配列の中に1つの要素を入れるだけで良い」
↑あなたが配列を持っていて、それがすでに空であることを強調しておきますが、それによって新しい要素のためのスペースがあればそうなる
配列に空きがある限り、Ω(1)、つまり一定の時間があれば良い。また、配列の大きさは関係ない←サイズが4で、値が1つしか入っていない場合もある

配列はランダムアクセスに対応している
＝角括弧[]表記を使えば、いわゆる一定時間内にワンステップで任意の場所にジャンプすることができる
配列が十分な大きさで満杯になっていなければ、配列への挿入の下限は一定時間Ω(1)になる
すでに要素で満たされた配列があって、そこにもう一つ追加したい場合はサンティアゴの言うように値を全てコピーする必要があるため、実行時間の上限はO(n)になる
Javaのベクトルとは、サイズを変更したり、大きくしたり小さくしたりできる配列のようなもの
Cの配列はそうではない。C言語の配列は値が前後に並んだ連続したメモリのブロックで、サイズを決めたらそこで終わり。基本的には自分でサイズを変更しなければならない

このように、配列はこれから紹介するデータ構造の中では最初の、最もシンプルなもの
しかし、コンピュータのメモリにアクセスできるようになった今できることに比べれば、それほど大したことではない
今日はポインタを活用する
ポインタとは、メモリ上の場所を参照するためのアドレス
より洗練されたデータ構造をつなぎ合わせていく
まず、ある意味で1次元の、次に、ある意味で2次元のデータ構造を、非常に基本的な構成要素を使って作る

先週までの3つの構文を思い出して欲しい
struct　メモリ上に独自の構造体を定義することができる仕組み
.(ドット)　structの中に入って、構造体の中の特定の変数(nameやnumber)を取得する演算子
*(星)　間接参照演算子＝「この特定のアドレスに行く」という意味
この3つの要素を使うだけで、配列よりもさらに洗練された独自のデータ構造を構築することができ、最終的にはより効率的に問題を解決できるようになる
実際、C言語のプログラミングでは、ドットとスターの2つの演算子を組み合わせて、意図的に矢印のように見せる手法がよく使われている
->　この使い方についてはもう少し後に説明する

今日学ぶことは構文的には過去のビルディングブロックのようなものだが、このビルディングブロックを新しい方法で使って、これまでとは違った方法で問題を解決していく

まず連結リスト(linked lists)と呼ばれるものを使ってみましょう
例えば連結リストは配列の問題点を解決するデータ構造になる
配列に挿入するのにO(n)ステップが必要だとしたら、率直に言ってちょっと面倒だし、コストもかかる
GoogleやTwitterのように、大量のデータを扱う非常に大きなプログラムを書いている場合、効率的な検索のために全てのデータを大きな配列に格納することも考えられる
二分探索のようなものを使って全てをソートしておく場合、O(log n)という値になった

しかし、配列に別のツイートを追加したり、別のウェブページを追加したりしたいと思うたびにかなりの苦痛を伴うことになる
サンティアゴの言うように、ツイートやウェブページを追加するために元の小さな配列の内容を全て新しい大きな配列にコピーしなければならない可能性がある
連結リストはよりダイナミックなデータ構造
元のデータをすべて触って古い場所から新しい場所に移動させることなく、データ構造を大きくしたり小さくしたりすることができる
一体何をする？
メモリの図で考えてみる
1という値がコンピュータのメモリのアドレス0x123にあるとする
2という値が0x456にあるとする
3という値が0x789にあるとする
↑このように意図的に数字をコンピュータのメモリに分散させていることに注目してほしい
というのも、先ほどの配列の問題は、プログラムの他の部分によるhello,worldなどの値が邪魔になる可能性があるから
そこで提案したいのは、もし1、2、3を保存したいのであれば、好きな場所に置いて、既存の値がある場所を気にする必要は無い(バラバラに置いて良い)、ということ
＝単純にスペースがあるところに値を置いていけば良い
問題は、1、2、3といった値をコンピュータのメモリ上の好きな場所に置くようになると、それらの値を簡単に見つけることができなくなってしまうこと
1がどこにあるかわかったとしても、(配列で行っていたように)次の値を探すために単純に1つ右を見たり、2を足してその次の値を探したりするだけでは、もはや十分ではない
配列ではすべて順番に前後に並んでいた
コンピュータのメモリを、好きな場所に数字を書く事ができるキャンバスのように考えることにすると、コンピュータのメモリに散らばっている他のものとは関係なく、1つ、2つ、3つ…となんとかたどり着くことができれば、それで良い、ということになる
そこで、コンピュータからもう少し容量を奪うことでこれを実現してみましょう
1、2、3の下にもう1スペース確保する
1、2、3を格納するだけのメモリではなく、2倍の情報を格納してみる
気にしている数字(1、2、3)に加えて、いわば少しのメタデータを保存してみましょう
その値自体を気にはしていないが、実際のデータを追跡するのに役立つ値
1つ目(1の下)「0x456」(2が入っているメモリのアドレス)
2つ目(2の下)「0x789」(3が入っているメモリのアドレス)
3つ目(3の下)「0x0」(すべてが0のビットということ)
↑何のためにこんなことをする？
ソフィア
「1つ目の要素が2つ目の要素とどのように関連しているのか、あるいは1つ目と2つ目の間がどのようにリンクしているのかを知るため」
↑その通り。
それぞれのデータを保存するのに実質的に2倍の容量を使って2つ目のスペースを確保
→2つ目のスペースには、これからリストと呼ぶものの中の次の要素へのポインタを格納している
ヘンゼルとグレーテルが残したようなパンくず(毛糸？)→次の要素へのヒント・道筋を示す
最後の0x0は全てのビットが0であることを示す＝NULLと呼んでいるものと数値的に等価
NULLは、メモリに何か問題が発生したことや、スペースが足りないことを示す特別な記号
↑「アドレスがない」ということ
0x0、つまりNULLを使うと、そこには有用なアドレスがないことを示すことができる
これらを抽象化して、何らかの形でリンクしている数字のリストとして考えてみる
このリンクは0x123のような低レベルの数字であるアドレスやポインタによって実装されている
図式的には、連結リストと呼ばれるデータ構造は、ポインタを介して接続された、いわば「NODE」と呼ばれるノードの集合体であると考えれば十分
ノードとはコンピュータサイエンスの一般的な用語で、気になるものを格納する、ある種の構造を指す
ここで我々が気にしているのは、数字と他の構造体へのポインタ
つまり、これは連結リストで、これらの長方形(2つ分のメモリ)はそれぞれノードを表している
コードでは、最終的にC言語の構造体と呼ばれるものを使ってノードを実装する

質問コーナー
「アドレスを格納するためにこれらのセルを全て使用するのはメモリの無駄ではないか？」
↑良い質問。まさにそれが我々が支払わなければならない代償
これからもコンピュータサイエンス、特にプログラミングの問題を解決するときには、このように必ず何らかの代償を支払うことになる
何らかのコストがかかり、実際には何らかのトレードオフが発生する
さっきのように、配列への挿入がO(n)であることが受け入れられなかったとしたら、それは古い配列から新しい配列に全ての値をコピーするのに、非常に多くのステップが必要になるからだが、もしそれがパフォーマンス上の理由やあなたが解決しようとしている問題のために受け入れられないのであれば、それは構わない
この問題を解決することで、既存の数値をどこかに移動させることなく、メモリ上の任意の場所に数値を置くことができるようになり、時間を節約することができるが、その代償としてスペースが増えてしまう
つまり、コンピュータの時間と人間の時間のどちらが大切か、あるいは空間や空間のコスト、つまり文字通りコンピュータのために必要なメモリの量が多いかどうか、ということになる

この問題を実際のコードに置き換えてみる
前回C言語で構造体を見たときには、nameとnumberの2つの要素を持つpersonを定義するためにこのようなことをしていた
typedef struct
{
string name;
string number;
}
person;
↑これを今回のノードに置き換えると…
typedef struct
{
int number;
ポインタ
}
node;

この構造体が別の構造体へのポインタを持っていることを表現するにはどうしたらいい？
ある型へのポインタを表すにはint *やchar *を使っていた…
→node *
文字通り、このポインタの目的はデータ構造内の次のノードを指すこと
↓
typedef struct
{
int number;
node *next;
}
node;
そしてこのポインタは個々のデータ構造の先頭を意味するnumberと呼ばれるintの後に追加されることになる
ここでC言語の問題にぶつかる
C言語はある種の単純な言語で、複雑に見えるかもしれないが、「以前に見たことのないものは何も理解できない」ということを思い出してほしい
今のところ、我々がnodeについて言及したのはこのコードの最後の行が初めてであることに注意
問題はこの構文では、typedefの動作の性質上、コンパイラがコードの最後の行とセミコロンを読み終わるまで、nodeというものは実際には存在しないということ

これには回避策がある↓
typedef struct node　←ここにnodeを持ってくる
{
int number;
struct node *next;　←ここにstructを持ってくる
}
node;

単なるコピペで冗長のように見えるが、これがC言語で一般的に行われていること。
typedef struct nodeは、関数のプロトタイプと同じで、コンパイラに「よし、struct nodeというものが存在するぞ」というヒントを与える

このような構造を定義するだけでなく、連結リストをどのように構築するか、より有用なコードに変換するにはどうすればいいか

ここで、「連結リストは単なるポインタから始まる」と提案する
小道具→NULLポインタである「list」という変数→矢印は床を指している(何も指していない)
1、2、3という3つの数字を持つ連結リストの割り当てを始めたい
今のところ我々のプログラムに存在するのはこのlistという変数のみ
配列は使わない
→mallocを使う
mallocを使うとメモリの大きさを指定するだけで、好きなだけメモリを割り当てることができる
今日最終的にできることは、mallocを使って1つの構造体を動的に割り当て、その中に数字の1を入れ、別の構造体に数字の2を入れ、別の構造体に数字の3を入れること
そして、listの矢印を使って、実際にそれらをつなぎ合わせ、一方が他方を指すようにする
まず1を入れるノードを用意する→numberには1を、ポインタにはNULLを設定
リストのインスタンス化、つまりリストの作成を始めたところで、次のようなことをする
このlistという変数は、このリストがメモリのどこにあるかを追跡するためのもの
listがこのノードを指すことで、ノードの間がつながる
そして、別のノードを確保するときには、この連結リストに挿入したい
配列の世界では新しいメモリの塊を割り当てて、この値を新しい値にコピーする必要があった
連結リストの世界では、2回目にmallocを呼び出して、「ノードが入るのに十分な大きさのメモリの塊をもう一つください」と言うだけで良い
もう一つノードを用意する
listという連結リストに戻って、新しいノードを挿入したい
→矢印の方向に進み、ノードのnextフィールドを次のノードに向ける
これでサイズ2の連結リストができた
見かけ上は3つの変数があるだけ
ノードを指すポインタで、そのノードは他のノードを指している
次に3を入れるノードを用意したい
mallocは強力で、利用可能な場所であればどこからでも、コンピュータのいわゆるヒープ領域からメモリを取得してくる＝定義上、メモリは連続していない可能性がある
次の数字は必ずしもコンピュータのメモリ内の近くにあるとは限らない→近くではなく、ずっと向こうにあるかもしれない。実際にそうなる可能性がある
配列の世界のように連続している必要は無い
その新しいノードへのポインタを保持して、これらすべてのものをつなぎ合わせたいのであれば、一番最初から始めれば良い
list→1→2→3…
この方法の欠点はweek0以降の友人である二分探索を頼れなくなること
二分探索はO(log n)という点で素晴らしいものだった
中身をO(n)より速く見つけることができた
しかし、この方法の利点は、サイズを変更するたびに、メモリの割り当てとコピーを繰り返し、すべての値を変更する必要がないこと＝ダイナミズムがある
GoogleやTwitterのような大量のデータを扱う際に、サンティアゴが提案したような配列の挿入に頼らなければならないとしたらパフォーマンス的には致命的
→連結リストのようなダイナミックなデータ構造を使用して、利用可能なスペースを割り当て、この物理的なポインタのように、それらをつなぎ合わせることでどこにあるかを思い出すことができるというのは、ダイナミズムを必要とする場合にはよりダイナミックな構造を作り出せるという点で、実に先端的であると言える

質問のコーナー
「連結リストの処理全体の中で実際にmallocを使うのはいつ？また、mallocは何のために使われている？」
↑先生がステージ裏から大きなブロックを手に持ってくるたびに、ノードをmallocするプロセスを演じていた(伝わってなかった)
先週扱ったように、mallocを呼び出すと、メモリの塊の最初のバイトのアドレスが返される→これらの(ステージ上の)ノードはそれぞれ、1回のmallocの呼び出しの戻り値を表している
この質問に答えるには実際のコードに置き換えるのが一番かもしれない

node *list;
これは物語の始まりを表すコードの一行で、最初は何も初期化されていない「list」という変数しかなかった
矢印は何も指していなかった
これはただのメモリで、実際に値を入れる前のゴミのような値が中に入っているということ
このリスト変数はNULLなどに初期化しない限り、デフォルトではゴミのような値を持っている
node *list = NULL;
これは空の連結リストを作成するだけのコードライン
次に我々がしたことはステージ裏からmallocによってノードの大きな箱を持ってきたこと
コードで表すと↓
node *n = malloc(sizeof(node));
これでなんでも好きな変数を呼び出せる
sizeofはC言語の演算子で、データ型のサイズを何バイトにするかを示すもの
MacやPC、CS50 IDEで計算して、これらのノードが何バイトを占めるのかを把握することができる
mallocは1つの引数を取り、動的に割り当てたいバイト数を指定して、そのバイトの最初のアドレスを返す
→それをノードを表すnという変数に割り当てる
これで、まずは数字が入っておらず、矢印がどこを向いているかわからないノードができた
list NULL
n -> number(ゴミ)　next(ゴミ)
C言語では常にポインタを返す関数を呼び出すときは、NULLかNULLでないかをチェックしなければならない
それがNULLだったら有効なアドレスがないということなので、それを触ってはいけない
nがNULLでなければ、それは良いこと＝有効なアドレスだということ
if(n != NULL)
{
(*n).number = 1;
}
*演算子によってその場所に行き、.演算子でそこにある構造体の中に入ってその中の変数(この場合はnumber)に行くという意味
このように、最初はサイズ1のリストがあり、この変数が現時点で唯一のノードを指している場合、このコードを実行すれば1がノードに入る
*nは、そこに埋め込まれているアドレスを基にそこへ行き、数字を代入する
もう一つしなければならないことがある
構造体の次のポインタを表すゴミのような値を、NULLに置き換えたい
NULLは、これがリストの終わりということを示す
ゴミのような値のままではいけない→ゴミのような値は何も指していないわけではなく、あちらにもこちらにも向いている可能性のある任意の数字だから

if(n != NULL)
{
n -> next = NULL;
}
と.をあちこちで使う必要はなく、巧妙なアプローチができる
先ほど1を代入したときに使った、()、.の3つを矢印->表記に置き換えることができる
つまり、「矢印の方向に行く」ということ
(*n).number = 1;
↓
n -> number = 1;
アドレスから始まって、そこに行き、その領域にあるnumberまたはnextをそれぞれ見ていく
以上のステップを経て、このノードを初期化し、その中に数字の1とNULLを入れた
次はどうすれば良い？
この時点でこのコードにはまだ目に見えていない他の変数がある
(実際にステージ上で行ったことをコードに置き換えているから)
つまり、もう一つの変数nがあって、それはステージ上の先生自身を表しているようなもの
先生が一時的な変数nだとすると、先生は「list = n;」という一行のコードを実際に実行して初めて、このノードがコンピュータのメモリのどこにあるかを思い出す
nはメモリ上のものを実際に追跡するために使用できる一時的な変数
ノードを連結リストに追加したい場合、nに次のノードを指し示させてから、nをlistに代入する→nはlistが指し示したら、消える

↓次に実行するコード
node *n = malloc(sizeof(node));　←さっきと同じ構文だが、nには新たなメモリのアドレスが入る
if(n != NULL)
{
n -> number = 2;
n -> next = NULL;
}

この時点で、1が入ったノードはNULLを指しているので2が入ったノードとつながっていない
新しいノードを割り当てて、気になる数字を入れて、そのnextポインタをNULLに初期化したからといって、そのノードがデータ構造の一部になるわけではない
連結リストには古いノードから新しいノードへのポインタがまだ無い
あるべき姿にたどり着くためにはもう1行コードを追加する必要がある
list -> next = n;
リスト変数から初めて、コードの通りに矢印をたどる
そして、nextフィールドを更新して、新しく割り当てられたノードである(最新の)nを指すようにする
これでサイズ2の連結リストが出来上がった

▼連結リストへのノードの追加
①ノードを割り当て、その2つの変数であるnumberとnextを初期化
②連結リスト上の既存のノードと繋げる

↓次に3を入れるノードを追加
node *n = malloc(sizeof(node));
if(n != NULL)
{
n -> number = 3;
n -> next = NULL;
}

list -> next -> next = n;
↑この構文はあまり使わないが、私たちが操作している基本的な構成要素を表している
もし先に進んで2を3にリンクさせたいならlistから出発する
→矢印を辿って進む
→もう一度矢印に沿って進む
→2が入っているノードのnextフィールドをnに設定する
nは直近に割り当てられたノードの現在のアドレス
このように、構文は少し新しくなっているが、我々が使っている2つの矢印は、文字通りポインタをたどって、ポインタをたどって、1つの値を次の値に割り当てることをコードで表現したもの
この時点で、一時的な変数であるnを取り除けばサイズ3の全く新しい連結リストを段階的に構築したことになる
大変な作業のように見えるが、これでリストを動的に成長させることができる

質問のコーナー
「もし3つ以上の要素を持つ長いリストを作ろうとした場合、next -> next ->…と何度も繰り返すのは面倒ではないか？」
↑だからこそ、このような構文は通常書かないと言った。本格的なプログラムで一時的にそれをやってみてデモンストレーションしてみよう
一般的にはループを使って、一時的な変数を使って、これを指して、また繰り返して、また繰り返して…ということをする
ここで断っておくが、ループを適切に使えば、変数を何度も更新するだけで、ただ一本の矢印を書く事になる

連結リストの検索にかかる時間はどれくらい？
→O(n)になる
例えばさっきの連結リストで3という数字を探すには3つの数字全てを見なければならず、O(n)となる
10という数字を探すのなら、最初から初めて、探して、探して、探し続けることになる
配列では一瞬でリストの最後にジャンプできる→中間でも最初でもどこでも一瞬
連結リストは残念ながら、最終的には1つのアドレス、つまり最初のノードの指すアドレスだけで表現される
我々人間から見ればすぐにノードのつながりを直感的に見ることができるが、コンピュータはパンくずを辿って最初から進んでいくしかない

連結リストに挿入するときの実行時間は？
→多くの生徒がO(1)、残りの生徒がO(n)と回答
O(n)と答えた生徒は、挿入する際に最後に追加しなければいけないと仮定している
最後に要素を追加するので、最初から矢印を1つ1つたどっていかなければならず、実行時間がO(n)になる…という仮定
↑実は意図的に先生はそう思うようにステージ上でノードを順番に配置していた
しかし、実は「連結リストはソートされていなければならない」という条件はつけていない
もっと別な方法で、もう少し効率的に4という数字を割り当てたい場合、そして率直に言って、連結リストがソートされているかどうか気にしない場合は、listから出ている最初の矢印を新しいノードにつないでも良い←新しいノードをリストの先頭に挿入できる
つまり、リストの最後に挿入するのではなく、常にリストの先頭に割り込ませる形で挿入すれば実行時間はO(1)になる
(厳密にはmallocでメモリを確保してnumberとnextを初期化するのでステップは3か4だが、それは要素の多さに左右されないのでO(1)とみなすことができる)
つまり、このリストに関しては、ソートされた順序を犠牲にすることができれば、O(1)で挿入することができる→リストは長くなっていくが、最後ではなく最初から長くなっていく
あくまでトレードオフの問題。もしソート順にこだわらず、アルゴリズムやコードでソートを必要としないのであれば、それを回避して、一定時間での挿入を実現することができる
GoogleやTwitterのような巨大なプログラムの場合、その方法は大変な節約になる

CS50 IDEで実際に数字を扱ったり、メモリ上のものを操作したりするプログラムをいくつか書いてみよう

▼list.c
まずは配列でリストを作ってみる

#include <stdio.h>

int main(void)
{
//サイズ3の整数のリストを作る
int list[3];

//このサイズ3の配列に新しい値をハードコーディングしていく
list[0] = 1;
list[1] = 2;
list[2] = 3;

for(int i = 0; i < 3; i++)
{
    printf("%i\n",list[i]);
}

}

今度はもっとダイナミックなものに移行してみる
配列の作成を事前に行う必要はなく、動的に割り当てられたメモリの塊を使って行うことができる

▼list2.c
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
//int3個分のメモリを確保する
//mallocを使って配列を取得する方法
int *list = malloc(3 * sizeof(int));

//listがNULLかどうかチェック
if(list == NULL)
{
    return 1;
}

//mallocによって取得したメモリは配列と等価性があり、
//配列同様に[]で操作することが可能
list[0] = 1;    //*list = 1;と同じ
list[1] = 2;    //*(list+1) = 2;と同じ
list[2] = 3;    //*(list+2) = 3;と同じ

//この時点で、「あ、4つ目の整数も作らなきゃいけないんだった」と気付く
//前に戻らずに動的に新たなメモリを割り当てる
int *tmp = malloc(4 * sizeof(int));

if(tmp == NULL)
{
    free(list);
    return 1;
}

//サンティアゴの方法で配列に新たな要素を追加するために古い要素を全てコピーする
for(int i = 0;i < 3; i++)
{
    tmp[i] = list[i];
}

tmp[3] = 4;

//古いリストを解放
free(list);

//一時的なリストtmpを元のlistとして扱う
list = tmp;

for(int i = 0;i < 4;i++)
{
    printf("%i\n",list[i]);
}

free(list);

}

ここでは意図的に2回ともmallocを使っているが、C言語では[]表記で配列を作成すると窮地に追い込まれる
これまで見てきたようなコードは使えないし、[]表記を使って宣言した配列のサイズを変更するようなことはできない
より技術的に言えば、[]表記を使うとスタック上に配列を静的に確保していることになる
mallocを使ってメモリを取得した場合、それはヒープから来ており、それはサイズを変更したり、メモリを返したり、もっと多くのメモリを取得することもできる

実際にはもっと簡単な方法がある
配列やメモリの塊のサイズを変更して再割り当てをする場合、このような作業を全て行う必要は無い
reallocという、このようなケースで実際に役立つ新しい関数を使うことができる
これによってintのサイズの4倍のメモリの塊を再割り当てすることができる
int *tmp = realloc(list, 4 * sizeof(int));
↑2つの引数
①すでに割り当てたメモリの塊のアドレス
②再割り当てしたいメモリのサイズ
reallocを使えば、「古いリストに入っていたものを新しいリストにコピーする」ところまでやってくれる
既存のメモリの塊の最後にたまたま空きがあった場合、先ほどのスライドで見た「hello,world」の場合と違って、実際には全く同じアドレスが返される

質問のコーナー
「なぜプログラムの最後にtmpを解放する必要が無いのか？」
↑代入によってlistに変数名を変更したから。listを解放すればOK

「配列やrealloc、mallocを使えばこのようなことができるのに、なぜ連結リストを使う必要があるのか？」
↑今やったことは全て今回の講義の始まりへの後戻りに過ぎない。
今書いたコードのどのバージョンでも、我々はこの配列のためにより多くのスペースを再割り当てした
つまり、手動でforループを使って、あるいはrealloc自身がforループを使って、古い値を全て新しい値にコピーしなければならなかった
↑これらのアプローチの実行時間は全てO(n)だった
挿入に関しては、連結リストのように重複せずに追加するというダイナミズムはなかった
また、構造体の先頭への挿入をO(1)で行えるような機能もなかった
最終的な目標は、このコードを変更してダイナミズムを与え、単なる整数の配列ではなく、適切な連結リストとして実際に実装すること

5分間の休憩

今日は配列の再検討から始めて、配列をソートしておけば検索が上手くいくことを指摘したことを思い出して欲しい→week0の時に気に入ったO(log n)が得られる
しかし、配列を動的に変更しようとすると、すぐに非常に高コストになってしまう
正直なところ、データ量の多い実世界のソフトウェアではO(n)は非常に高くつく
そこで、ポインタを使って連結リストと呼ばれる構造体をつなぎ合わせることで、メモリの使用量は増えるが、そのコストを回避することができる
メモリの増加とコストの増加の対価として、ダイナミズムが得られる
先ほど書いたようなコードであれば違いがわからないほどだが、現実のソフトウェアでは大きな違いとなって現れる
連結リストに動的に追加するコードは、実は今週のpset5の課題の一部
しかし、事前に必要なノード数がわかっている場合に、ノードを割り当ててつなぎ合わせる作業を構文的に始めるためのビルディングブロックをいくつか見てみよう

▼list3.c
連結リスト
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int number;
struct node *next;
}
node;

int main(void)
{
//ポインタを宣言する際には必ずNULLなどに初期化
//宣言しただけだとゴミのような値が入っているため、セグメンテーションフォールトにつながる
node *list = NULL;

//このsizeof演算子は、mainの上にある構造体の定義から、整数とstruct nodeへのポインタを格納するのに必要なスペースを算出している
node *n = malloc(sizeof(node));

if(n == NULL)
{
    return 1;
}

//先ほどステージ上で先生がやったことをコードにする
//まずは最初のノードに1を入れて、listに連結する
n -> number =1;
n -> next = NULL;

list = n;

//次に2を入れるノードを作る
n = malloc(sizeof(node));

if(n == NULL)
{
    free(list);
    return 1;
}

n -> number = 2;
n -> next =NULL;

//listの1番目のノードのnextポインタを更新して、代わりに新しいノードのアドレスnを格納する
list -> next =n;

//最後の
n = malloc(sizeof(node));
if(n == NULL)
{
    free(list ->next);
    free(list);
    return 1;
}

n -> number =3;
n -> next =NULL;

list ->next->next =n;

//forループでprintfしたいが、配列はここでは使えない…→ポインタを使う
//tmpというノードへの一時的なポインタを与え、それをリストの先頭にあるものに初期化する
//tmpがNULLにならない限り、tmpをtmp->nextに更新し続ける
//これによってリストの一番最初のノードを指して、次のフィールドに更新し、次のフィールドに更新し…続けることができる
for(node *tmp = list; tmp != NULL; tmp = tmp->next)
{
    printf("%i\n",tmp->number);
}

//連結リストの解放
//listがNULLを指さない限り、左から右へと割り当てられたメモリを解放していく
//ノードには次のノードへのポインタが含まれているため、いきなり開放してしまうと次への道を見失ってしまう
//tmpに次のノードへのポインタを格納することで、「左手で現在のノードを指し示しつつ、右手で次のノードを指し示す」ようなことができる
//free(list)で解放されるのは左手で指し示している現在のノードのみ
while(list != NULL)
{
    node *tmp = list->next;
    free(list);
    list = tmp;
}

}

質問のコーナー
「前にやったように、なぜノードのサイズの3倍のmallocを使って3つのノードを取得しなかったのか？」
↑実は一度に3つのノードのためにmallocでメモリを取得することも可能
慎重に1つずつ取得していった
3つを一度に取得した場合は、ポインタ演算を使うか、[]記法を使って、大きなメモリの塊を基本的にノードの配列として扱い、それをつなぎ合わせる必要がある
デモのために構文を示す小さくて簡単な例を用意したが、現実のシステムでは1、2、3の順に挿入することは無いと仮定している→大抵の場合、1を挿入した後、2を挿入するまでにはしばらく時間が経つ
現実の世界では「1のためにメモリを取得する時」と「2のためにメモリを取得する時」の間には隔たりがある

「なぜmallocがメモリの取得に失敗する時があるの？」
↑ほぼ失敗しないが、コンピュータのメモリが不足している時は失敗する
PCがフリーズしたり再起動してしまうのは大抵これが原因。

より補強するために、連結リストを使った簡単な例を見てみよう
ここでもリストは左から右への1次元構造とする
そして、2つ目の次元を追加して、それが何をもたらすのかを見てみよう

ここでは数字を変えてみる→最初の数字を2とする
2は更にmallocされている他のメモリの塊を指している
list→2→4→5
今回はわざと2、4、5と数字の感覚を広げてみた

さらにこのリストに挿入したいと考えた場合、
ソートされた順序で、ノードを最後でも最初でもなく、真ん中に追加するには少し違った考え方をしなければならないことがわかったから。
例えば真ん中にノードを増やしたい場合は、実際に行わなければならない作業が少し増えてしまう
例えば数字の1を追加したいとする

node *n = malloc(sizeof(node));
if(n != NULL)
{
n -> number = 1;
n -> next = NULL;
}
↑先ほどと同じコード。この時点では1が入ったnというノードは空間に浮かんでいるようなもので、リストに挿入されていない状態。
一時的な変数nは数字の1を割り当てるときに指し示しているだけ
先に進んで、これをリストに連結したい
直感的に1が2より前にあったら、(ステージ上で)listから2への接続を外して1に接続し直せば良い
↑ここまで他に何もしなければ、2、4、5という3つのノードを迷子にしてしまったことになる←残りのノードがどこにあるかわからなくなってしまう
もしコードに別の変数がなければ、あるいはリストの元々の始まりを片手で示していなければ、文字通りリストの残りの部分を孤児にしてしまったことになる
先週に引き続き、技術的には大規模なメモリリークが発生する
例えば、コンピュータを再起動するか、プログラムが終了してOSが事態を収集するまで、文字通り二度と元に戻すことができない、3つのノードのサイズのメモリをリークしたことになる
↑このような状況は避けたい
操作の順序は実際に重要
最初に数字の1を挿入したとき、「そうか、1はリストの最初から始まっているんだ」と認識すべき
元々list→2となっているなら、
まずは1を入れた一時的なノードnの矢印(next)をlistと同じく2に接続する
新しいノードnとlistがこのノード(2が入ったノード)を指している状態なので、今度はちょっとした切り替えができる→この状態ならlistの接続を外しても大丈夫
listから2が入っているノードへの接続を外して、n(1が入っているノード)に接続し直す
↑これを図式化すると、以前のように「list = n;」と言って、「これがnで、これがlistで…」とこの矢印を最初に調整してしまうと悪いことが起こる←残りの2、4、5が入ったノードを孤児にしてメモリリークを起こしてしまう

正しいコードを見てみよう
n -> next = list;
正しいコードは、nから始めて、そのnextフィールド、この矢印を更新して、リストが元々指していたものと同じものを指すようにする
そして先に進み、両方が現在重複して2が入っているノードを指しているようなリストに更新する
list →2→4→5
　↑
n

list = n;
listが新しいノードnを指すように更新する
list→1→2→4→5

先ほどとは順序が変わり、以前は最後にlistに追加していたが、今回は最初に追加することを提案した
では最後の例として3を割り当てたい場合を考えてみよう
list→1→2→4→5
まずはもう一つのノード、数字の3をmallocする
(ステージ上で)3の入ったノードを用意し、2と4のノードの間に置く
先ほどと同じく、いきなり2から4への接続を外して3に接続し直すようなことは避けたい
なぜなら2以降の残りの4と5という二つのノードを孤児にしてしまうから
連結リストの真ん中にいるとき、真ん中に挿入するために書くコードでは、ソートされた順番に挿入することを気にしているなら、最初にこれ(新たに3を入れたノードn)を更新するべき
3が入ったノードnの矢印を4に接続
list→1→2→4→5
　 　 　↑
　 　 　3

↑これで新たなノードnとすでに元々あったノード2から4への接続が同時にある状態になった
これで、元々の2から4への接続を外して、最後の矢印を更新して、正しい位置にある新しいノードを指す(2→3)ようにしても大丈夫
list→1→2→3→4→5
我々はこれで連結リストを後にしようとしている
なぜなら多くの人が指摘したように、連結リストは良いものだが素晴らしいものではない
動的であるという点では優れているし、ソート順を気にせず本当に必要であれば先頭に挿入するなどして追加することができる
しかし、ソートされたままの状態で、途中や最後に挿入するとなると、以上に述べたようにそれなりの作業が必要になってしまう
というのも、これらの矢印をすべて操作し続けるとなると、結局O(n)のようになってしまうから
このように、ダイナミズムが得られるとしても、必ずしもパフォーマンスが向上するというわけではない
しかし、根本的に全く新しい世界が開けたのは確か
我々はポインタを糸のように使って、メモリ上のデータ構造をつなぎ合わせることができるようになった＝メモリをキャンバスのように使い、好きな値を描くことができる
そして、値がどこにあるかを記憶することができる
しかしこれは非常にシンプルで、左から右への一次元
もし自分自身に2つ目の次元を与えたらどうなるだろう？
左から右だけでなく、右から左、上から下…というように考え始めたらどうなるか？
↑これはコンピュータにとっては無意味なこと。コンピュータはメモリをバイト0、1、2、3…と考えているにすぎない
しかし私たち人間は、これらのデータ構造をもう少し抽象的に、もっと単純に考えることができる→現実世界ではお馴染みの方法で考えることができる
木、家系図→家長がいて、その下に子孫がぶら下がっているような図
根っこ(ルート)があって、それがどんどん枝分かれして、上から下へと成長していくような木構造のアイデアを活用することができる
木(tree)については連結リストから学んだ教訓を生かすことができる
加えて、配列の特徴を取り戻すこともできる

二分探索ツリー
二分探索ツリーというものについて、次のように定義してみよう
サイズ7の配列があるとする
1234567
4
↓
2 or 6
ソートされていればこの配列に二分探索を適用できることを思い出してほしい
ソートされた配列での二分探索が非常に強力だったのは、この問題を何度も何度も半分にし、電話帳を何度も何度も半分に引き裂くことで、O(log n)になるからだと結論づけた
1234567
4
↓
2 or 6

しかし、二分探索の問題点は、ランダムにアクセスできるように配列を使用する必要がある、ということ
一定時間で配列へのインデックスを作成し、0番目、n-1番目、(n-1)/2番目…のような中間点を求める、といった単純な演算ができなければならない
データ構造上での演算ができなければならな
そして我々は、配列ではなく連結リストのような動的なデータ構造に移行することで、そのランダムアクセスをなくすことを提案したところ
↓
1次元ではなく2次元で考えるようにしたらどうだろう？
つまり配列とは長さだけでなく「高さ」もある2次元の構造だと考えれば良い
1234567
↓
4
2 　6
1 3 5 7
これらの値の間には視覚的な関係が保たれているように見える
これらの値は何を使ってつなぎ合わせることができるだろうか？
↑それはポインタ。ポインタはメモリ上のものをつなぎ合わせるための新しい構成要素。
メモリ上のものが数字でも何でも良い
もう少しメモリを投入して、ノードを使い、整数をノードで包んで、そのノードが数字だけでなくポインタも含むようにすると、家系図のような絵を描けるかもしれない
その家系図には、例えば頂点にルート・ノードがあり、子ノードがある
左の子、右の子…とこの定義は何度も繰り返される
コンピュータ科学者は連結リストのダイナミズムを得るために、このデータ構造を使用している
上の家系図で言うところの1、3、5、7よりも下のマスをどんどん追加していくことで、ツリーにノードを追加していくことができる
そして、ポインタを使ってそれらをつなぎ合わせ、ツリーを垂直に、下へ下へ…と成長させていく
しかし、優秀なコンピュータ科学者なら、これらの数字をランダムにしてはいけないことに気付くだろう。そうしないと本当に時間の無駄になってしまう
何らかのアルゴリズムを使うべき
→このツリーのパターンに気付いた人はいる？
このツリーの7つのノードにはどんなパターンが現れている？
ランダムに並んでいるわけではなく、非常に意図的に左から右へ、上から下へ、ある方法で並べられている
→「上に真ん中の数字を置いている」
1と3の間には2を、5と7の間には6を、2と6の間には4
それは必ずしも真ん中の数字ではなくても良い
これを少し一般化して、いわば「このツリーのどこかのノードを選ぶと、その左の子はその値よりも小さく、右の子はその値よりも大きくなる」とコメントすることができる
そして、それを何度も繰り返すことができる
4の左の子は2で「より小さい」、右の子は6で「より大きい」
2の左の子は1で「より小さい」、右の子は3で「より大きい」
6の左の子は5で「より小さい」、右の子は7で「より大きい」
↑先週も扱ったが、これは再帰的な定義であると言える→再帰的なデータ構造
つまり、自分自身を呼び出すことで再帰的になるのは、アルゴリズムや関数だけではない
データ構造そのものも再帰的になる
上記のツリーは技術的には2つのツリーを持つツリー
4は技術的には2つの子を持っている
2つの子それぞれは、それぞれがより小さなツリーである

再帰的な構造をコードで表現してみよう
ポインタを使うことで必要に応じてツリーにノードを追加できるというダイナミズムがある
さらに、左の子は常に小さく、右の子は常に大きいことから、二分探索、つまり、このデータ構造の正式名称である二分探索ツリーにとって重要な順序を維持している
これでより効率的な検索ができるようになった→どうやって？

例えば3という数字を検索したい場合、どうすればいい？
まずツリーの頂点ルートから始める(連結リストのように、先頭から始める)
3は明らかにルート4より小さい
↑week0で電話帳の半分を破り捨てたように、これで木の半分を切り倒したと考えれば良い。というのも、もし3があったとして、それは絶対に4より右側には存在しないので、左側に集中することができる
左に行くと2がルートのツリーがある。言ってみれば小さなサブ・ツリー。
3はどうやって見つければ良い？
ルート2より大きい方の右を見てみる
→見つけた！
↑それとは対照的に、もし8という数字を探すとしたら…
4から始める→8は4より大きいので右側を見る→6がある
→8は6より大きいので右側を見る→7が終端→8は無い！
ツリーに最初から存在しない数字を探す際にも、毎回ツリーの半分を切り捨てることができている←week0で見たのと同じ効果、同じパフォーマンスを得られている

このアイデアをどのようにコード化すれば良い？
構成要素は全て揃っている
先に提案しておく→連結リストに使っていたノードの代わりに、連結リストはnumberとnextと呼ばれる1つのポインタで構成されていたが、これらは何とでも呼べるものだった
typedef struct node
{
int number;
struct node *next;
}
node;

↓numberだけでなく、「左」、「右」の2個のポインタを加える

typedef struct node
{
int number;
struct node *left;
struct node *right;
}
node;
leftとrightはいずれもstruct nodeへのポインタ。
先ほどと同じ用語だが、ポインタが1つでなく2つになったことで、概念的には左を指してより小さなサブ・ツリーを指すことができるし、右を指せばより大きなサブ・ツリーを指すことができる
では、二分探索のようなものをどうやって実装する？
実際にコードを実装してみよう。ここからが再帰の醍醐味でもある。
マリオのピラミッドを再帰的に作るときには、ちょっと無理をした
ピラミッドはゲームの中の再帰的な物理構造、または仮想構造であると主張した
しかし、データ構造とポインタがあれば、再帰性は本当に輝きを増す

C言語で「ツリーから数字を検索する」という目的の関数を宣言すると、定義上、ツリーのルートから下に向かって検索することになる
bool search(node *tree , int number)
↑boolを返す関数を提案する。真か偽か、その番号がツリーの中にあるかどうか、yesかnoか。
この関数は2つの引数を取る。
1つ目の引数はノードへのポインタ、つまりツリーの事。ルートと呼ぶこともできる。
そして2つ目の引数は、4でも6でも8でも良いが、気になる数字を受け取る。
では、その最初のコードの塊は何になるか？

bool search(node *tree , int number)
{
if(tree == NULL)
{
return false;
}
まず、ポインタを扱うときはプログラムがフリーズしたりクラッシュしたり、悪いことが起こらないように常にNULLかどうかをチェックしてください。
ポインタがNULLを指しているかどうかは誰にもわからないし、もしかしたら誤って、または意図的にNULLポインタでこの関数を渡してしまうかもしれない
もしツリーがNULLであれば、つまりそこにツリーがなければ、明らかにその数字は存在しない→その場合はfalseを返す
これはベースケースの一つ。

その他、探している数字がツリー自身の数字よりも小さい場合
else if(number < tree->number)
{
return search(tree->left, number);
}
↑もし、引数で求めた数字がツリー自身のnumberフィールドの数字よりも小さければ、それは「左に行きたい」ということを意味する
電話帳では電話帳の左に行ったが、ここでは左のサブ・ツリーに行くことになる
しかし、サブ・ツリーを検索するにはどうすれば良いか？
↑ここで、ツリーが再帰的なデータ構造であることが重要になる
ツリーは2つのサブ・ツリーに新しいルート・ノードを加えたもので、先ほど(上記のコード)と同じ
つまり、より小さなツリーを検索するコードはすでに用意されている
従って、「左側のツリーをsearchする return search(tree->left, number);」とだけ書けば良い。つまり、現在のノードから始まり、左の子に行き、同じ数字を渡す、という意味。番号は変わらず、ツリーは左の子になっている。←コードでは事実上、ツリーを半分に切ったことになる＝右半分は無視
そして、その答えが何であれ、それを返す
そうでなければ、もし気になる数字が現在のノードの数字よりも大きければ逆のことをする
else if(number > tree->number)
{
return search(tree->right, number);
}
右のサブ・ツリーを検索し、同じ数字を渡す
上から下へ進むにつれて、左右のツリーを切り倒して行き、どんどん対象を絞っていく
最後の1つの場合は？
→ツリーそのものにその数字が含まれている場合
つまり、ツリーの中の数字が探している数字と同じなら、先に進み、この場合に限りtrueを返す
else if(number == tree->number)
{
return true;
}
ここでまたコードがちょっと…再帰的というか、ちょっと頭を悩ませることになる
NULLだった場合はfalse、4つ目の場合はtrueしか無い→真ん中の2つの枝のどちらにもtrueもfalseも無い
↑それで良い。なぜならこのコードは左のサブ・ツリーを検索して何も無かった場合、つまり文字通り木の葉のところにいた(ツリーにいなかった)場合にはfalseを返すように設計されているから→ツリーに存在しなければ、ツリーの端っこから落ちてNULLに行き着くからfalseを返す
この2つの検索の内部呼び出し、再帰呼び出しは、ちょうど責任転嫁のようなもの
自分で真偽を答えるのではなく、左または右のツリーをそれぞれ検索して、より小さな質問の答えを返している
このように、再帰性は必ずしも強制的なものではなく、適切なものであると言える
データ自体が再帰的であれば、コード化技術としての再帰性はむしろ輝きを増す
つまり、week0で簡単に説明したかもしれないが、マイナーな最適化を行うならば、もちろん数字が等しいかどうかを明示的にチェックする必要はない
最後の条件を取り除き、もしそれがNULLでなく、左でも右でもなければ、私たちはその上に立っているに違いないと仮定すれば良い。そこでtrueを返すだけ
ここで状況をまとめてみよう
これで2次元のデータ構造ができた
2次元であるという点で、連結リストよりも優れていると言えるだろう
この二分探索ツリーの定義に従ってデータをソートしておく限り、二分探索を取り戻すことができるのは素晴らしいこと
しかし、我々は代償を支払った
これまでの話では必ずしも良いことばかりは起きていない
ツリーの欠点とは何か？
ツリーの長所を説きながら、密かに、我々はどんな代償を支払ったのか？
繰り返しになるが、この文脈での答えは、空間、時間、開発者の時間、お金、何らかの資源、個人的なもの、物理的なもの、現実の世界のものであることが多い。
べスリー「挿入はもはや一定の時間O(1)ではなくなったと思う。そして、更に多くのメモリが必要になったはず。今回は1つのポインタではなく、2つのポインタをソートするためにメモリが必要になっている」
↑その通り。挿入はもはや一定の時間ではなくなった。なぜなら、もしソートされた順序を維持する必要があるなら、それを一番上に置くことはできないから
他の物をどんどん下に押し込んでいくわけにはいかない
その場合、順序を維持したとしても非常に長くて筋張ったものになってしまうかもしれない
例えば、もう一つの数字、もう一つの数字を追加して、トップに詰め込んでしまうと、おそらくバランスを保つ必要がある
更に大きなポイントは、2倍の数のポインタを使っていること
我々のノードは以前より多くのメモリを使っている
これはトレードオフの関係にある
ここで挿入に関して、二分探索ツリーに挿入するときの実行時間を考えてみよう
アンケート→多くの生徒がO(log n)と予想
一部はO(n^2)と予想したが、これだと連結リストなどを超えて最悪ということになる←幸い、状況はそこまで悪くない

例えば、先ほどの二分探索ツリーに8を加えたいとする
ルート4から始める→8は4より大きいので右に進む
6→8は6より大きいので右に進む
7→8は7より大きいので右に進む
そして、新しいノードがこの下のどこかに作られることになる
mallocを呼び出してメモリを用意し、いくつかのポインタを用意すればツリーに8つ目のノードが追加されたことになる
↑ルートから始めて、1、2、3…とこれだけのステップを踏んだとして、これをO記法に一般化するにはどうしたらいいか？
綺麗にバランスよく配置すると、二分探索ツリーの高さはnの対数になることがわかった
nがノードの総数だとすると、log_2 nがツリーの高さになる
つまり、n個のノード、n個の数字を取り、それらを綺麗にソートしてバランスを取ると、全体の高さはlog nになるということ
挿入の実行時間は、新しい数字が属する場所を見つけるのに何ステップかかるか？に相当する→みんなの予想通り、O(log n)になる
しかし、少しずさんになって、ちょっとした不運をもたらすノードを挿入し始めたらどうだろう？
例えば下のようなツリー
1
2
3
「大きければ右」という二分探索ツリーのルールにはしたがっている
左のサブ・ツリーは無いが、探索木の定義に反しているものはないので、厳密には問題ではない←二分探索ツリーであることには違いない
しかし、これはちょっとした特殊ケース、変則的なケースで、挿入の仕方によって二分探索ツリーは実際にはもっと何かに似てくると言ってもいい
↑連結リストに似ている
上から下へ、つまり2次元的に描いているが、これはアーティストが描いたものにすぎない
これは二分探索ツリーでもあるし、連結リストとも言える
どんなに善意のデータ構造であっても、不幸な入力や不運な設計があると、偶然にも別のデータ構造になってしまうことがある
しかし、このような値でも解決する方法がある
1、2、3を挿入すると、それが長くなって筋状になり、その時点ですべてがO(n)になるという変則的な状況を許容することができる
↑それはただの連結リストで、たまたま左から右へ、ではなく斜めに描かれているだけ
そもそも1、2、3の木が長くて筋張ったものにならないようにするための解決策がここにはある
オーディエンス「2を木の一番上にある新しいルート・ノードにしたらどうか？」
その代わりに、ノードを挿入するときに、単純に「右、右、右…」と進んでいかないようにしたらどうか？←何らかの判断を下す
そして、自分のデータ構造やツリーが長くなってきたことに気付いたら、2つ目の次元を使って実際に回転させ、ルートを変えてみるべきかもしれない
コンピュータサイエンスのデータ構造とアルゴリズムの上級クラスを履修すると、AVL木や赤黒木など、様々なタイプの木のデータ構造を学ぶことができる
これらのデータ構造には、挿入や削除の際にツリーのバランスを常に保つために、必要に応じて物事をシフトさせるアルゴリズムが組み込まれている
そういった方法を用いると少し時間がかかるかもしれないが、多くのデータを持っている場合、高さが直線的に長くなったり、筋張ったりするのではなく、高さが対数的になるようにバランスを保つことは、用途にもよるが全体的にかなりの時間を節約することになるだろう
つまり、バランスの取れた二分探索ツリーへの挿入は、確かにO(log n)だと言えるかもしれない。しかし、それはバランスが保たれていることが条件。
そのためには今日の説明以上に多くのコードが必要になるが、設計上の決断としてはありうること
ここまで配列、連結リスト、ツリーと進んできたが、それぞれ素晴らしい点と欠点があり、それらはトレードオフの関係だった
しかし、これらのアイデアのいくつかは、他の構造にも応用できると思う

質問のコーナー
「右側に1、2、3が一列に並んでいるのはなぜ問題なのか？」
↑必ずしも問題ではない。あまり大きなデータセットではなく、構造内の値が少ない場合は、正直なところ、誰も気にしない。要素が3つでも、10個でも、1000個でも、コンピュータが十分に速ければ100万個の要素があっても大したことではない
しかし、それが1000万、10億の要素になると、あなたが構築しようとしているビジネスが何なのか、あなたが作ろうとしているアプリケーションが何なのか、に全く依存してしまう
あなたが書こうとしているアプリケーションは何なのか？データの大きさは？使っているコンピュータの速度は？←最終的にはそれが重要な判断材料になる
実際、2週間前にアルゴリズムを見たとき、バブルソート、選択ソート、マージソートを比較したとき、n log nとn^2の異なるカテゴリの間で、かなりの違いがあったことを思い出してほしい
検索の文脈では、log nはnよりもはるかに優れている
もし、あなたのデータ構造が長く糸のようなものになってしまったら、それは電話帳を1000ページ検索するようなもの←二分探索なら同じページを検索するのに1000ステップではなく10ステップで済む

それでは、それぞれの長所を生かすことができないかを考えてみよう
ここまで配列、連結リスト、ツリーを見てきた
ここでちょっとしたフランケンシュタインのように、色々なものをマッシュアップして、これらのものの最良の特徴を取り入れて、より大きなものを作り上げることができたらどうだろう
実際、私はデータ構造の究極の目標は、検索と挿入に要する時間が、O(n)、O(log n)でないものだろうと思っている→究極はO(1)
コンピュータのメモリを巧妙にレイアウトして、値を検索したり挿入したりしたいときに一瞬で完了するようにできたら？
直線的、対数的な実行時間ではなく、一瞬で終わる
ここで、ハッシュテーブルと呼ばれる話題を紹介する
ハッシュテーブルは、基本的には連結リストの配列である別のデータ構造のこと
つまり、このフランケンシュタインの怪物は、最終的に配列と連結リストを組み合わせたもの
まずサイズ26の配列から始めようと思う
よりわかりやすくするために、配列を垂直に描き始める
そして、今気になっているデータ構造が、数字よりももっと面白いものだとする
辞書や携帯電話の連絡先や名前のようなものを保存したいとする
自分が知っているすべての人を記録しておきたい場合、人を探すのに線形時間や対数時間がかからなければいいよね。むしろ一瞬であれば尚良いと思われる
先ほどのサイズ26の配列→英語にはAからZまで26の文字があるので、0番がA、26番がZだとする
新しい携帯電話の連絡先アプリケーションにすべての友人を挿入するとしたら、どこに入れれば良い？
それぞれの要素を0から25、あるいはAからZと考えてみよう。
そして、新しい友人や連絡先を携帯電話に挿入する際には、その名前自体と何らかの関係がある場所に入れてみよう
ただ最初から入れるのではなく、必ずしもアルファベット順に並べる必要はない
この配列の特定の場所に、上から下へではなく、特定のエントリに配置してみよう
例えば、私が最初に連絡先に追加したい人がAlbusだとする
AlbusはAから始まるので、Aの位置、つまりこの配列の最初の(一番上の)エントリに入れることを提案する
次にZachariasを追加したいとする
彼の名前はZから始まるので、最後の(一番下の)エントリに入る
このように、私はあちこち飛び回っている→0から25まで飛んだ
でもこれは配列なので、一定時間で行うことができる
[]表記を使えば、任意の要素をランダムに検索できる
だからこれらの要素はどちらも一定時間で置けた。Albusのすぐ後にZachariasを置く必要はない→好きな場所に置くことができる
三人目がHermioneだとする
彼女はHの位置に置く。なぜなら、計算してみるとHの位置がどこかわかるから
アルファベットの特定の文字にすぐにジャンプすることができる
そして、ASCIIとちょっとした算術のおかげで、それを数字に変換することができる
Hは8番目の文字、つまり7の位置に対応しているので、彼女は0、1、2…6、7の位置、となる
私のアドレス帳には他のすべての人々が登録されている
私の友人は26人もいないので、データには多少のギャップ(空いているところ)があるが、ここには全員を割り当てることができる
しかし、問題があるかもしれない
私はここまで幸運だっただけで、名前の頭文字が他の人と重複しない人しか知らなかった
しかし、学校で出会った人を連絡先に追加したとたん、例えばHarryは同じ場所に行かなければならなくなった
HermioneとHarryの両方を保存したい場合には問題がある←どちらもHで始まるから
しかし、これが配列であれば、致命的に問題になる。その時点ですべてが壊れてしまう
なぜなら、サイズを大きくすることはできるが、そのサイズは27と決まっている
「どの数字がどの文字なのか」をどうやって知るのか、ということになる→完全な混乱状態に陥る
では、連結リストのアイデアを借りて、配列を連結リストの配列にしたらどうだろう？
それなら、HermioneとHarryが配列の中で同じ位置にあるという衝突があっても、それはそれで良くなる
万が一そのようなことがあっても、左から右へと連結リストに繋ぎ合わせていくだけ
これは理想的な方法ではない。なぜなら単純な算術と[]表記を使ってHarryにたどり着くのに、1ステップではなく2ステップかかるから
しかし、少なくとも私のアドレス帳には彼を入れることができるようになる
ちょっとしたトレードオフだが、合理的な選択ではある
さて、他の人、Hagridだが、アドレス帳のHagridのところまで行くのに3ステップかかるのは理想的ではないよね
しかし、Harryと同様、アドレス帳に彼の名前が入っていないのに比べれば3ステップで見つけられる方がはるかにマシ
↑ハッシュテーブルとは、まさにこのようなデータ構造のこと。
それは連結リストの配列で、そのように実装することができる
そして、ハッシュ関数という概念を導入することが前提になっている
これは実際近いうちに他の文脈で見られるようになるだろう
ハッシュ関数を使えば、たくさんの人をそれぞれの場所に確実にマッピングすることができるようになる
つまり、ここにはランダム性は存在しない
この人たちの名前を見るたびに、その人たちが所属する場所がわかり、その場所は決して変わることはない
では、どうすれば良い？
それは、問題解決そのものと、機能とは何かということを考えれば良いことがわかる
input　→　■　→　output
これはまた、入力と出力を持つ任意の言語の関数でもある
ハッシュ関数は今のところ■の中の秘密のソースのようなものになる
ハッシュ関数とは、文字通り、数学的またはプログラミング的に、ある文字列(この場合は友人の名前)を入力とし、ある出力を返す関数の事
ハッシュ関数の出力は通常、数字である
この場合、私が欲しいのは0から25までの間の数字
ハッシュテーブルという概念を画面上だけでなく実際のコードで実装するには、文字列(char *)を入力として受け取り、0から25までのintを返す関数を書かなければならない
これにより、HermioneやHarry、Hagridを7という数字に変換する方法を知ることができる
では、このハッシュ関数は何をするのだろう？
Albusのような入力を受けて0を出力し、Zachariasのような入力を受けて25を出力する
このようなものを実装するために私が書くコードは、ユーザーの入力であるChar *を見ることになるだろう
そして、最初の文字を見て、この場合はそれぞれAかZになる
そして、ちょっとした計算をして、65などを差し引く
そして、シーザー暗号やこれまでの文字列操作と同じように0から25までの数字を得ることができる
ここからは、このビルディングブロックを使って、もう少し効果的に問題を解決することができるだろう
例えば、たくさんの友人のために部屋を用意した結果、それらの連結されたリストのいくつかが少し長くなっているのは気に入らないだろう
そして、ここで使える別の用語がある
これらはチェーンリンクフェンスや鎖の小さなリンクのように見えるので、言ってみれば鎖のようなもの
これらは鎖であり、連結リスト
中には長くなり始めているものもある
一定の時間、つまりO(1)を目指しているのに、技術的には文字通り1ステップで済む名前もあれば、2～4ステップかかるものもある、というのはちょっと馬鹿げている
↑そこで、派生版を考える
どうすれば最適化できる？
もしあなたが人気者で、連絡先にたくさんの名前があり、HやLの検索に他の人よりも時間がかかっていることに不快感を感じ始めたとしたら、状況を改善するために何ができるだろう？
あまりにも多くの衝突が発生し、あまりにも多くの名前が互いに衝突している場合、論理的な解決策は何だろう？
どうすればパフォーマンスを向上させることができる？
オーディエンス「最初の文字だけでなく、もっと多くの文字をハッシュ関数で見るべきでは？例えば2番目の文字も見てみる、とか」
↑良い発想だ。人の名前の頭文字だけでは明らかに不十分、ということだね
なぜなら私たちの多くはHやA、Zなどで始まる名前を持っているから
それなら、2文字を見て、衝突する確率を減らすことができないだろうか？
そこで先ほどのハッシュテーブルを再構築してみよう
Hermione、Harry、Hagridの問題に焦点を当てて、
ハッシュテーブルの配列(ここでは縦長のもの)を取り出して、その場所にあるのはHだけではないと考えてみよう
その場所が具体的にHaから始まり、Hb、Hc、Hd…Hzまでと続くと考えたらどうだろう
そして、Ia、Ib…Iz…と、AaからZzまでの文字の組み合わせをすべて列挙する
これは物事を分散させるように思える
なぜならHermioneは配列のHeの位置に入るから
HarryはHaの位置、Hagridは…ああ、くそ。HagridはまだHarryと同じ場所に入ってしまった
どうすればいい？繰り返しになるが、これはひどいものではない。特に高速なコンピュータでは2つのステップは大したことではない
ただし、大規模なデータセットでは、もはや連絡先に登録されている人の話ではなく、世界中のGoogleアカウントやTwitterアカウントを持っている人の話となると、これらの情報を素早く検索したい場合には名前がHやA、Zで始まる人がたくさん出てくる
それを更に分散させることができれば良いが…どうする？
最初の2文字を使うだけでなく、論理的には最初の3文字を使うことになると思う
Haa、Hab、Hac…Hzz、そしてIaaに至るまでのすべての文字列
先ほどの3人の友人をハッシュ化すると、HermioneはHerの場所に入り、配列の要素となる。HarryはHar、Hagridもみんなと同じようにHagという自分だけの場所を見つけることができた
これで問題は解決したように見える
もっとよく考えて、他にもHagやHarやHerで始まるハリーポッターの名前があるかどうかGoogleで調べてみるといいかもしれない
なぜなら、代わりに4文字使うこともできるから
しかし、そのために我々はどんな代償を支払っているだろうか？
この方法で我々は検索時間を短縮しようとしてきた
ちょっとしたASCIIの計算をするだけで、どんどん大きくなる配列の中でジャンプすべきインデックスの番号を数学的に把握することができる
しかし、私はどんな代償を払わなければならない？
オーディエンス「これはかなり多くのメモリを使わなければならないだろう」
↑その通り。膨大な量のメモリを必要としている
以前はどのくらいのメモリが必要だった？
元々26個の場所、いわば配列の要素があったとすると、もちろん、それほど悪くはない
しかし、その欠点として3つ、4つ…あるいはもっと多くの名前を持つようになり、チェーンが長くなる可能性がある
一方で、AからZまでではなく、AaからZzまでとすると、26×26で676個の場所が必要になる
これまで行ってきたほとんどのことよりも大きいが、大したことではないようにも聞こえる
しかし、それが3つとなると26×26×26で17,576個の場所が出来てしまう
問題は、そのメモリが必要になることではない
正直なところ、メモリが必要であれば使えば良い。もっとメモリを増設してアップグレードすれば良い
問題は、名前がHaaやAzzなどのアルファベットの組み合わせで始まる人を、それほど多くは知らない、ということ→多くの場所は使われずに空っぽのままになると考えられる
しかし、空であっても問題はない
week2で書いたように、[]表記を使ってメモリ内の気になる場所にジャンプするだけで演算が上手くいくように、配列やランダムアクセスが必要な場合は、それらが存在しなければならない
このように、トレードオフを見つけたり、トレードオフの変曲点を見つけたりすることは芸術や科学のようなもので、特定のデータやアプリケーションに対して、時間と空間のどちらがより重要か、あるいは両者の間のハッピーミディアムを見つけ出すこと
Pset5では最終的に自分のメモリ使用量とコンピュータの時間使用量を最小限にすることで、このバランスを考えなければならない
ここで一つ指摘しておきたいことがある
このハッシュテーブルという概念は、今まで見てきたデータ構造の中で最も洗練されたものであることに間違いは無いが、皆さんにとってはすでにお馴染みのものではないだろうか
このカードは皆さんの家にあるトランプよりは大きいかもしれない
しかし、もしあなたがこのカードで遊んだことがあり、カードがランダムに出てくるとしたら、あるゲームのためにカードをソートする必要があるかもしれない
時には完全にシャッフルする必要がある
整理したいのであれば、数字だけでなくスーツ(マーク)ごとに分類することもできる
ハート、スペード、クラブ、ダイヤを別々のカテゴリに分けたり
↑比喩のためにこれらのマークが書かれた4つのバケツを持ってきた
今までにトランプを分類したことがあるかもしれないが、その時には無意識に値をハッシュ化したことがあるはず
もし1枚目を見て、ああ、これはダイヤのエースだな、と思ったとする
最終的にはダイヤであること、エースであることを気にするかもしれない
でも今は、例えばダイヤのバケツに入れておこうと思う
→次々とマークに応じてそのマークのバケツに入れていく
実際、ハッシュ化とは、ある入力を見て、その入力の特徴(カードのマークやアルファベットの文字)に基づいて、バケツの0、1、2、3のような数値を出力すること
今まで皆さんもこのような経験があるはず。なぜこんなことをやった？
オーディエンス「バケツの中身がわかれば、より早く検索対象にたどり着ける可能性がある。0、1、またはそれ以下で検索できるようになるかもしれない。」
↑その通り。少なくとも人間としては1つの大きな問題(トランプならサイズ52)よりも4つの小さな問題(マーク毎のサイズ13)を処理する方がはるかに簡単になる
ここでは一種の最適化がなされている
つまり、入力としてカードを受け取り、特定のバケツにハッシュ化してから、より小さな問題を解き進めることができる
しかし、ハッシュテーブルの本質はそこではない
ハッシュテーブルの目的は情報を保存することだが、情報を保存することで、より素早く情報を得ることができる
もしダイヤのエースを見つけたいなら、サイズ52の配列や連結リストではなく、サイズ13の問題、つまりサイズ13の連結リストを調べれば良いことになる
つまり、ハッシュテーブルを使えば、入力をバケツ化することができ、より素早くデータにアクセスすることができる
一般的には純粋に線形的に、対数的に何かを行う場合よりもステップ数は少なくなる
理想的には、A～Zではなく、Aa～Zzなどを使って、衝突(重複)する要素の数を最小限にするようにハッシュ関数を選択する
質問→ハッシュテーブルの場合、実行時間はどのくらいになる？
ハッシュテーブルですべてのデータが入っていて、携帯電話にn人の連絡先があるとすると、ある特定の人のデータにたどり着くまでに何ステップ踏む必要がある？
アンケート→80%がO(1)、20%がO(n)
実は20%のO(n)と答えた人が技術的にも数学的にも正しい。
ここで、現実の世界とアカデミックな世界との違いが見えてくる
現実世界のプログラマーは、13枚のカードが入ったバケツの方が、52枚のカードが入ったバケツよりも絶対に良いと言うだろう←13ステップの方が52ステップより4倍速いから
しかし、学者は「そうだ。しかし漸近的には、13のステップを踏むことは、技術的にはO(n)である」と言うだろう。漸近的とは、nが非常に大きくなるにつれてということ
なぜそうなる？ここにあるカードの場合、技術的にはnを4で割って13となる
しかし、カードが全部でn枚の場合、技術的には、このバケツの大きさはn/4になってしまう
過去に実行時間について話したとき、4で割るとか、何かを加えるとか、そういう定数は捨てると説明した。つまり、÷4は取り除いて考える
技術的にはハッシュテーブル検索もO(n)のまま
しかしながら、現実世界とアカデミックな世界はやはり違う
技術的にハッシュテーブルが線形探索や連結リストと同じだとしても、現実的には異なる
例えば、これらの値を事前にハッシュ化して、4個、26個、576個のバケツに分散させておけば、実際の経過時間(wallclock time)に換算すると、その方が速くなる
つまり、実際の時計を見ると、配列や連結リストのアプローチよりも、ハッシュテーブルのアプローチの方が、より短い時間しか経過していない
アンケートでO(n)と答えた人は正しいが、しかし、実際のプログラミングでは正直nステップより速いのであれば、それは十分良い事と言える
だから、我々はもっと実践に重きを置くべきであり、時には理論に重きを置くべきではない
実際、それが課題となる
Pset5では10万以上の単語を使って、ハッシュテーブルというデータ構造を実装することが課題となっている
簡単に言うと、1行につき1つの英単語が書かれた大きなテキストファイルを用意する
そして、14万語以上の英単語をハッシュテーブルを使ってコンピュータのメモリに読み込むことが、あなたの目標となる
単純化して、A～Zまでの26個のバケツを持つハッシュテーブルを使った場合、多くの衝突が発生する
14万語以上の単語にはA、B、Z、またはその中間で始まる単語がたくさんある
Aa～ZzやAaa～Zzzまでの方が良いかもしれない
しかし、ある時点で自分のためにメモリを使いすぎてしまうことになる
オプションであるPset5の課題の1つは、遊び心を持ってクラスメイトに挑戦すること
これを選択すると、コマンドを実行して、使用しているRAMやメモリの量や、コードの実行時間の長さをコースのウェブサイトに表示するボードに載せることができる
学術的にはみんなのコードはO(n)だが、トランプのアプローチであるn/4は、nよりも実際にははるかに優れている
このように、理論と実践の間の対比を解き明かしていく
しかし、メモリ上にレイアウトする方法はこれだけではない
ここでは、これらの構成要素をすべて手に入れたときに出てくる他のアイデアをいくつか紹介したい
その1つが、これから「trie」と呼ぶデータ構造
trieはretrievalという言葉を短くしたもの
プレフィックスツリーとも呼ばれる
これは異なるタイプの木で、通常、数字だけてなく、単語やその他のより高度なデータを格納するために使用される
trieは実際には配列で構成されたツリー
ハッシュテーブルは連結リストの配列
trieは各ノードが配列で構成された木
コンピュータ科学者たちは、ある時期から少しずつ創造性を発揮して、文字通り様々なデータ構造を融合して、何かを生み出そうとしたようだ
その結果、trieは次のような形になった
このtrieにはこれまでの理論に見たものよりも優れた素晴らしい特性がある
ここにtrieの1つのノードがある
これは、長方形や正方形のような意味でのノード
そのノードの内部には、この場合、サイズ26の配列がある
そして、それぞれの場所またはバケツはA～Zを表す
これからハリーポッターの名前のような単語を挿入するたびに、H-A-G-R-I-Dのように名前の文字をたどっていき、次のように、あるノードから別のノードへの一連のポインタをたどっていく
例えば、これがA～Z、あるいは0～25であれば、ここにはHという場所がある
現時点の目標が、連絡先の最初の1人、例えばHarryを挿入することだとすると、まず最初のノード、ツリーのルートを見て、Hの場所を探す
そして、Hagridがそこから始まること、HagridのHがそこから始まることを心に留めておく
そして、もしHagridのAを挿入したいのであれば、新しいノードを追加して26文字を表す
そこで、私は「OK、Aはここにある」という事実を記録しておく(ポインタで)
H→A→G→R→I→D
trieとは木の事で、各ノードが配列になっている
その配列は、それぞれ他のノードへのポインタの配列
ここではすべての構成要素がマッシュアップされている
このツリーの各ノードは、上から下まで、他のノードへのポインタの配列になっている
例えば、Hagridが自分の連絡先にいるかどうかを確認したい場合、文字通り最初のノードから始めて、Hポインタをたどる
→Aポインタをたどる→Gポインタをたどる…→R→I→D(緑のボックス)の順に進む
この構造体の中にはブール値がある。これについてはまた別の機会に説明するが、「はい」か「いいえ」で私の連絡先にHAGRIDという名前の人がいることを示す
今のところ、他の文字は表示されておらず、Dの他には緑のボックスもない
つまり、名前がHAGRIA、HAGRIB、HAGRICの人はいないということ
一方で、Harryを探してみると、HarryとHagridはHとA、そして、3番目のノードを共有している
H→A→R or D
しかし、HarryはRとYを格納するために別のポインタをたどる必要がある
H→A→R→R→Y(緑のボックス)
ここで緑の部分に注目してほしい
この緑のボックスはデータ構造のチェックマークのようなもので、ブール値で「はい」を意味する
私の連絡先にHarryという名前の人がいる
そして、Hermioneを追加すると、彼女はHを共有し、2番目のノードも共有する
H→A or E
その後、Hermioneはいくつかの新しいノードを必要とする
この重要な特性に注目してほしい。このような複雑さは、恐らくこれまで見てきた中で最も奇妙な構造
たとえ電話帳に10億人の名前があったとしてもHagridを見つけるのに何ステップかかる？
→6ステップ(H→A→G→R→I→D)
20億、40億人いたら何ステップ？
→6ステップ
少なくともデータ構造の中の人間の名前の長さ分だけの一定の時間がかかる
trieデータ構造にどれだけ多くの名前を詰め込んでも、名前の総数は、特定の名前を探すのにかかるステップ数に影響しない
あくまで名前の長さ分しかかからない
ここで少し学術的な話をする
実在の人物であれ、空想上の人物であれ、名前の文字数には限りがあると仮定すると、それは多分20とか100とかだと思う
6文字よりは多いが数百はいかないだろう←それが一定であると仮定することができる
技術的には、trieを使えば、O(1)の検索時間と挿入時間という究極の目標を手に入れることができる
なぜなら、データ構造内の他の人の名前の数であるnには依存しないから
入力する名前の長さにのみ依存する
もし、世界中のすべての名前が適度にリンクされていて、6とか200とか、ある有限の値よりも小さいと仮定すれば、それを呼び出すことができる
そして技術的にはO(1)、つまり一定時間になる
これが、今日一日の目標だった「時間の一定化」
なぜなら一定の時間は、線形時間や対数時間、あるいは我々が見てきた他の何よりも優れているように思われるから
しかし、常にすべてはトレードオフの関係にある
今、我々はどんな代償を支払ったのだろうか
オーディエンス「例えば、あなたの連絡先に2人の人がいるとする。一人はDanielで、もう一人はDanielleという名前。Danielがすでにリストに入っているとlがtrueのブール値を持っていることになる。しかし、そのlが演算子であり、Danielleを表す別のlを指していない場合、どうやってDanielleにたどり着くのか？」
↑面白い着眼点。特別なケースと言えるが、ある人の名前が他のある人の名前の部分文字列だったらどうするか？という質問だね。←それは解決できる問題だと仮定しよう。私はこのツリーの各ノードを表すコードをまだ示していない。そのようなケースでも下に矢印を続けることができることを指摘させて欲しい

オーディエンス「このtrieの全てを収納するには膨大なメモリが必要になるのでは？そして、それには多くの時間がかかり、システムが遅くなる可能性があると思う」
↑その通り。現在、3人の名前しかリストにないのに、それらがNULLだとしてもここには何十～何百ものポインタが描かれている。
配列の各ブロックにポインタが無い、ということはNULLということになるが、NULLを格納するにしても8個の0ビットが必要になる
つまり、実際のメモリ使用量が不足しているわけではなく、効率的に使用していないだけ
一番上のHのノードでも、26個のポインタのうち、1つしか使っていない
他の25個のポインタはNULLに初期化されているので、25個のポインタを無駄にしていることになる
そして、ツリーの下の方に行けば行くほど、HAGRIDで始まる名前がある可能性はどんどん低くなっていくことは想像できるだろう
一定時間で検索できることの代償は、何MB、何GBものストレージスペース＝メモリ
配列は前後に連続しているからこそランダムアクセスが可能←その分メモリを多く消費する
理論的には理想かもしれないが、理論は必ずしも実践を意味しない
教科書では効率の悪い設計でも、実際にはより効率的な場合もある
Pset5では、あなた自身のスペルチェッカで、非常に大きなテキストコーパスのスペルチェックに使用する辞書を構築する際に、現実世界でのトレードオフをあなた自身が経験することになる

そして、今日の最後に、この種のデータ構造で他に何ができるのかを見てみたいと思う
これまで見てきた配列は本当に最も単純なデータ構造で、配列それ自体はただの連続したメモリのブロックに過ぎない
その後、連結リストを紹介した。連結リストは1次元のデータ構造で、ノードとメモリをつなぎ合わせることができ、動的な割り当てが可能
また、ノードを挿入したり削除したりして割り当てを解除したい場合は、ツリーが登場した。ツリーは配列と連結リストの両方の長所を兼ね備えている
しかし、より多くのスペースを使い、より多くのポインタを使用しなければならない
その後、ハッシュテーブルが登場し、配列と連結リストの二つのアイデアが融合した
それは上手く機能した。実際、自分のスペルチェッカを使って実験してみると、そのことを実感するだろう
最後にtrieもある。一見より良いように見えるが、大きなコストがかかる
そこで、これらのビルディングブロックを自由に使えるようにすると、より高いレベルの問題を解決するために、低レベルの実装の詳細として実際に使用できることがわかった
これが抽象データ構造、または抽象データ型と呼ばれるもの
抽象データ構造とは、現実世界の問題を実装するために思い浮かべる心の中の構造のようなもので、通常は他のデータ構造で実装されている
つまり、このレベル(低いところ)でコードを書いているようなもの
しかし、最終的にはこのレベル(高いところ)で構築したものについて考えることになる
それは抽象化であり、低レベルの実装の詳細を、上のレベルでの議論や問題解決のために単純化すること

そのようなデータ構造にはどのようなものがあるか？
queues(キュー)＝待ち行列は、非常に一般的な抽象データ構造
queuesとは？イギリスで育った人は、お店の外に並んでいる列をqueuesと呼ぶ
実際にそれが名前の由来となっている
つまり、お店やレストランの前に立って入店を待っている人は、一般的には行列の外にいることになる
しかし、待ち行列には重要な特性がある
少なくとも、公平な社会に生きている人なら、自分が最初に並んだら、最初に抜けられると思いたいはず。最初に入ったら、最初に出る。
自分が最初に並んでいるのに、その列の後ろにいる人たちを入れ始めたら、ちょっと不愉快だよね。
そこで、待ち行列が正しく実装されていればFIFO(First In , First Out 先入れ先出し)と呼ばれる性質を持つ
私たち人間は、これを公平な性質だと考えるだろう
そしてqueuesには一般的に、enqueueとdequeueという2つの操作が関連付けられている
これは単なる慣習で、追加や削除、あるいは挿入や削除など、何とでも呼べる
enqueueとは、お店に行って列に並び、待つ、ということ→列に入る
dequeueは、「あなたにサービスを提供する準備ができました」という意味→それで列から出る
どのようにしてqueuesを実装する？
このデータ構造の面白いところは、抽象的であるということ
実際のコードよりもアイデアに近いもの
ある種の公平な待ち行列システムを作りたい
率直に言って、この例をコードに置き換えるならば、人の配列を使うことを想像できるだろう
人の連結リストを使うこともできる
↑配列でも連結リストでも実際には同じように機能するだろう
覆いの下には、低レベルの実装の詳細がある
しかし、お店に入るために外で行列を作るような現実世界の例えをコードに置き換えて、配列を使った場合、何が問題になる？
現実世界からいきなりコードに飛躍したとしても、一般的に行列を表現するのに配列を使うことに何かデメリットはあるだろうか？
オーディエンス「配列を使った場合、既存の値をそのまま取り出すことはできない。メモリを動的に割り当てなおすことができないため、最初の人が出るには、新たな配列を用意しなければならない」
↑良い指摘だ。
アップルストアの前に10人並んでいるとする。
6フィートずつ離れたところに10人分のスペースがある
もし誰かをdequeueするなら、最初に並んだ人が店の中に入ることになる
そして2人目の人を次にdequeueする…
配列の問題点は、列の先頭に基本的に空のスペースがあることだと思われる
しかし、列の最後にはまだ新しい人を入れるスペースが無い
これには解決策がある→「みんな、少し前に出てくれないかな」と言えば良い
しかし、これは非効率。人間の世界ではそうでもないが、お店に入れば良い。
しかし、コードの世界では値をコピーしなければならない
例えば、2人の人間が店に入った場合、8つの値を2つ分移動させなければならない
つまり、dequeue処理はO(n)になる
これは理想的ではない。ローカル変数などを少し賢く使えば、もっと良い結果が得られるかもしれない
しかし、配列を使ってどれだけうまく実装できるかが、queueの1つの課題になるだろう
想像するに、配列には限界があるのではないか
というのもアップルストアに行くと、すでに10人が並んでいて不愉快だよね。
並んでいる列に入れてくれない。「申し訳ございませんが、本日は満席になっております」と言われても、明らかに満席ではない
なぜなら最終的には列にもっと余裕ができるから
連結リストであればどんどん人を追加していくことができる
たとえ店の外の列が以上に長くなったとしても、少なくとも連結リストでは、時間をかけて現れたすべての顧客に対応することができる
↑固定サイズの配列ではそれが難しい
また、より大きな配列を割り当てることもできる
でもそうすると、すべてのお客さんに「ねえ、みんなこっちに来てくれない？」「いや、あそこに戻ってくれ」つまり、人間、つまり値とメモリを常に行き来させていることになる
以上が、待ち行列という現実世界の概念を実装するための注意点
待ち行列は、コンピュータの世界でも、プリンタキューなどの特定のアイデアを表現するために、非常に一般的に使用されている
例えば、何かをプリンタに送るとき、特にキャンパスやオフィスでは待ち行列ができる
理想的なのは、最初に印刷した人が、その後、最初に印刷物を手にすること
待ち行列を使うソフトウェアも存在する

しかし、待ち行列以外にも抽象的なデータ型が存在する
stacks　スタックは、配列や連結リストなどを使って実装することができるデータ構造
スタックには異なる性質がある。それは「後入れ先出し」。
最後に入って、先に出る。
カフェテリアのトレイについて考えてみよう
誰もがキャンパスでカフェテリアのトレイを使っていた健康的な時代には、トレイはこのように積み重ねられる(スタックされる)傾向があった。
そして、最後に積まれたトレイが最初に出てくる(使われる)
洋服屋に行っても、自分のクローゼットに行っても、ハンガーにかけたり、引き出しに入れたりするのではなく、ここにセーターを…というように積み上げて(スタックして)いく
この場合、一番簡単な方法は「後入れ先出し」。
しかし、もし私がすべてのセーターをこのスタックに保存していたら、赤や青のセーターのような、低レベルの(下の方にある)セーターにはたどりつけないかもしれない
つまり「LIFO」(Last In , First Out)はスタックを特徴づけるために使われる特性
スタックは現実世界の文脈に応じて、役に立つか立たないかが決まる
しかし、コンピュータの世界でも、スタックが実際に使用されるアプリケーションを目にすることがある
スタックがサポートする2つの操作は、一般的にPushとPopと呼ばれている
追加や削除、挿入や削除と同じことだが、一般的にはPushとPopと呼ばれる
push　スタックに値を入れる(押し込むイメージ)
pop　スタックから値を取り出す

そして、もう一つのデータ構造は、実際には非常に現実的な類似物を持つもので、dictionaries（辞書)として知られている
辞書は抽象的なデータ型で、配列や連結リスト、ハッシュテーブル、trieなどで実装することができ、キーと値を関連付けることができる
辞書とは、実際に紙に印刷された本の形をしている昔ながらの辞書。
その本の中にはたくさんのキーがあり、appleやbananaなどの太字の単語が並んでいて、それぞれに定義、つまり値がある
辞書は、検索しやすいようにアルファベット順に並べられている
しかし、辞書は、キーと値を関連付ける抽象的なデータ型
単語の定義を調べるときに、その単語自体を調べるように、キーを使って値を調べる
辞書は、実は私たちの身の回りにも存在する
辞書を辞書として認識している人は少ないだろう
でも、例えばニューヘブンやケンブリッジなどにある「Sweet Green」というサラダ屋に行ったことがある人は知っているだろうが、そこではネットやアプリで事前に注文してからお店に行って、棚から料理を受け取ることができる
そしてこの棚、ケンブリッジやその他の都市で行われている方法では、実際にアルファベットの文字が棚に並んでいる。A～Zまで。
そのアイデアでは、私が自分のサラダを受け取るときはDセクションで、ブライアンが受け取るときはBセクションで…ということのようだ(名前で受け取る位置が変わる)
ここでも、アルファベットの文字が、人々のサラダである値にマッピングされるこのデータ構造、つまり辞書が、必ずしもフェイルプルーフ(誰が扱っても安全で、ミスができないようにする仕組み であり、人為的なミスに対してあらかじめ対策を講じる考え方)ではないという意地悪な例を考えることができる
Sweet Greenの非常に素晴らしく整然としたシステムが実際に破綻するような逆説的な事例を思い浮かべることができる？
もしお店に行って、あなたの名前に基づいて何かを選ぶとしたら、このシステムでは何が問題になるのか、制限を考えられる？
オーディエンス「同じ名前の人がいると、被ってしまうのでは？」
↑その通り。同じ名前の人がいると、物が積み重なっていく
実際、Sweet Greenではそのような場合、サラダを重ねる
また、あるデータ型の上に別のデータ型を重ねるという、興味深い現象も起きる
これらはすべて、いわばスクラッチのカスタムピースのようなもので、私たちは常により面白くてパワフルなアイデアに組み替えている
しかし、ある時点で、BやDなどのアルファベットがたくさんあると、この棚の高さには限界がある
だから、Sweet Greenは、配列を使ったスタックで辞書を実装したようなもの
なぜなら、配列はサイズが決まっているから。つまり、ここには垂直方向に数インチのスペースしかない
このように現実的な制限がある。そうなるとSweet Greenはどうする？
おそらく、ちょっとしたズルをして、DをCセクションに入れたり、DをEセクションに入れたりするだろう
現実世界では誰も気にしない。思った場所になかったら、あなたは恐らく左右に目を移すだろうから。
でも、アルゴリズム的には、それは物事を遅くしてしまう
最悪の場合、あなたがサラダを受け取るのが遅かったり、Sweet Greenがとても人気があって、棚に大量のサラダが並んでいたりすると、あなたの名前が「Albus」だとしても、あなたのサラダはずっと先のZセクションに置かれてしまうこともあり得る
これもアルゴリズムの判断としては妥当で、ある場所のスペースがいっぱいになると、どこか他の場所にスペースを確保することになる
ここでも時間と空間のトレードオフが発生している

最後に別の機関の友人が、スタックとキューの概念を区別する素晴らしい視覚化をしてくれたことに感謝して、終わりにしたいと思う

アニメ再生
さえない少年が友達ができない理由を人気者に聞く
→さえない少年はスタックで毎日同じ服を着ていた
(その日着た服を洗って服の山の一番上にしまって、また次の日も服の山の一番上にある同じ服を着ていた)
→服をクローゼットにかけて、キューにすると人気が出るよ、と教えてもらった
(クローゼットの左から取って、右にしまう)


この記事が気に入ったらサポートをしてみませんか？