CS50 Lecture4 Memory
前回はアルゴリズムについて学んだが、今回はアルゴリズムをより強力にする計算機に焦点を当てる。
16進数
01,02,03,04,05,06,07,08,09,0A,0B,0C,0D,0E,0F,10(16),11(17)....となる
16(の位)*1 + 1(の位)*0 = 16
また、
色を表すRGBにおいて
ただの48,49,21だと、0~9を使っているので、10真数なのか16進数なのかわからない。
そこで、0xを数字の前につけて表すのが慣例となっている。
Photoshopなどでこのようなパレットが出てくる
色は16進数で表される。
赤でも緑でも青でもない場合、#000000(黒)で、光の波長が全くない場合。
このカラーコードを最高値にすると、#FFFFFF(白)で、赤も緑も青もたくさんあるということ。
#FF0000・・・赤
#00FF00・・・緑
#0000FF・・・青
となる
記号の意味
&(アンパーサンド)・・・C言語において、任意の変数名の前に&を一つつけるだけでこの変数がどのアドレスに格納されているかがわかる(アドレスを確認する)
*(アスタリスク)(間接参照演算子)・・・C言語において一つつけると実際のプログラムに対して特定のメモリアドレスの内部を調べるように指示できる。次のアドレスに行けという意味。(そのアドレスを確認する)また、変数の宣言にも使われる。
一方が他方のプログラムを元に戻す。
# include <stdio.h>
int main(void)
{
int n = 50;
//アドレスをプリントする時は、%p(ポインタのp)を使う
printf("%p\n", &n);
}
//結果: 0x7ffcfdfabcbc
# include <stdio.h>
int main(void)
{
int n = 50;
printf("%i\n", *&n);
}
//結果: 50
*&nとすることで、&演算子の効果を取り消し、nのアドレスにいけということになる。
しかしこれは無意味な演習である。なぜなら、nの中身を知りたければ普通にnを出力すれば良いから。
ポインタ
他のアドレスの値を格納する変数
# include <stdio.h>
int main(void)
{
//nに50を代入
int n = 50;
//nのアドレスを一時的にpに格納(50を入れてるわけではない)
//int *p = &n;というのは正しくない(コンパイルできない)
int *p = &n;
printf("%p\n", &p);
}
//結果: 0x7ffc98fbfae0
nのアドレスを一時的に変数に格納してプリントアウトしている
nに入っている50は、0x123というアドレスでメモリのどこかに格納されている。
しかし、pは、変数そのもの。しかし、変数であることに変わりはないので、メモリのどこかに格納されている。
pはあえて大きめに占有している。
なぜなら最近のポインタは8byteを占める傾向がある。
実際にpには何が格納されているのか？
→アドレス(0x123という数字)を格納しているにすぎない。
もし通りにこのようなメールボックスがあるとすれば、その中になんでも入れることができる。
バーチャルでも同じように、p(メールボックス)にはアドレスでも文字でも数字でもなんでも入れることができる。
ブライアンも、自分のメールボックスを持っていて、それは固有のアドレスを持っている。
ラベルはNで、アドレスは0x123
デイビッドのpというポストに0x123という数字があれば、それを手がかりに、ブライアンのNというポストをみることができる。
ブライアンのポストには50という数字が入っている。
s = “HI!”;
sにHI!が格納されていたとすれば、一つ一つの文字にこのようにアクセスすることができる
それぞれの文字のアドレスが図のようなものだったとすると、sには、文字列の一番最初のアドレスと考えてみる。
文字列は、最後に\0がついてるので、文字列の最初のアドレスさえわかれば、あとは\0まで取得すればいいから。
HI!のアドレスを表示してみる。
# include <stdio.h>
# include <cs50.h>
int main(void)
{
string s = "HI!";
//上記のようにいちいちpで入れ替えたり&や*を使わなくてもメモリ上でその文字列がどこから始まっているかのアドレスを出力できる
// int *p = &s
printf("%p\n", s);
}
//結果: 0x402004
# include <stdio.h>
# include <cs50.h>
int main(void)
{
string s = "HI!";
// int *p = &s
// printf("%p\n", s);
printf("%p\n", &s[0]);
printf("%p\n", &s[1]);
printf("%p\n", &s[1]);
}
//0x402004(Hのアドレス)
//0x402005(Iのアドレス)
//0x402005(!のアドレス)
アドレスを抽象化し、sをただのポインタ、つまりコンピューターのどこかにある文字のアドレスとして捉える。
\0が8つの0ビットして表されることを知っていれば、最後までたどり着くことができる。
charはintと同じように文字のアドレスを表すもの
char *s = "HI!";
char * は文字列を指すポインタ変数になる
ポインタ演算子
# include <stdio.h>
int main(void)
{
char *s = "HI!";
printf("%c\n", *s);
}
//結果: H
char * はポインタであるはずなのに、Hが出るのは、*はそのアドレスに行くという機能もあるから
# include <stdio.h>
int main(void)
{
char *s = "HI!";
printf("%c\n", *s);
printf("%c\n", *(s+1));
}
//H
//I
ちなみに、s+1とすると、Hの隣に格納されている、Iにアクセスできる
ポインタに対して簡単 な演算ができる
下記は整数を比較するコード
# include <stdio.h>
# include <cs50.h>
int main(void)
{
int i = get_int("i: ");
int j = get_int("j: ");
if (i == j)
{
printf("Same\n");
}
else
{
printf("Different\n");
}
}
文字列を比較しようとしているコード
# include <stdio.h>
# include <cs50.h>
int main(void)
{
char *s = get_string("s: ");
char *t = get_string("t: ");
if (s == t)
{
printf("Same\n");
}
else
{
printf("Different\n");
}
}
s: David
t: David
//Different
何をやってもDifferentになるのは、文字列ではなく、文字列が格納されているアドレスを比較しているから。
# include <stdio.h>
# include <string.h>
# include <cs50.h>
int main(void)
{
char *s = get_string("s: ");
char *t = get_string("t: ");
if (strcmp(s, t) == 0)
{
printf("Same\n");
}
else
{
printf("Different\n");
}
}
s: David
t: David
//Same
# include <stdio.h>
# include <string.h>
# include <cs50.h>
int main(void)
{
//sのアドレスを格納
char *s = get_string("s: ");
//sのアドレスをtに格納
char *t = s;
//コピーされた最初の文字だけを大文字にする
t[0] = toupper(t[0]);
printf("s: %s\n", s);
printf("t: %s\n", t);
}
s: hi!
//s: Hi!
//t: Hi!
sもtも大文字になる...
sもtも全く同じポインタが入っており、参照元は同じだから
t[0]で、tの１文字目に移動することは、s[0]で、sの1文字目に移動することと同じだから
sもtも大文字になってしまった。
上記のプログラムの変形版を作ってみる。
プログラムを変更して、sという文字列を取得するように書いてみる。
しかし、どこかにそも文字列をコピーする必要がある。
そこで、文字列をコピーするプロセスのもう一つのステップとして、メモリを追加しなければならない。
「HI!\0」があると、tの場所を確保するため4byteくれとコードで書かなければならない。
malloc
メモリの割り当てをいみする。文字列tを作りたい場合使用できる
入力として、何 バイトのメモリを要求したいのか指定する数字を受けとる。
「HI!\0」なら4byteなのでmalloc(4)と書く
が、もう少しエレガントに書くとすると、malloc(strlen(s) + 1)と書くことができる
(なぜ+1かというと、文字列はHI!の3文字+\0(ヌル文字)(1byte)で構成されているから)
# include <stdio.h>
# include <string.h>
# include <cs50.h>
# include <ctype.h>
# include <stdlib.h>
int main(void)
{
//sのアドレスを格納
char *s = get_string("s: ");
//メモリを割り当てる
char *t = malloc(strlen(s) + 1);
//nの文字列の大きさ分ではなく i < n + 1(\0までコピーしなければならないから)
//i < n + 1を、i <= nと書いた方が合理的
for(int i = 0, n = strlen(s); i <= n; i++)
{
t[i] = s[i];
//tにiを加えたアドレスに行きたい時
//角括弧表記はポインタ演算と同じ
//だけど読みにくい
*(t+i) = *(s+i);
}
if(strlen(t) > 0)
{
t[0] = toupper(t[0]);
}
//tの最初の文字に移動してそれを大文字にする、といったこともできるけど、読みにくい
*t[0] = toupper(t[0]);
printf("s: %s\n", s);
printf("t: %s\n", t);
}
s: hi!
//s: hi!
//t: Hi!
新たにsを別の場所へコピーしたものを参照したtのみが大文字に変わった。
mallocはget_stringと同じように、メモリの塊の最初のバイトのアドレスを返してくれるが、時には上手くいかないことがあり、macがフリーズしたり再起動したりすることがある。それはは大体、メモリのエラーであることが多い。
なので、実際には次のようなエラーチェックをする必要がある。t == NULLの部分
# include <stdio.h>
# include <string.h>
# include <cs50.h>
# include <ctype.h>
# include <stdlib.h>
int main(void)
{
//sのアドレスを格納
char *s = get_string("s: ");
//メモリを割り当てる
char *t = malloc(strlen(s) + 1);
//nの文字列の大きさ分ではなく i < n + 1(\0までコピーしなければならないから)
//i < n + 1を、i <= nと書いた方が合理的
for(int i = 0, n = strlen(s); i <= n; i++)
//nullはポインタがないということで、\0とは違う
if(t == NULL)
{
//プログラムを終了
return 1;
}
{
t[i] = s[i];
//tにiを加えたアドレスに行きたい時
//角括弧表記はポインタ演算と同じ
//だけど読みにくい
*(t+i) = *(s+i);
}
//for文を使わなくてsdlibに、文字列をコピーする関数がある
//第一引数がコピー元、第二引数がコピー先
strcpy(t,s);
if(strlen(t) > 0)
{
t[0] = toupper(t[0]);
}
//tの最初の文字に移動してそれを大文字にする、といったこともできるけど、読みにくい
*t[0] = toupper(t[0]);
printf("s: %s\n", s);
printf("t: %s\n", t);
}
mallocを使ってメモリを確保し、最終的にそれを返す責任はプログラマにある。
要求ばかりして確保だけしていくとメモリ不足になる。
メモリを使い終わったら、開放しなければならない。
free
mallocの出力を入力とする = mallocの出力は、割り当てられたアドレス
=メモリの最初のバイトのアドレス
# include <stdio.h>
# include <stdlib.h>
int main(void)
{
char *s = malloc(4);
s[0] = 'H';
s[1] = 'I';
s[2] = '!';
s[3] = '\0';
printf("%s\n", s);
//ここでfree(アドレス)追加すればメモリが開放される
free(s);
}
valgrind ./filename
// All heap blocks were freed -- no leaks are possible
# include <stdio.h>
# include <stdlib.h>
int main(void)
{
//intのアドレスを格納できるxという変数を与えなさいという意味
int *x;
int *y;
x = malloc(sizeof(int));
//xの住所にいって42ということ
*x = 42;
//yの住所にいって13ということ
*y = 13;
y = x;
*y = 13;
}
上記のコードはエラーになる。
その原因は下記。
int *x;
int *y;
x,yは何もさしておらず、設定するのは別のステップ
x = malloc(sizeof(int));
xの分のメモリを確保
*x = 42;
xの指し示す場所に42を格納する
*y = 13;
次に、*yに13を入れようとすると、弾かれる（エラーになる）
なぜなら、まだyのためのメモリ(白い枠)を確保していないから。
一旦yも、xと同じ場所を参照するように変更する
そして、
*y = 13;
yの参照先に13を入れようとすると、
x の参照先も13に上書きされてしまった。
下記のように、scoreに何も代入されていないものを出力しようとすると、謎の数字が出てくる。
これは初期化されていないから。
# include <stdio.h>
# include <stdlib.h>
int main(void)
{
int scores[3];
for(int i = 0; i < 3; i++)
{
printf("%i\n", scores[i]);
}
}
//2114144848
//32766
//0
しかし、例外もあり、グローバル変数は、設定しなければ、慣習的に０またはnullに初期化される。
しかし、変数は 常に初期化するべき。
二つの液体の中身を入れ替えるとすると、グラスが二つでは足りない。
（片方を片方のグラスに入れようとすると混ざってしまうから）
青い液体を赤い液体が入っているグラスに入れるために、赤いグラスを別のグラスに一時的に入れ替えて、場所を確保する必要がある。
赤い液体が入っていたグラスに、青い液体を注ぐことができる。
最後に、もともと青い液体が入っていたグラスに、赤い液体を戻す。
グラスの位置を入れ替えたわけではないが、液体の中身を入れ替えることができた。
上記の話のように、入れ替えるには一時的な余分な場所が必要。
# include <stdio.h>
void swap(int a, int b)；
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, u is %i\n", x, y);
//x,yを入れ替える
swap(x, y);
printf("x is %i, u is %i\n", x, y);
}
void swap(int a, int b)
{
//一時的にaを置いていく
int tmp = a;
a = b;
b = tmp;
}
machine code・・・0,1のコード。Linuxでプログラムを実行したり、MacOSやWindowsのアイコンをダブルクリックしたりすると、ハードドライブに保存されているプログラムの０、1がここに読み込まれ、マシンコードと呼ばれる０と１のコードが生成される。メモリの一番上の部分に読み込まれる。
malloc・・・machine codeの下にあり、予備のメモリを確保するために使用する大きなメモリの塊。
heep・・・mallocの下にあり、mallocを呼び出す度に、マシンコードやグローバル変数の下にある、この領域のメモリの塊のアドレスが与えられる。
ヒープがここから下に向かって存在すると考えられているのに対し、スタックがここから上に向かって存在すると考えられている。
mallocを呼んで、メモリを要求すると、それはheepに割り当てられる。
関数を呼び出した場合、関数はヒープ空間ではなく、スタック空間と呼ばれるものを使用する。
例えば、main関数、swap関数を使用すると、下記の図のようになる
main関数で、二つのローカル変数xとyを持ちたい場合
上記のmain関数では、int(intはsize:4byte)変数x,yがあった。
x,yをそれぞれ、1,2で初期化する。
次にswap関数を呼ぶ。
それぞれにa,bという整数を用意する。また、グラスの中身を入れ替える際に使用したような余分なグラスと同じ役割のtmpという場所を確保する。
余分なグラスを用いて、中身を変えたように、swap関数でaとbの中身を入れ替えるために、
まずtmpの中身をaと同じにする。a = 1, tmp = 1
次にaとbを同じにする。a = 2, b = 2
次にはbをtmpと同じにする。tmp = 1, b = 1
swapはaとbの値を入れ替えている限りに多いては正しい。
しかし、swapが戻った瞬間（関数の処理が終わった瞬間）これらはゴミのような値になってしまう。(swapの中のa,b,tmp)
引数を取るコードを書いたり、ある関数から別の関数に引数を渡したりすると、それらの引数はある関数から別の関数にコピーされる。
確かに、xとyはaとbにコピーされる。
しかし、swapの文脈で正しくスワップされているだけで、元の値には触れていない。
だから、基本的にはx、y の値を実際に変更するような形でswapを再実装する必要がある。
x,yのコピーを変更するのではなく、x,yを変更できるようにするにはどうすれば良いか？
→ポインタを使用する
→mainからswapへの処理でx,yを文字通り渡すのではなく、xのアドレスとyのアドレスを渡さなければならない。
main関数のxの4byte先にあるのが、0x123,yの4byte先にあるのが0x127かもしれない。
ポインタは8bteであり、swap関数のaやbを整数ではなく、整数へのポインタ、つまりint *変数として宣言すれば、これをaと呼ぶことができる。xのアドレス、0x123をaに入れ、yのアドレス0x127をbに入れる。
変数tmpにはアドレスaにあるものを格納する(tmp = 1)
swapするために、aのアドレス(0x123)にあるもの(1)をbのアドレス(0x127)にあるもの(2)に変更する。
最後に、bではなくbがさすアドレス(y)にいき、tmpの値(1)に変更する。
単純に値のコピーを取得するのではなく、swap
がこれらのアドレスに行くようにする(引数に&をつけてアドレスを渡す)ことで、x,yのスワップを実現している。
xとyを入れ替えるコード
# include <stdio.h>
void swap(int *a, int *b);
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, u is %i\n", x, y);
//x,yを入れ替える
//&はこの変数がどのアドレスに格納されてるかわかる
swap(&x, &y);
printf("x is %i, u is %i\n", x, y);
}
//引数のaやbはその変数のポインタを取得している
void swap(int *a, int *b)
{
//一時的にaのアドレス(xのアドレス)をtmpに置く
int tmp = *a;
//aに行って(a*)bのアドレス(b*)を入れる
*a = *b;
*b = tmp;
}
マリオのコード
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int h)
{
//高さがなければリターンする
if(h ==0)
{
return;
}
// 自分の関数を今の高さの一つ小さい高さで呼び出す
draw(h - 1);
for(int i = 1 ; i <= h; i++)
{
printf("#");
}
printf("\n");
}
bubber overflow
・・・配列を割り当てた時びその配列の境界を超えてしまうこと。あるいはmallocを使っていて、割り当てたメモリの塊の境界を超えてしまう場合。
Youtubeやzoom、netflixの文脈でのバッファとは、mallocなどで取得したメモリの塊で、動画を構成するバイトで満たされている。
数値を受け取ってそれを出力するコード
#include <stdio.h>
int main(void)
{
int x;
printf("x: ");
//ユーザーから入力を受け取る
//引数にはアドレスを渡さなければならない
scanf("%i", &x);
printf("x: %i\n", x);
}
文字を受け取って出力する
#include <stdio.h>
int main(void)
{
//char *x; と宣言すると、初期化されてないのでエラーになる
//char *s = mallo(4);でもおkだけどfreeでメモリを解放しなければならない
char s[4];
printf("x: ");
//ユーザーから入力を受け取る
//引数には*xはアドレスであることが明確なので&は不要
scanf("%s", x);
printf("s: %s\n", s);
}
mallocはheepメモリを使う
→freeを使わないといけない
しかし、スタックを使う場合はfreeを使う必要はない。(自動的に管理されているから)
ファイルを開くにはかき3種類
- 読み取り
- 書き込み
- 追加
下記で名前と電話番号ダウンロードできる
#include <stdio.h>
#include <cs50.h>
#include <string.h>
int main(void)
{
//fileのデータ型
//fileへのポインタ、つまりファイルのアドレス
FILE *file = fopen("phonebook.csv", "a");
if(file == NULL)
{
return 1;
}
char *name = get_string("Name:");
char *number = get_string("Number:");
//ファイルに印刷する
fprintf(file, "%s,%s\n", name, number);
fclose(file);
}
ビットマップファイル、ビットのマップ、ビットのグリッドがあれば、ビットは0,1になる。
typedef unit8_t BYTE;
C言語ではバイトとは何かという共通の定義はなくバイトとはビットのこと。
バイトを作成する最も簡単な方法は文字列を定義したように自分で定義すること。
Discussion