米ハーバード大学4週目の講義「メモリ」：半導体不足を解決する試金石となるか？ 

この問いには、そう簡単に答えることはできない。だが、それを十分に考えさせられる講義だった。あまり効率的ではない探索アルゴリズムを用いた場合はメモリに負荷がかかるだけでなく、検索結果が分かるまでに非常に時間がかかってしまう。では、最適な探索アルゴリズムとは？これを数学的に示しながら解いて行く内容だ。今回もまた面白い内容だった。

Hexadecimal（16進数）

なぜコンピューターサイエンスに携わる人達は、人間に馴染みのある10進数ではなく、メモリは16進数を使うのか？それはメモリと相性が良いからである。

16進数は、0−9のあとは、アルファベットの大文字A-Fが数字の10−15を表す。仮に、次のような2桁の16進数があるとすると、16の位は0で1の位がAなので、10進数の15となる。

16^1 16^0
   0    A

では、16進数の10 は、10進数では16となる。

16^1 16^0
   1    0

そして2桁で表せる最大値はFF、または16^1 * 15 + 16^0 * 15 = 240 + 15 = 255は、8ビットで表せる最大値となり、2桁の16進数は1バイトと同じなので、メモリでは16進数を用いられる。そして、10進数と混合しないように、16進数を表すときは、最初に0x をつけることになっている。例えば、0xFF は次のようになる。

Illustrator（イラストレーター）などを使ってRGBを調整するときも16進数が使われている。RGBの3色それぞれに255ビットずつを用いてそれを組み合わせて表現する。

#000000 は、RGBすべてが0なので、黒。

その反対の最大値 #FFFFFF は、RGBすべてが FF なので、白。

#FF0000 は、RGBすべてのRが最大値、Gは0、Bは0なので、赤。

#00FF00 は、RGBすべてのGが最大値、Rは0、Bは0なので、緑。

#0000FF は、RGBすべてのBが最大値、Rは0、Gは0なので、青。

Addresses（アドレス）

地球上に住所が割り当てられていて、そこに手紙や荷物を送れるのと同じように、コンピューターサイエンスの世界でも同様に住所＝アドレスが存在する。そのアドレスも、変数とは別にメモリに格納されていて容量を使用することになる。C言語ではそれを操ることも可能で、アドレスを表現するときは、& を使い、&で出力でき、printf の中ではプレースホルダーとして%p を使う。 それに対して、* は、アドレスに行くこと（リンクとして繋ぐイメージ）を指示する。

よって次のプログラムでは、0x7ffdf27c42cc などのアドレスが返される。

#include <stdio.h>
int main(void)
{
    int n = 50;
    printf("%p\n", &n);
}

Pointers（ポインター）

ポインター変数（*）は、アドレスを保存できる。

#include <stdio.h>
int main(void)
{
   int n = 50;
   int *p = &n;
   printf("%p\n", p);
}

変数nには50が代入されていて、それは0x123というアドレスに保存されているとする。変数pには、n（=50）が保存されているアドレス 0x123 が格納されている。pは（アドレス）、8バイトを使うので下の図でも8つの四角を専有している。

Strings（文字列）

string s = "HI!"; と宣言した変数は、一文字ずつメモリに格納される。そして、s[0]、s[1]、s[2]、s[3]と、それぞれ個別にアクセスすることもできる。

各配列は、メモリのどこかのアドレスに保存されているので、次のようになる。配列は人間が分かりやすく理解するためにアドレスを一時的に置き換えられた構文と捉えることができる。

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

Pointer arithmetic（ポインタの算術演算）

ポインターを使えば、Stringを使わなくてもChar型で文字列を出力することができる。そして、その文字列は連続したアドレスに格納していることが分かる。CS50では、String型が用意されていたが、実際のC言語環境では存在していないので、String型を実現しようとしたらchar *s と指定する。

#include <stdio.h>
int main(void)
{
    char *s = "HI!";
    printf("%cn", s[0]);
    printf("%cn", s[1]);
    printf("%cn", s[2]);
}

配列はメモリのある場所（アドレス）に格納されているので、アドレスを使った操作も色々可能。アドレスに1を追加したら次のアドレスにアクセスが可能で、どの値を参照することもできる。よって、プログラムを間違えて自分が意図していないアドレスにアクセスした場合は、そこにある値を書き換える可能性があり危険で、注意が必要だ。

#include <stdio.h>
int main(void)
{
    char *s = "HI!";
    printf("%cn", *s);
    printf("%cn", *(s+1));
    printf("%cn", *(s+2));
}

Compare and copy（比較とコピー）

次に、ユーザから2つの文字列の入力を求めるプログラムを実行した場合、仮に同じ文字列を入力した場合は、”Same”となるはずだが、結果は、”Different”が出力される。これは、文字列ではなく、アドレスを比較しているからである。

#include <cs50.h>
#include <stdio.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = get_string("t: ");
    if (s == t)
    {
        printf("Samen");
    }
    else
    {
        printf("Differentn");
    }
}

ユーザーに文字列の入力を求め、その文字列をSに格納、かつTにコピーし、Tの先頭文字を大文字に変更する場合、以下のプログラムで良さそうだが…

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = s;
    t[0] = toupper(t[0]);
    printf("s: %sn", s);
    printf("t: %sn", t);
}

結果は、S も T も先頭文字が大文字に変換されてしまう。それは、両方とも同じアドレスを指しているから。これを解決するには、for 文を使ってコピーする必要がある。

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = malloc(strlen(s) + 1);
    for (int i = 0, n = strlen(s); i < n + 1; i++)
    {
        t[i] = s[i];
    }
    t[0] = toupper(t[0]);
    printf("s: %sn", s);
    printf("t: %sn", t);
}

malloc は、必要な数のメモリだけ配分する関数である。malloc(strlen(s) + 1) の + 1 は、文字列の最後の付随している Null 文字を含める必要があるため。

ユーザーが何も入力しなかった場合などのエラーを防ぐために、エラー処理をしてあげる尚良し。最後に free 関数を使って使用したメモリを解放することを忘れずに。

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = malloc(strlen(s) + 1);
    if (t == NULL)
    {
        return 1;
    }
    for (int i = 0, n = strlen(s); i < n + 1; i++)
    {
        t[i] = s[i];
    }
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }
    printf("s: %sn", s);
    printf("t: %sn", t);
    free(t);
}

Valgrind（ヴァルグリンド）

valgrindは、メモリリークがあったかどうかを確認するためのコマンドライン。メモリリークとは、コンピューターがメモリ不足の状態に陥ることを意味する。仮に次のようなプログラムがあった場合、コンパイルはされるが、メモリリークが発生している状態である。

malloc(3) を使って、3文字しかメモリを用意していないのに、実際は4文字分を代入している。よって、正しいプログラムは、以下のようになる。

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
    char *s = malloc(4);
    s[0] = 'H';
    s[1] = 'I';
    s[2] = '!';
    s[3] = '';
    printf("%sn", s);
    free(s);
}

Garbage values（ごみ値）

次のプログラムは、int *x; int *y; のポインタを使って整数型へ参照はしているが、値は指定（初期化）していない。よって。たまたまそのアドレスに格納されていた値（Garbage values）によって誤作動を起こす可能性があるというのがこの章の説明。初期化を忘れないように。

int main(void)
{
    int *x;
    int *y;
    x = malloc(sizeof(int));
    *x = 42;
    *y = 13;
    y = x;
    *y = 13;
}

Swap（入れ替え）

2つの整数を入れ替えるプログラムを考える。もし、2つのワイングラスに違う銘柄のワインが注がれていた場合は、人間であれば簡単に位置を入れ替えることができるが、コンピューターではそう単純にはいかない。次に思いつくのは、3つ目のワイングラスを用意して、入れ替えることができるだろう。swap 関数を使って実行しようとしても、うまくいかない。

#include <stdio.h>
void swap(int a, int b);
int main(void)
{
    int x = 1;
    int y = 2;
    printf("x is %i, y is %in", x, y);
    swap(x, y);
    printf("x is %i, y is %in", x, y);
}
void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

Memory layout（メモリ配列）

メモリに保存される値は、適当な場所が選ばれているわけではなく、いくつかの領域に分けられている。まず machine code は、1 と 0 のバイナリーに置き換えられたコンパイル後のマシン言語が保存されている場所。これがメモリの一番上に位置している。次が、globals で、グローバル変数を宣言した変数を保存する場所。3番目の heapは、malloc 関数を使って、メモリスペースを確保をする領域。一番下のstackは、main 関数等の中に入っているLocal vairables（ローカル変数）が格納されている。

よって、swap 関数を機能させるためには、x と y のアドレス（&x、&y）を渡せば良い。そして、そのアドレスへ行くためにポインタを int *a int *b と記述すれば良い。

#include <stdio.h>
void swap(int *a, int *b);
int main(void)
{
    int x = 1;
    int y = 2;
    printf("x is %i, y is %in", x, y);
    swap(&x, &y);
    printf("x is %i, y is %in", x, y);
}
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

scanf

今までCS50で予め用意されていた get_int ではなく、C言語に用意されている scanf を使用すれば、整数の入力を指示できる。

#include <stdio.h>
int main(void)
{
    int x;
    printf("x: ");
    scanf("%i", &x);
    printf("x: %in", x);
}

同様に、文字列も可能だ。

#include <stdio.h>
int main(void)
{
    char *s;
    printf("s: ");
    scanf("%s", s);
    printf("s: %sn", s);
}

Files（ファイル）

ポインタを使えば、ファイルを開くことも可能になる。

#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
    FILE *file = fopen("phonebook.csv", "a");
    if (file == NULL)
    {
        return 1;
    }
    char *name = get_string("Name: ");
    char *number = get_string("Number: ");
    fprintf(file, "%s,%sn", name, number);
    fclose(file);
}

fopen 関数は、ファイルを開く指示ができる関数で、FILE へのポインタを返す。fprintf 関数を使えば、書き出しができ、fclose 関数は、ファイルを閉じることができる。

Graphics（グラフィックス）

ファイルは、Excel などの CSV ファイルだけでなく、画像ファイルや動画ファイルを操作することも可能。

次のプログラムは、ファイルの先頭3バイトを見れば、JPEG ファイルかが分かる。

#include <stdint.h>
#include <stdio.h>
typedef uint8_t BYTE;
int main(int argc, char *argv[])
{
    // Check usage
    if (argc != 2)
    {
        return 1;
    }
    // Open file
    FILE *file = fopen(argv[1], "r");
    if (!file)
    {
        return 1;
    }
    // Read first three bytes
    BYTE bytes[3];
    fread(bytes, sizeof(BYTE), 3, file);
    // Check first three bytes
    if (bytes[0] == 0xff && bytes[1] == 0xd8 && bytes[2] == 0xff)
    {
        printf("Mayben");
    }
    else
    {
        printf("Non");
    }
    // Close file
    fclose(file);
}

感想

今週は、プログラミングの中でも初心者が躓くと言われているポインタを学んだが、非常に噛み砕きながら説明されていて、ポインタに苦手意識がある人でも理解できるのではないかと感じた。実際に、自分も大学時代にはよく分かっていなかった気もするが、今回きちんと理解できた気がする。この章だけでも動画を見る価値があるのではないだろうか？