Week 5 データ構造
ようこそ！
これまでの数週間で、プログラミングの基本的な構成要素を学んできました。
C言語で学んだすべてのことは、Pythonなどの高水準プログラミング言語でこれらの構成要素を実装する際にも役立ちます。
毎週、概念はますます難しくなり、まるで急な坂道を登るようでした。今週は、データ構造を探求しながら、その険しさが少し緩やかになります。
これまでに、配列を使ってメモリ内のデータを整理する方法を学びました。
今日は、メモリ内でのデータの整理方法と、皆さんの知識が深まることで生まれる設計の可能性についてお話しします。
データ構造
*データ構造（Data structures）*とは、本質的にはメモリ内での情報の整理形式のことです。
- メモリ内でデータを整理する方法はたくさんあります。
*抽象データ型（Abstract data types）*とは、概念的に想像できるもののことです。コンピュータサイエンスを学ぶ際、まずはこれらの概念的なデータ構造から始めるのが効果的です。これらを学ぶことで、後に具体的なデータ構造をどのように実装するかを理解しやすくなります。
キュー（Queues）
*キュー（Queues）*は、抽象データ構造の一種です。
キューには特定の特性があります。すなわち、「FIFO（First In First Out）」、つまり「先入れ先出し」です。遊園地のアトラクションの列に並んでいる自分を想像してみてください。列の最初の人が最初にアトラクションに乗ることができます。最後の人は最後に乗ることになります。
キューには特定の操作が関連付けられています。例えば、アイテムを*エンキュー（enqueue）*する、つまりアイテムが列やキューに加わることができます。さらに、アイテムは列の先頭に到達すると、*デキュー（dequeue）*されてキューから離れることができます。
コードでは、キューを次のようにイメージできます。
const int CAPACITY = 50;
typedef struct
{
person people[CAPACITY];
int size;
}
queue;
peopleという名前の配列がperson型であることに注目してください。CAPACITYはスタックが保持できる最大値です。整数のsizeは、キューが実際に保持できる量に関係なく、現在どれだけ埋まっているかを示します。
スタック（Stacks）
キューとは対照的なのが*スタック（stack）*です。根本的に、スタックの特性はキューとは異なります。具体的には、「LIFO（Last In First Out）」、つまり「後入れ先出し」です。食堂でトレイを積み重ねるのと同じように、最後に置かれたトレイが最初に手に取られます。
スタックには特定の操作が関連付けられています。例えば、*プッシュ（push）*はスタックの上に何かを置きます。*ポップ（pop）*はスタックの一番上から何かを取り除くことです。
コードでは、スタックを次のようにイメージできます。
const int CAPACITY = 50;
typedef struct
{
person people[CAPACITY];
int size;
}
stack;
peopleという名前の配列がperson型であることに注目してください。CAPACITYはスタックが保持できる最大値です。整数のsizeは、スタックが実際に保持できる量に関係なく、現在どれだけ埋まっているかを示します。このコードがキューのコードと同じであることに注目してください。
上記のコードには制限があることに気づくかもしれません。このコードでは配列の容量が常に事前に決定されているためです。したがって、スタックは常に大きすぎる（メモリを無駄にする）可能性があります。5000個分のスペースのうち1個しか使っていない状況を想像してみてください。
スタックが動的であること、つまりアイテムが追加されるにつれて成長できることが理想的です。
Jack Learns the Facts
- イーロン大学のShannon Duvall教授によるJack Learns the Factsというビデオを視聴しました。
配列のサイズ変更
第2週に遡ると、最初のデータ構造を紹介しました。
配列は、連続したメモリブロックです。
配列を次のようにイメージできます。
メモリ内には、他のプログラム、関数、変数によって保存されている他の値があります。これらの多くは、一度使用されたものの現在は利用可能な、未使用の「ゴミ値（garbage values）」である可能性があります。
4番目の値4を配列に保存したいとします。何が必要になるでしょうか？新しいメモリ領域を割り当て、古い配列を新しい配列に移動させる必要があります。最初、この新しいメモリ領域はゴミ値で満たされています。
この新しいメモリ領域に値が追加されると、古いゴミ値が上書きされます。
最終的に、すべての古いゴミ値が新しいデータで上書きされます。
- このアプローチの欠点の一つは、設計が悪いことです。数値を1つ追加するたびに、配列を1要素ずつコピーしなければなりません。
配列
- メモリの別の場所に
4を置くことができれば便利ではないでしょうか？定義上、これはもはや配列ではありません。なぜなら4はもはや連続したメモリに存在しないからです。メモリ内の異なる場所をどのようにつなぐことができるでしょうか？
ターミナルでcode list.cと入力し、次のようにコードを記述します。
// Implements a list of numbers with an array of fixed size
#include
int main(void)
{
// List of size 3
int list[3];
// Initialize list with numbers
list[0] = 1;
list[1] = 2;
list[2] = 3;
// Print list
for (int i = 0; i 3; i++)
{
printf("%i\n", list[i]);
}
}
上記は、このコースの序盤で学んだことと非常によく似ています。3つのアイテムのためにメモリが事前に割り当てられています。
最近得た知識を基に、ポインタの理解を活用して、このコードをより良い設計に改善できます。コードを次のように修正してください。
// Implements a list of numbers with an array of dynamic size
#include
#include
int main(void)
{
// List of size 3
int *list = malloc(3 * sizeof(int));
if (list == NULL)
{
return 1;
}
// Initialize list of size 3 with numbers
list[0] = 1;
list[1] = 2;
list[2] = 3;
// List of size 4
int *tmp = malloc(4 * sizeof(int));
if (tmp == NULL)
{
free(list);
return 1;
}
// Copy list of size 3 into list of size 4
for (int i = 0; i 3; i++)
{
tmp[i] = list[i];
}
// Add number to list of size 4
tmp[3] = 4;
// Free list of size 3
free(list);
// Remember list of size 4
list = tmp;
// Print list
for (int i = 0; i 4; i++)
{
printf("%i\n", list[i]);
}
// Free list
free(list);
return 0;
}
サイズ3の整数リストが作成されていることに注目してください。次に、3つのメモリ番地に値1、2、3が割り当てられます。その後、サイズ4のリストが作成されます。次に、リストが最初のものから2番目のものへコピーされます。値4がtmpリストに追加されます。listが指していたメモリブロックはもう使用されないため、free(list)コマンドを使用して解放されます。最後に、コンパイラに対してlistポインタをtmpが指しているメモリブロックを指すように指示します。listの内容が印刷され、その後解放されます。さらに、stdlib.hが含まれていることにも注目してください。
listとtmpは、どちらもメモリの塊を指し示す「看板」のようなものだと考えると分かりやすいでしょう。上記の例では、listはある時点でサイズ3の配列を指していました。最後には、listはサイズ4のメモリの塊を指すように指示されました。厳密には、上記のコードの最後では、tmpとlistは両方とも同じメモリブロックを指しています。
forループを使わずに配列をコピーする方法の一つとして、reallocを使用する方法があります。
// Implements a list of numbers with an array of dynamic size using realloc
#include
#include
int main(void)
{
// List of size 3
int *list = malloc(3 * sizeof(int));
if (list == NULL)
{
return 1;
}
// Initialize list of size 3 with numbers
list[0] = 1;
list[1] = 2;
list[2] = 3;
// Resize list to be of size 4
int *tmp = realloc(list, 4 * sizeof(int));
if (tmp == NULL)
{
free(list);
return 1;
}
list = tmp;
// Add number to list
list[3] = 4;
// Print list
for (int i = 0; i 4; i++)
{
printf("%i\n", list[i]);
}
// Free list
free(list);
return 0;
}
リストがreallocを介して新しい配列に再割り当てされていることに注目してください。
- 必要な3つや4つのアイテムではなく、30個など、必要以上に多くのメモリをリストに割り当てたくなるかもしれません。しかし、これはシステムリソースが必要でないときにも負荷をかけるため、悪い設計です。さらに、最終的に30個以上のメモリが必要になる保証もほとんどありません。
連結リスト（Linked Lists）
ここ数週間で、3つの便利なプリミティブを学びました。
structは自分で定義できるデータ型です。ドット記法の.を使うと、その構造体内部の変数にアクセスできます。*演算子は、ポインタの宣言や変数のデリファレンスに使用されます。今日は、
->演算子が導入されます。これは矢印です。この演算子は、アドレスに行き、構造体の内部を見ます。*連結リスト（linked list）*は、C言語における最も強力なデータ構造の一つです。連結リストを使用すると、メモリのさまざまな領域にある値を含めることができます。さらに、必要に応じてリストを動的に拡大・縮小させることができます。
3つの異なるメモリ領域に保存された3つの値を次のようにイメージできます。
- リスト内のこれらの値をどのようにつなぎ合わせることができるでしょうか？
上に描かれたデータを次のようにイメージできます。
ポインタを使って、次のアイテムがどこにあるかを追跡するために、より多くのメモリを利用できます。
リストの中に次がもう何もないことを示すためにNULLが使用されていることに注目してください。
慣例として、リストの最初のアイテムを追跡するポインタをメモリにもう一つ保持します。これをリストの*ヘッド（head）*と呼びます。
メモリ番地を抽象化すると、リストは次のようになります。
これらの箱は*ノード（nodes）と呼ばれます。ノードにはアイテム（item）*と、*ネクスト（next）*と呼ばれるポインタの両方が含まれています。コードでは、ノードを次のようにイメージできます。
typedef struct node
{
int number;
struct node *next;
}
node;
このノードに含まれるアイテムがnumberという整数であることに注目してください。次に、nodeへのポインタであるnextが含まれており、これはメモリ上のどこかにある別のノードを指し示します。
連結リストを利用するようにlist.cを書き直すことができます。
// Start to build a linked list by prepending nodes
#include
#include
#include
typedef struct node
{
int number;
struct node *next;
} node;
int main(void)
{
// Memory for numbers
node *list = NULL;
// Build list
for (int i = 0; i 3; i++)
{
// Allocate node for number
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = get_int("Number: ");
n->next = NULL;
// Prepend node to list
n->next = list;
list = n;
}
return 0;
}
まず、nodeがstructとして定義されます。リストの各要素について、nodeのサイズ分だけmallocを介してメモリが割り当てられます。n->number（つまりnのnumberフィールド）に整数が代入されます。n->next（つまりnのnextフィールド）にnullが代入されます。そして、そのノードはlistというメモリ場所で示されるリストの先頭に置かれます。
概念的に、連結リストを作成するプロセスを想像してみましょう。まず、node *listが宣言されますが、これはゴミ値を持っています。
次に、nというノードがメモリに割り当てられます。
次に、ノードのnumberに値1が代入されます。
次に、ノードのnextフィールドにNULLが代入されます。
次に、listはnが指し示しているメモリ場所を指すようにされます。これでnとlistは同じ場所を指しています。
新しいノードが作成されます。numberとnextフィールドの両方がゴミ値で満たされています。
nのノード（新しいノード）のnumber値が2に更新されます。
また、nextフィールドも更新されます。
最も重要なことは、これらのノードへの接続を失わないようにすることです。さもないと、ノードは永遠に失われてしまいます。したがって、nのnextフィールドは、listと同じメモリ場所を指すようにされます。
最後に、listはnを指すように更新されます。これで2つのアイテムを持つ連結リストができました。
- リストの図を見ると、最後に追加された数値がリストの最初に表示されていることがわかります。したがって、最初のノードから順番にリストを印刷すると、数値は逆順に表示されます。
次の方法で、リストを正しい順序で印刷できます。
// Print nodes in a linked list with a while loop
#include
#include
#include
typedef struct node
{
int number;
struct node *next;
} node;
int main(void)
{
// Memory for numbers
node *list = NULL;
// Build list
for (int i = 0; i 3; i++)
{
// Allocate node for number
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = get_int("Number: ");
n->next = NULL;
// Prepend node to list
n->next = list;
list = n;
}
// Print numbers
node *ptr = list;
while (ptr != NULL)
{
printf("%i\n", ptr->number);
ptr = ptr->next;
}
return 0;
}
node *ptr = listが、listが指している場所と同じ場所を指す一時的な変数を作成していることに注目してください。whileはptrが指すノードの内容を印刷し、その後ptrを更新してリスト内の*次（next）*のノードを指すようにします。
この例では、リストの先頭に挿入するのにごくわずかな手順しかかからないため、リストへの挿入は常に \(O(1)\) のオーダーになります。
このリストの探索に必要な時間を考えると、最悪の場合、アイテムを見つけるために常にリスト全体を探索する必要があるため、 \(O(n)\) のオーダーになります。リストに新しい要素を追加するための時間計算量は、その要素がどこに追加されるかによって決まります。これは以下の例で示されています。
連結リストは連続したメモリブロックに保存されません。十分なシステムリソースがあれば、好きなだけ大きくすることができます。しかし、欠点は、配列の代わりにリストを追跡するためにより多くのメモリが必要になることです。各要素について、要素の値だけでなく、次のノードへのポインタも保存しなければなりません。さらに、連結リストでは、 \(n\) 番目の要素の場所を見つけるために最初の \(n - 1\) 個の要素を通過する必要があるため、配列のようにインデックスを使ってアクセスすることはできません。このため、上に描かれたリストは線形探索（リニアサーチ）する必要があります。したがって、上記のように構築されたリストでは、二分探索（バイナリサーチ）は不可能です。
さらに、このコードで示されているように、数値をリストの末尾に置くこともできます。
// Appends numbers to a linked list
#include
#include
#include
typedef struct node
{
int number;
struct node *next;
} node;
int main(void)
{
// Memory for numbers
node *list = NULL;
// Build list
for (int i = 0; i 3; i++)
{
// Allocate node for number
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = get_int("Number: ");
n->next = NULL;
// If list is empty
if (list == NULL)
{
// This node is the whole list
list = n;
}
// If list has numbers already
else
{
// Iterate over nodes in list
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
// If at end of list
if (ptr->next == NULL)
{
// Append node
ptr->next = n;
break;
}
}
}
}
// Print numbers
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
printf("%i\n", ptr->number);
}
// Free memory
node *ptr = list;
while (ptr != NULL)
{
node *next = ptr->next;
free(ptr);
ptr = next;
}
return 0;
}
このコードが末尾を見つけるためにどのようにリストを*辿って（walk down）*いるかに注目してください。要素を末尾に追加（アペンド）する場合、最後に追加する前にリスト全体を通過する必要があるため、コードは \(O(n)\) で実行されます。さらに、ptr->nextを追跡するためにnextという一時変数が使用されていることに注目してください。
さらに、アイテムが追加されるたびにリストをソートすることもできます。
// Implements a sorted linked list of numbers
#include
#include
#include
typedef struct node
{
int number;
struct node *next;
} node;
int main(void)
{
// Memory for numbers
node *list = NULL;
// Build list
for (int i = 0; i 3; i++)
{
// Allocate node for number
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = get_int("Number: ");
n->next = NULL;
// If list is empty
if (list == NULL)
{
list = n;
}
// If number belongs at beginning of list
else if (n->number list->number)
{
n->next = list;
list = n;
}
// If number belongs later in list
else
{
// Iterate over nodes in list
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
// If at end of list
if (ptr->next == NULL)
{
// Append node
ptr->next = n;
break;
}
// If in middle of list
if (n->number ptr->next->number)
{
n->next = ptr->next;
ptr->next = n;
break;
}
}
}
}
// Print numbers
for (node *ptr = list; ptr != NULL; ptr = ptr->next)
{
printf("%i\n", ptr->number);
}
// Free memory
node *ptr = list;
while (ptr != NULL)
{
node *next = ptr->next;
free(ptr);
ptr = next;
}
return 0;
}
リストが構築される過程で、どのようにソートされているかに注目してください。この特定の順序で要素を挿入する場合、最悪の場合、現在のすべての要素に目を通す必要があるため、各挿入についてコードは依然として \(O(n)\) で実行されます。
- このコードは複雑に見えるかもしれません。しかし、ポインタと上記の構文を使えば、メモリ内の異なる場所にあるデータを繋ぎ合わせることができるという点に注目してください。
木構造（Trees）
配列は、高速に検索できる連続したメモリを提供します。また、配列は二分探索を行う機会も提供します。
配列と連結リストの長所を組み合わせることはできないでしょうか？
*二分探索木（Binary search trees）*は、データをより効率的に保存し、検索や取得ができるようにするためのもう一つのデータ構造です。
ソートされた一連の数値を想像してみてください。
次に、中央の値が木の頂点（ルート）になると想像してください。その値より小さいものは左側に配置されます。その値より大きいものは右側に配置されます。
ポインタを使用して、メモリの各領域の正しい場所を指し示すようにし、これらのノードを接続できます。
コードでは、これは次のように実装できます。
// Implements a list of numbers as a binary search tree
#include
#include
// Represents a node
typedef struct node
{
int number;
struct node *left;
struct node *right;
}
node;
void free_tree(node *root);
void print_tree(node *root);
int main(void)
{
// Tree of size 0
node *tree = NULL;
// Add number to list
node *n = malloc(sizeof(node));
if (n == NULL)
{
return 1;
}
n->number = 2;
n->left = NULL;
n->right = NULL;
tree = n;
// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
free_tree(tree);
return 1;
}
n->number = 1;
n->left = NULL;
n->right = NULL;
tree->left = n;
// Add number to list
n = malloc(sizeof(node));
if (n == NULL)
{
free_tree(tree);
return 1;
}
n->number = 3;
n->left = NULL;
n->right = NULL;
tree->right = n;
// Print tree
print_tree(tree);
// Free tree
free_tree(tree);
return 0;
}
void free_tree(node *root)
{
if (root == NULL)
{
return;
}
free_tree(root->left);
free_tree(root->right);
free(root);
}
void print_tree(node *root)
{
if (root == NULL)
{
return;
}
print_tree(root->left);
printf("%i\n", root->number);
print_tree(root->right);
}
この探索関数は、treeの場所へ行くことから始まります。そして、再帰を使用してnumberを探索します。free_tree関数は再帰的に木を解放します。print_treeは再帰的に木を印刷します。
上記のような木構造は、配列にはない動的な性質を提供します。望む通りに成長させたり縮小させたりできます。
さらに、この構造は、木が平衡（バランス）している場合、 \(O(\log n)\) の検索時間を提供します。
辞書（Dictionaries）
*辞書（Dictionaries）*もデータ構造の一種です。
- 単語と定義がある実際の書籍形式の辞書のように、辞書には*キー（key）と値（value）*があります。
アルゴリズムの時間計算量における「聖杯」は、 \(O(1)\) または定数時間です。つまり、アクセスが瞬時に行われることが究極の目標です。
- 辞書は、ハッシュ化（hashing）を通じて、このアクセス速度を提供できます。
ハッシュ化とハッシュテーブル（Hashing and Hash Tables）
*ハッシュ化（Hashing）*とは、ある値を受け取り、後でその値へのショートカットとなる値を出力できるというアイデアです。
例えば、「apple」をハッシュ化すると値が
1になり、「berry」をハッシュ化すると2になるとします。したがって、「apple」を見つけるのは、ハッシュアルゴリズムに「apple」がどこに保存されているか尋ねるのと同じくらい簡単です。設計の観点からは理想的ではありませんが、最終的に、すべての「a」で始まるものを一つのバケツに、「b」で始まるものを別のバケツに入れるという、ハッシュされた値を「バケツ分け」する概念は、この概念をどのように使えるかを示しています。ハッシュされた値は、その値を見つけるためのショートカットとして使えます。*ハッシュ関数（hash function）*は、大きな値を小さく予測可能なものに還元するアルゴリズムです。一般的に、この関数はハッシュテーブルに追加したいアイテムを受け取り、そのアイテムが配置されるべき配列のインデックスを表す整数を返します。
ハッシュテーブル（hash table）は、配列と連結リストを組み合わせた素晴らしいものです。コードで実装する場合、ハッシュテーブルはノードへのポインタの配列になります。
ハッシュテーブルは次のようにイメージできます。
これが、アルファベットの各文字が割り当てられた配列であることに注目してください。
次に、配列の各場所で、そこに保存されている各値を追跡するために連結リストが使用されます。
*衝突（Collisions）*とは、ハッシュテーブルに値を追加しようとしたときに、ハッシュされた場所にすでに何かが存在する場合のことです。上記では、衝突した値は単にリストの末尾に追加されます。
ハッシュテーブルとハッシュアルゴリズムをより良くプログラミングすることで、衝突を減らすことができます。上記の改良版を次のようにイメージできます。
次のハッシュアルゴリズムの例を考えてみましょう。
これはコードで次のように実装できます。
#include
unsigned int hash(const char *word)
{
return toupper(word[0]) - 'A';
}
ハッシュ関数が toupper(word[0]) - 'A' の値をどのように返しているかに注目してください。
プログラマである皆さんは、より多くのメモリを使って大きなハッシュテーブルを持ち、検索時間を短縮する可能性を取るか、より少ないメモリを使って検索時間が増える可能性を取るか、という利点について決定を下さなければなりません。
この構造は、 \(O(n)\) の検索時間を提供します。
トライ木（Tries）
*トライ木（Tries）*もデータ構造の一種です。トライ木は、配列の木です。
トライ木は常に定数時間で検索可能です。
- トライ木の欠点の一つは、膨大な量のメモリを消費する傾向があることです。「Toad」という単語を一つ保存するだけで \(26 \times 4 = 104\) 個の
nodeが必要になることに注目してください！
「Toad」は次のように保存されます。
「Tom」は次のように保存されます。
この構造は、 \(O(1)\) の検索時間を提供します。
この構造の欠点は、使用するためにどれだけ多くのリソースが必要かという点です。
まとめ
このレッスンでは、ポインタを使って新しいデータ構造を構築する方法を学びました。具体的には、以下について深く掘り下げました。
データ構造
スタックとキュー
配列のサイズ変更
連結リスト
辞書
トライ木
また次回お会いしましょう！