カテゴリー
Subscribe Now

* You will receive the latest news and updates on your favorite celebrities!

Trending News
Rampsをはじめるきっかけ 

  目次1 日本からの電話2 日本行きを阻む香港政府のコロナ対策3 34歳のふわっとした夢…

Blog Post

米ハーバード大学5週目の講義「データ構造」:検索スピードを優先した場合に発生する代償とは?
Lifestyle, Tech

米ハーバード大学5週目の講義「データ構造」:検索スピードを優先した場合に発生する代償とは? 

営利団体等のビジネスの場では、ROI(Return on Investment)または投資収益率を考えることは普通である。工場などに設備投資をする際に、どのぐらいの収益を生む事業になりうるのかを評価しなければ、その投資をするべきか否かの判断がつかない。「データ構造」の回では、検索スピードを上げるためには、RAMメモリの容量をたくさん使えば良いことを学ぶが、同時に莫大な費用を支払うことに繋がりかねないという現実的な課題も知る。そのバランスはどこが正しいのか?

 

Resizing arrays(配列のサイズを変更する)

前回は、malloc 関数を使ってメモリにスペースを確保することを学んだ。仮に、下の図のように 123 と並んだメモリに対し、追加でデータを加えたい場合、そこに他のデータが格納されている場合「hello, world\0」は、そこのアドレスは使用することができない。

これを解決するための一つの案としては、必要なメモリ分だけ空いている領域を見つけ、そこに移動させれば良い。ただ、これはすべて値をコピー&貼り付けをしないけないので、時間を要してしまう。

 

Data structures(データ構造)

Data structure(データ構造)とは、もう少し複雑な方法でメモリに保存する構造だが、上のような問題を解決してくれる。

データ構造を作るためには、いくつかのツールが必要である。

  • struct カスタマイズされたデータタイプを作る
  • . 構造体の中のプロパティにアクセスする
  • * ポインタで参照されたアドレスにいく
  • -> ポインタで参照されたプロパティにいく

 

Linked Lists(連結リスト)

Linked list(連結リスト)は、連続したメモリ領域ではなく、違う部分に保存することができる。例えば、以下のように、123 を非連続したメモリ領域、0x1230x4560x789 に保存することができる。

ただし、123という連続したデータに戻すためには、次のデータがどこに保存されているのかをコンピュータに教えるために、アドレスを別に保存する必要があり、そのアドレスを保存するためのメモリ領域が追加で必要である。ここにトレードオフが発生する。既存のデータを移動させなくて良い代わりに、更にメモリ領域を取る必要があり、検索スピードは早くなるが、メモリ代を支払うことになる。Google や Twitterなどのサービスに置き換えて考えた場合、データサイズが変わる度にメモリ領域を移動させて、コピ&ペーストをした場合、処理速度にかなり影響を及ぼすことになる。

これを、プログラムで記述すると次のようになる。

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

これを使ってlink というLinked list を作ることができる。要素を追加するためには、まず node 型に malloc 関数を使ってメモリ領域を確保する。また、確保されたメモリ領域に既にデータが入っていないことを確認し(n != NULL)、そこに値を代入する。また、その次に次の値に参照するために、次の値が格納されているアドレスを指定する。これを繰り返す。

// We use sizeof(node) to get the right amount of memory to allocate, and
// malloc returns a pointer that we save as n
node *n = malloc(sizeof(node));
// We want to make sure malloc succeeded in getting memory for us
if (n != NULL)
{
    // This is equivalent to (*n).number, where we first go to the node pointed
    // to by n, and then set the number property. In C, we can also use this
    // arrow notation
    n->number = 1;
    // Then we need to make sure the pointer to the next node in our list
    // isn't a garbage value, but the new node won't point to anything (for now)
    n->next = NULL;
}

リストにデータを追加する場合は、更にメモリ領域を確保する。

n = malloc(sizeof(node));
if (n != NULL)
{
    n->number = 2;
    n->next = NULL;
}

また、ここでポインタの参照先を先頭文字の n に指定する必要がある。

list->next = n;

3つ目の要素を追加するためには、同様に処理し、最後に要素を繋げる必要がある。

n = malloc(sizeof(node));
if (n != NULL)
{
    n->number = 3;
    n->next = NULL;
}
list->next->next = n;

Implementing arrays(配列を導入する)

配列のサイズを変更するプログラムを見てみよう。

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    // Use malloc to allocate enough space for an array with 3 integers
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }
    // Set the values in our array
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;
    // Now if we want to store another value, we can allocate more memory
    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 new number to list of size 4
    tmp[3] = 4;
    // Free original list of size 3
    free(list);
    // Remember new list of size 4
    list = tmp;
    // Print list
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }
    // Free new list
    free(list);
}

既にメモリ領域を確保した値に対しては、realloc 関数を使えば動的に変更できる。

int *tmp = realloc(list, 4 * sizeof(int));

では、変数sは何なのか?実は、文字列が格納されている先頭のアドレスが格納されている。

 

Implementing linked lists(連結リストを導入する)

それでは、これまで学んだことをすべてまとめてコードを書くと、

#include <stdio.h>
#include <stdlib.h>
// Represents a node
typedef struct node
{
    int number;
    struct node *next;
}
node;
int main(void)
{
    // List of size 0. We initialize the value to NULL explicitly, so there's
    // no garbage value for our list variable
    node *list = NULL;
    // Allocate memory for a node, n
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    // Set the value and pointer in our node
    n->number = 1;
    n->next = NULL;
    // Add node n by pointing list to it, since we only have one node so far
    list = n;
    // Allocate memory for another node, and we can reuse our variable n to
    // point to it, since list points to the first node already
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free(list);
        return 1;
    }
    // Set the values in our new node
    n->number = 2;
    n->next = NULL;
    // Update the pointer in our first node to point to the second node
    list->next = n;
    // Allocate memory for a third node
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        // Free both of our other nodes
        free(list->next);
        free(list);
        return 1;
    }
    n->number = 3;
    n->next = NULL;
    // Follow the next pointer of the list to the second node, and update
    // the next pointer there to point to n
    list->next->next = n;
    // Print list using a loop, by using a temporary variable, tmp, to point
    // to list, the first node. Then, every time we go over the loop, we use
    // tmp = tmp->next to update our temporary pointer to the next node. We
    // keep going as long as tmp points to somewhere, stopping when we get to
    // the last node and tmp->next is null.
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }
    // Free list, by using a while loop and a temporary variable to point
    // to the next node before freeing the current one
    while (list != NULL)
    {
        // We point to the next node first
        node *tmp = list->next;
        // Then, we can free the first node
        free(list);
        // Now we can set the list to point to the next node
        list = tmp;
        // If list is null, when there are no nodes left, our while loop will stop
    }
}

仮に、リストの最初に追加をしたい場合は、

// Here, we're inserting a node into the front of the list, so we want its
// next pointer to point to the original list. Then we can change the list to
// point to n.
n->next = list;
list = n;

 

Trees(ツリー)

キレイに並び替えられた配列では、バイナリー探索を使えば、早く探索できた。

ツリー構造は、一つのノードから2つのノードを参照するデータ構造。以下の例では、親ノード(4)より数字が大きい場合は、右側の子ノード(6)へ、小さい場合は、左側の子ノード(2)へ参照する。

このデータ構造は、次のように記述できる。

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

このデータ構造を使ってデータを結合するためには、次のようになる。

// tree is a pointer to a node that is the root of the tree we're searching in.
// number is the value we're trying to find in the tree.
bool search(node *tree, int number)
{
    // First, we make sure that the tree isn't NULL, if we've reached a node
    // on the bottom, or if our tree is entirely empty
    if (tree == NULL)
    {
        return false;
    }
    // If we're looking for a number that's less than the tree's number,
    // search the left side, using the node on the left as the new root
    else if (number < tree->number)
    {
        return search(tree->left, number);
    }
    // Otherwise, search the right side, using the node on the right as the new root
    else if (number > tree->number)
    {
        return search(tree->right, number);
    }
    // Finally, we've found the number we're looking for, so we can return true.
    // We can simplify this to just "else", since there's no other case possible
    else if (number == tree->number)
    {
        return true;
    }
}

 

More data structures: hash table(その他のデータ構造:ハッシュ表)

データ構造の中でおおよそ O(1) で探索できるのが hash table(ハッシュ表)。仮に、iPhoneに入っている電話帳アプリは、アルファベットのAを0、Zを26とインデックス登録し、そのインデックスに1名しか登録がなければ、1発で探索できる可能性がある。

ただし、次のようにHから始まる名前が多い場合は、先頭文字だけ参照していては、階層が深くなってしまって探索に時間がかかってしまうので、最初の2文字だったり、3文字をインデックスして参照することで探索を早くできる。一方で、これはメモリ領域をさらに使用することを意味する。

Trie(発音はTry、意味はRetrieval)構造とは、配列を使用したツリー構造を意味する。すべてのノードに配列のAからZまでがあり、それぞれのノードから更にA-Zの配列がポインタで接続されている。これで最も早く探索できるが、コストも高い。

この他にも、Abstract data structures、Queueなどががある。

感想

今週は、コンピュータの性能とそのコストのトレードオフについて学んだ。もちろん、コストをかければ探索スピードは早くなるが、ビジネスの場においてはこれがなかなか難しい。ある予算に対して、それを最大限使うという設計が求められそうだ。

Related posts

コメントを残す

Required fields are marked *