ハーバード大学 コンピュータ・サイエンス講座 受講メモ CS50 2020 Week4 Memory
CS50 2020 Week4 Memory
いよいよ難しくなってきたけど、やっぱり面白い。
もうちょっと踏み込んだらハッカーになれてしまうんじゃないかと妄想が膨らんでしまう。
しかし、画面に出てる学生の受講者、むっちゃ減ってない…？最初もっと大勢いたと思うけど、結構脱落していくんだろうか。。
俺も都度試験とかあったらついてけてないかも…
自由受講で良かった…
これまではCS50ライブラリという補助輪を付けてC言語を扱ってきた
ライブラリを使用するには、もちろんcs50.hを選択してコードの先頭にインクルードする
clangの仕組みを考えると、-lcs50を使ってコードをリンクしていたことになる
先週はアルゴリズムに焦点を当てたが、今日はアルゴリズムをより強力に実装するために、現在使用しているコンピュータに焦点を当てる
そして、補助輪を外して、コンピュータの覆いの下で実際に何が起こっているのかを見ていく
先に進むために理解しなければならないこと、覆いの下で起こっていることはそれほど多くはなく、もっと面白くて洗練された、もっと楽しい問題を解き始めることができる
必要なのはいくつかの追加の構成要素だけ
そこで、今日はまず数の数え方を学び直してみましょう
コンピュータのメモリ
メモリにあるすべてのバイトを番号で呼び出せる
コンピュータのメモリについて語るとき、コンピュータやコンピュータ科学者、プログラマーは、実は10進法を使わない傾向にある
⇒16進法を使う
16種類の数字を使う基数システム
0～9までは10進法と同じ⇒そこから後はアルファベットを使い始めるA～F
0から数え始めるのが特徴
10以降の数字も一桁で表現できるのが利点
0からFまでの16の数字をbase-16と呼ぶ
16の1乗の位 16の0乗の位
↓
01 02 03 04…0A 0B 0C…0F ⇒10 ←10に見えるが、16進法ではこれが16
コンピュータの世界でも、メモリの世界でも、そしてもうすぐ扱うファイルの世界でも、16進法を認識して使えることはとてもありふれたことになるでしょう
FF ←(16×15) + (1×15) = 240+15 = 255
列とその中にある値を掛け合わせるという小学校の算数のようなもので、このFはそれぞれ15を一桁で表現している
数週間前に2進法の話をしたとき、255は偶然にもここで見たパターンで、2進法を使った8つの1ビットを表していた
11111111
コンピュータ科学者が16進法を好む理由は、8ビットの中に、左に4つ、右に4つというように、実際には2つのペアがあるから
16進法では16個の可能な値を表現できるので、一度に4ビットを表現するのに最適なシステム
つまり、コンピュータの世界では4ビット単位で話したい時には代わりに16進法を使うのが素晴らしく便利
なぜなら、16進法の1桁は2進法の4桁の0と1に相当するから
0000～1111
2×2×2×2 = 16
16進法を表す時には頭に「0x」を付ける
0x48
RGBで色を表現するときにも16進法が使われる
photoshopの色のウィンドウの一番下に16進法で色を入力する欄がある
000000⇒黒
FFFFFF⇒白
FF0000⇒赤
00FF00⇒緑
0000FF⇒青
16進法をいちいち10進法に直して考える必要は無い
コンピュータのメモリに実際に何が保存されているのかを考えてみよう
数字を表すnという変数を宣言し、int型とする
そして、その変数に値を割り当てる
int n = 50;
↑実際に何かをするには、これをmainや他のプログラムに入れる必要がある
このようなコードをコンピュータで使うと実際には何が起こるのか？
▼address.c
コンピュータのメモリ上のアドレスで実験してみる
#include <stdio.h>
int main(void)
{
int n = 50;
printf("%i\n",n);
}
実行すると「50」と表示される
今日は、コンピュータのメモリを実際に調べるためのツールをいくつかご紹介します
まずはこのコードをコンピュータのハードウェアの文脈で考えてみましょう
つまり、このようなコードでプログラムを書いている場合、nはコンピュータのメモリのどこかにある必要がある
50はコンピュータのメモリのどこかに置かれる必要がある
整数は通常、少なくともCS50 IDEや最近のシステムでは4バイトになる傾向がある
⇒コンピュータのメモリのどこかに4バイトの入れ物が配置される
しかし、コンピュータのメモリ内には、暗黙のうちに存在するアドレスがある
コードに付けた変数名から、この変数nを参照することができる
確かにこの変数はメモリ上の特定の場所に存在している
どこにあるかはすぐにはわからないが、アドレスは持っているはず←コンピュータのメモリの中にある四角いマスには、0、1、2などの固有の識別子であるアドレスがあるから
C言語ではそのアドレスを実際に見ることができる
⇒プログラムを修正し、新しい構文を少し導入して、コンピュータのメモリの内部を覗き見できるようにしてみましょう
新しい演算子
&(アンパサンド)：アドレスを表す
任意の変数名の前にこの&を付けるだけで、「この変数がどのアドレスに格納されているのか教えてください」とCに伝えることができる
※ブール式で「かつ」を表すのは「&&」
*(アスタリスク)
プログラムに対して、特定のメモリアドレスの内部を調べるように指示することができる
「間接参照演算子」⇒「次のアドレスに行け」という意味
※乗算ではない
#include <stdio.h>
int main(void)
{
int n = 50;
printf("%p\n",&n); ←nの前に「&」を付けてnのアドレスを表示する
アドレスのフォーマットコードは「%p」
}
変数のアドレスをプリントアウトし、それを16進数として解釈するために慣習的に%pを使う
↓実行するとアドレスが表示される
0x7ffe51b9b73c
↑この具体的な数字自体に意味はない
&nではなく、興味本位で*&nをプリントアウトしてみると、この演算子の効果を取り消すことができる
知的な演習として、nに&を前置し、*を使って「そのアドレスに行け」と言えば、単にnそのものを印刷するのと全く同じことになる
フォーマットコードは整数の%iに戻す
⇒実行すると「50」が表示される
このように、一方が他方の効果を元に戻すだけだということを理解していれば、これらを使ってかなり面白いプログラムを作り始めることができる
▼ポインタ
ポインタと呼ばれる特殊な変数を利用してみましょう
%pのpはポインタを意味する
ポインタとは、他の値のアドレスを格納する変数のこと
整数へのポインタ、文字へのポインタ、ブールへのポインタ、その他のデータ型へのポインタがある
ポインタは実際に参照している値の特定の型を参照する
先ほどのコードに変数を一つ導入してみる
int *p
C言語でも最もわかりにくい構文かもしれない
一般的には、*は乗算やアドレスへの移動、さらには変数の宣言に使われるようになっている
int *p = &n
ここでできることはnのアドレスを一時的に変数に格納してプリントアウトすること
#include <stdio.h>
int main(void)
{
int n = 50;
int *p = &n;
printf("%p\n",p);
}
「int *」整数のアドレスを格納しているのであって、整数を格納しているのではない、ということを明確にしている
↓実行するとアドレスが表示される
0x7ffe91388a7c
プログラムの中で起こっていることや、システム上の他のことによって、これらのアドレスは毎回異なる
もう一回りしてnの値をプリントアウトするにはどうすればいいか？
目的がもはやnのアドレスをプリントアウトすることではなく、pを使ってnそのものをプリントアウトすることだとしたら、フォーマットコードを%iに変更して、nをプリントアウトすることになる
←仮にこの問題でnを直接表示したくないとしたら、つまりpを使ってnの値を表示するにはどうすればいいか？＝prinfの第二引数に何を入力すれば良い？
pはアドレス⇒そのアドレスの値を参照するのは*p
printf("%i\n",*p); ⇒ 「50」と表示される
見かけ上、結果は同じなので何も進展していないように見えるが、
この新しいパズルのピースを導入したことで、コンピュータのメモリにある何かのアドレスをプログラムで把握し、実際にそのアドレスに行くことができるようになった
int n = 50;
int *p = &n;整数50を格納した変数nはランダムなアドレスのメモリに配置される
pは厳密には変数そのもので、何か他の物のアドレスを格納する
pも変数であることに変わりはないので、pを宣言すると、実際に何バイトかのメモリを専有することになる
CS50 IDEをはじめとする最近のコンピュータシステムでは、ポインタは8バイトを占める傾向がある
pには何が格納されている？
50を格納している整数nが0x123…の位置にあり、ポインタpにそのアドレスが割り当てられているとすると、それは「この変数pに格納されているのは、16進数で表された0x123…という数字です」と言っているようなもの
正直なところ、人間としてはこの整数nが実際にどのアドレスにあるのか知ったとしても役に立つことはない
そのため、コンピュータ科学者がコンピュータのメモリについて語るとき、このような低レベルの詳細を、実際の数字で語ることはありません。
その代わりに、図式を単純化し、これまでの議論とは関係のないメモリをすべて抽象化して、ただ「pがアドレスを格納していることは知っている」と言う傾向がある
ポインタは矢印で「格納されているnのアドレス」を指し示しているイメージ
抽象化とは、理解する必要があるかもしれないが、必ずしも考え続ける必要のない低レベルの詳細を単純化すること
人間の日常生活でもこれらと同じメカニズムを使っている
例えば家の前の通りやハーバード・サイエンス・センターの地下にメールボックスがあるとすると、少なくとも住宅街ではこのような形をしているでしょう⇒「p」と書かれたポスト
ポストにはハガキでも小包でも、入るものならなんでも入れられる
⇒バーチャルのポインタも同じく、アドレスを含め、文字や整数、その他のものを保存することができる
先生のポストがp、ブライアンのポストがnだとする
ブライアンのポストnのアドレスは0x123
⇒先生のポストpに0x123が入っていれば、それが手がかりになって、先生はブライアンのポストの中を見ることができる
⇒ブライアンのポストには「50」という整数が入っている
人間社会では住所や番地を使って行っていたことを、コンピュータはメモリを使って下位レベルで行っている
次に、個々の整数ではなく、文字列を格納する根本的に異なるデータ型を考えてみましょう
string s = "HI!";
コンピュータのメモリ上ではH I ! \0
個々の文字は下記のようなブラケット表記で扱うことができる
H s[0]
I s[1]
! s[2]
\0 s[3]
文字列をあたかも文字の配列であるかのように扱うには、[]記法を使う
⇒文字列はアドレスを使って操作することもできる
例えば
H 0x123
I 0x124
! 0x125
\0 0x126
これらは意図的に連続したアドレスで、前後に並んでいることに注目
1バイト間隔で並んでいる⇒文字は1バイトだから
これらのアドレス自体は重要ではないが、これらが1バイト間隔で並んでいるという事実は重要。なぜならこれが文字列の定義であり、さらには連続したアドレスに格納される配列の定義でもあるから
sとは何か？⇒"HI!"という文字列⇒コンピュータのメモリのどこかに置かなければならない変数
sは高いレベルの文字列ではなく、低いレベルでの文字列のアドレスであると考えることができる⇒より具体的には文字列の最初の文字のアドレスに過ぎないと考えてみましょう
コンピュータやプログラマーにとって、なぜ文字列を最初のバイトのアドレスという観点から考えるだけで十分なのか？
例えば、どんなに長い文字列であっても、たとえそれが段落全体のテキストであっても、sのような文字列を単に最初のバイトのアドレスと同一であると考えることが、非常に巧妙で十分であるのはなぜでしょうか？
ここまでの数週間で学んだことがつながった
・文字列は前後に並んでいる配列
・すべての文字列は最後に\0(nul文字)で終わる
⇒文字列について考えるときに必要なのは、文字列がどこから始まるか？ということだけで十分
forループやwhileループなど、条件とブール式を使った発見的な手法を使えば、事前に文字列の長さを知ることなく、文字列がどこで終わるかを知ることができるから
文字列については、文字列の最初の文字のアドレスというだけの単純なものだと考えよう、ということ
▼文字列を使ったプログラム
#include <cs50.h>
#include <stdio.h>
int main(void)
{
string s = "HI!";
printf("%s\n",s);
}
「HI!」と表示されるだけ
文字列が実際に置かれているアドレスを表示したい
printf("%s\n",s);
↓%sを%pに変えてみる
printf("%p\n",s);
↓アドレスが表示される
0x402004
文字列を使っていても、%sを%pに変えるだけでメモリ上でその文字列が実際にどこから始まっているのかを知ることができた
1番目の文字のアドレスを表示してみる
printf("%p\n",&s[1]);
これらの演算子は、「この物体のアドレスは何か」というような質問に対して、非常にシンプルな答えを与えてくれる
s[1]の前に&を付ける必要がある
0x402004
0x402005 ←ちゃんと前の文字に並んでいる
#include <cs50.h>
#include <stdio.h>
↓すべての文字のアドレスを表示してみる
int main(void)
{
string s = "HI!";
printf("%p\n",s);
printf("%p\n",&s[1]);
printf("%p\n",&s[2]);
printf("%p\n",&s[3]);
}
↓全部並んでいた！
0x402004
0x402005
0x402006
0x402007
これは&や*演算子によって比較的簡単な操作が可能になったことを示している
s=文字列はコンピュータのメモリのどこかにある文字のアドレスと考えることができる
・文字列は前後に並んでいる
・文字列は最後に\0(nul文字)で終わる
↑この定義によって、それが文字列がどこにあるかを知るためにコンピュータに保存しておく必要のある最小かつ唯一の情報であることがわかる
終端をチェックするためのif条件を設けることができる
⇒ここでCS50ライブラリという補助輪を外す時が来た
これまでずっとCS50ライブラリ、特にcs50.hというファイルではちょっとした教育的な単純化が施されていた
先週、自分でカスタムデータ型を定義したことを思い出してほしい
今までずっと、文字列は存在していて、プログラムの中で使えるものだと主張してきた
文字列はCにも、Pythonにも、JavaScriptにもJavaにもC++にも、その他の多くの言語にも存在する
しかし、文字列は技術的にはCのデータ型としては存在しない！
代わりにより暗号めいた、より低レベルの「char *」として知られている
char *は先ほどのint *と同じように、文字列のアドレスを表すもので、int *がintのアドレスを表すのと同じ
文字列を「文字の並び」、より具体的には「文字の配列」、より具体的には今日のように「最初の文字のアドレス」と考えることに同意してもらえるなら、このポインタという今日の新しい用語を、昔からの馴染みの友人である文字列に適用できることになる
文字列stringはchar *の同義語と言っても良い
cs50ライブラリにはchar *を抽象化、単純化するコードが含まれていた
stringとはカスタムデータ型だった
今日は補助輪を外して、これまでずっと特定のアドレスの文字を操作していたことを明らかにしましょう
前回はカスタマイズ可能な構造体structを学んだ
typedef struct
{
string name;
string number;
}
person;
電話帳のプログラムをより良くするために名前と番号をパッケージしてpersonという一つの構造体を作った
typedefという機能を使って、新しい型を定義することができた
実はstringも構造体だった
↓cs50.hの中にあるコードの一行
typedef char *string;
char *を隠すためにstringというカスタムデータ型を定義していた
&や*を使って、変数のアドレスを取得したり、アドレスに移動したりすることができる
文字列の実際のアドレス、つまり最初の文字のアドレス、そしてそこからプログラム的に最後までの道を見つけることができるのは、nul文字のおかげ
アドレスやポインタを使ってできることがもう一つある
ポインタ演算というもの
数字であるものはすべて、計算することができる
計算は複雑ではないが、ここでは強力な力を発揮する
address.cに戻る
文字列の文字は配列の[]記号で一文字ずつ呼び出せることを再確認
#include <cs50.h>
#include <stdio.h>
int main(void)
{
string s = "HI!";
printf("%c\n",s[0]);
printf("%c\n",s[1]);
printf("%c\n",s[2]);
}
一文字ずつ
H
I
!
と表示される
↑これが文字列データ型である必要がないことに注目
⇒補助輪を外せる＝cs50.hをインクルードする必要はない
#include <stdio.h>
int main(void)
{
char *s = "HI!"; ←stringではなく、char *
printf("%c\n",s[0]);
printf("%c\n",s[1]);
printf("%c\n",s[2]);
}
*は「ここに何かのアドレスがある」ということを意味する
charは文字のデータ型
⇒char *は文字を指すポインタ変数になる
char *は実質string(文字列のデータ型)と全く同じように扱える
↓実行すると
H
I
!
stringを使った時と全く同じことになる
もう一つの方法がある
⇒もし、sが単なるアドレスであることがわかっていれば、この[]表記をなくすことができる
なぜなら、*はポインタを宣言するときに使う新しい記号であるだけでなく、紛らわしいことに、アドレスに行くのに使ったのと同じ記号でもあるから
つまり、sがアドレスを格納している場合、ポインタであることの定義上、*sはそのアドレスに行くことを意味する
さっきの図ではsは0x123から始まるアドレスにある可能性が高いと思われる
s[0]をsにしてみる
↓
ちゃんと一文字目のHが表示された
文字列であるsが技術的には単なるアドレスであることを知っていれば、それを使って計算することができる
s[1]を(s+1)としてみる
↓
H
I
↑ちゃんと二文字目が表示された！
[]を使わずにアドレスだけを使って文字列を扱えた
week2に紹介した[]表記は、技術的には単なるシンタクティク・シュガーでしかなかった
*やアドレスを、よりユーザーフレンドリーな方法で行っているにすぎない
最後のnul文字を表示しようとするとどうなる？
%cで表示しようとすると空白だが、%iで表示すると「0」が表示される
例えば、*(s+10000)を表示しようとすると、「segmentation fault」と表示される
↑良くない。触れるべきではないメモリに触れてしまっている
今回は敢えてこのことについて考える
segmentation faultは、コードのどこかで何か間違ったことをしていること、触ってはいけないところに触ってしまっていることを意味する
二つの文字列を比較するプログラムを書きたいという場合を考えてみる
▼compare.c
ユーザーが入力した二つの文字列の内容を比較するプログラム
↓まずはプログラムの正しさを示すために整数を比較するコードを書いてみる
#include <cs50.h>
#include <stdio.h>
int main(void)
{
int i = get_int("i: ");
int j = get_int("j: ");
if(i == j)
{
printf("Same\n");
}
else
{
printf("Different\n");
}}
※ここでcs50.hをインクルードしているのは単にget_stringやget_intを使うため
iとjが同じだったら「Same」、
iとjが異なったら「Different」と表示される
↓整数ではなく、文字列を比較してみると？
#include <cs50.h>
#include <stdio.h>
int main(void)
{
char *s = get_string("s: ");
char *t = get_string("t: ");
if(s == t)
{
printf("Same");
}
else
{
printf("Different");
}}
⇒同じ文字列を入力しても「Different」になってしまう！
このプログラムのどこに問題がある？
←文字列はアドレスだから比較しても同じにならない
get_stringを呼び出すたびに文字列は異なるアドレスに置かれている
しかし、私たちはこの答えを出す、あるいは自分でこの答えを吟味するためのツールを持っている
単純化するために、sとtそれぞれをまず文字列として表示させる
printf("%s\n",s);
printf("%s\n",t);
↑このフォーマットコードを%sでなく%pにしてみると
0xd8e6b0
0xd8e6f0
↑同じ文字列でも異なるアドレスに配置されていることがわかる
しかしほぼ似通ったアドレスに配置されていることに注目
たまたま同じものを入力したにも関わらず、Cと私のコンピュータは、両方の文字列に同じバイトを使用するような大胆なことはしない
どちらかを変更したいときに柔軟性がないため
コンピュータは非常に単純に、一方をこのメモリの塊に、もう一方をこのメモリの塊に、と入れることになる
二つの文字列はある程度距離が離れたアドレスに配置されているが、実際にどこに置くかはコンピュータの判断に委ねられている
メモリ上では何が起きているのか？
・sというポインタ変数がメモリ上に8バイトで配置される
・「HI!」という文字列がメモリ上の他のどこかに1文字1バイトで連続して配置される
H 0x123
I 0x124
! 0x125
\0 0x126
左のsに右のget_stringの値を代入するとどうなる？
week1で使い始めてからずっと、get_stringは文字列を取得して、それを戻り値として返している
↑どういうこと？
文字列が単なるアドレスであるならば、get_stringのような関数の戻り値は、文字列そのものではないはず。なぜなら文字列は高いレベルの概念だから
get_stringが常に行っていることは、文字列のアドレスを返すこと、より具体的には、文字列の最初の文字のアドレスを返すことだった！
sというポインタ変数に格納されているのは、この場合では0x123というアドレス
＝文字列全体を返しているわけではない
むしろ、一つの値だけを返している
tはどうなっている？
tも同様に、再びget_stringを呼び出す
tにはこのバージョンの「HI!」の最初の文字のアドレスが割り当てられる
H 0x456
I 0x457
! 0x458
\0 0x459
この時点ではtは0x456を格納している
sもtも単なるポインタであり、それぞれある文字列の最初の文字を指し示しているだけ
二つの文字列を比較する場合、以前のバージョンのプログラムのように、sがtと等しいかどうかをチェックしようとしていた
sとtはそれぞれ0x123と0x456、あるいは実際の値が何であれ、異なるメモリの塊を指しているので、同じにはならない
以前出てきた、2つの文字列を比較できるstrcmpという関数
その際に、なぜ単に等号を使うのではなく、strcmpを使うのか、そのうち説明すると約束していた
↓strcmpを使って今回の文字列を比較してみる
#include <string.h>
#include <cs50.h>
#include <stdio.h>
int main(void)
{
char *s = get_string("s: ");
char *t = get_string("t: ");
if(strcmp(s,t))
{
printf("Same\n");
}
else
{
printf("Different\n")
}}
↓実行すると、同じ文字列でも「Different」と表示されてしまう…
何か間違えた？
strcmpの戻り値を思い出してみると、ASCII順が同じであれば0、一方が前にあれば負の数、一方が後にあれば正の数を返すようになっている
if(strcmp(s,t) == 0) ←「==0」を加える必要があった
↑実行してみると、同じ文字列ならちゃんと「Same」と表示されるようになった！
前にやった事と結果は同じだが、今回は文字列を単なるアドレスと捉えて扱っている
▼文字列をコピーして変更を加え、変更前と変更後を表示するプログラム
#include <cs50.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(void)
{
char *s = get_string("s: ");
char *t = s;
t[0] = toupper(t[0]);
printf("s: %s\n",s);
printf("t: %s\n",t);}
char *s = get_string("s: ");
sを文字列tにコピーしたい
char *t = s;
代入演算子を使って変数を右から左へコピーするのは、整数でも文字列でも、おそらく他のデータ型で同じだろう
t[0]を大文字に変更する
t[0] = toupper(t[0]);
※toupper関数を使うためにctype.hをインクルードする
⇒実行してみると、
確かにtは最初の文字が大文字に変更されているが、sまで変更されてしまっている
↑tにコピーしたのはsのアドレスだから
tの一文字目を大文字にする＝sのアドレスにある文字列の一文字目を大文字にするのと同じ
sもtも同じ位置にある文字列の1文字目のアドレスを指し示すポインタ変数になっている
今回の場合は、文字列をコピーする方法を根本的に見直す必要がある
写真やコピーのように、人間が考えるような方法で文字列をコピーしたい場合、どのようにすればいいか？
生徒⇒sの要素をループさせて1つずつtの要素に代入していけばいいのでは？
それでは手数が多くなってしまう…⇒sとtが単なるアドレスであるという事実を受け入れるのであれば、これらの手がかりをたどっていかなければならない
▼変形版のコード
#include <cs50.h> ←get_stringに必要
#include <stdio.h>
#include <stdlib.h> ←mallocに必要
#include <string.h> ←strlenに必要
#include <ctype.h> ←toupperに必要
int main(void)
{
char *s = get_string("s: ");
char *t = malloc(strlen(s)+1);
for(int i = 0 , n = strlen(s); i <= n; i++)
{
t[i] = s[i];
}
t[0] = toupper(t[0]);
printf("s: %s\n",s);
printf("t: %s\n",t);}
依然としてsという文字列を取得する
⇒個々の文字をどこかにコピーしなければならない
文字列をコピーするプロセスの一つのステップとして、メモリを追加しなければならない
「HI!\0」があるとすると、この状況をどうにかしてコントロールし、コンピュータにコードで「あと4バイト分のメモリをくれ」と言って、文字をコピーするためのtの場所を確保する必要がある
文字列t(char *)を作りたい場合、メモリの割り当てを意味するmallocという新しい関数を使うことができる
※mallocを使うには#include <stdlib.h>を追加
mallocなどの関数がどのライブラリに入っているか？とかは、実際にはGoogleで検索すればOK。全て覚える必要はない。
malloc ←入力としてコンピュータに何バイトのメモリを要求したいのかを指定する数字を受け取る
ここでは「sの文字数に1を加えた数のバイトをください」と言っている
char *t = malloc(strlen(s)+1);
なぜ1を加える？⇒HI!だけなら3バイトになるが、最後のnul文字の文もバイトに追加する必要がある←tにも同じようにnul文字を置かないと、tの終端がわからなくなるから
for(i = 0; n = strlen(s);i <= n; i++)
{
t[i] = s[i];
}tにsの各文字を一つずつコピーしていく
「i <= n」←1ステップ分余分に処理するのはなぜ？
↑nul文字も含める必要があるから
⇒実行すると、確かにtの一文字目だけが大文字になった！
t[i] = s[i];↑より低レベルなところまで理解していることを示したいなら、
*(t+i) = *(s+i)
↑こうすることもできるが、読みにくくなるだけなので実際にはやめた方が良い
一方で、このプログラムには危険な点がある
ユーザーがget_stringに対して何も入力せずにEnterを押したらどうなる？
文字列の長さは0になる
↑実際には存在しない文字列の最初の文字を大文字にすべきではない
そのため、例えばtの文字列の長さが少なくとも0より大きい場合に限って、安全に処理を進めるというようなエラーチェックを行うべき
if(strlen(t) > 0)
{
t[0] = toupper(t[0]);
}
また、今回のような短い文字列ではなく膨大なメモリを消費するプログラムになることを考えると、もっとエラーチェックが必要になる
mallocはほとんどの場合、割り当てたメモリの塊のアドレスを返してくれる
get_stringと同じように、確保したメモリの塊の最初のアドレスを返してくれる
↑コンピュータのメモリが不足した場合は上手くいかなくなる
メモリエラーでPCがフリーズしたりしてしまう
▼メモリエラーを回避するためのエラーチェック
malloc関数の直後に↓
if(t == NULL)
{
return 1;
}
もしtがこの特別な値NULLに等しければ、1を返して終了し、プログラムから抜け出す
C言語の設計者や一般的なプログラマーは、\0を意味するNULと似たNULLという言葉を使っているが、NULとNULLは別の値。
⇒NULLはnullポインタを表す←偽のアドレスで、「アドレスが存在しない」ことを表す
技術的にはアドレス0を表す
※NULLはstdlib.hファイルに付属している記号
\0(nul文字)は文字のためのもの
NULLはポインタのためのもの
上記のプログラムで行った一文字ずつのコピー←実はそれを行ってくれる関数が存在する
strcpy(コピー先,コピー元)
もう一つ直しておきたいバグがある
mallocを使ってメモリを確保し、コンピュータにメモリを要求した場合、最終的にそれを返す責任はプログラマーである皆さんにある
4バイトでも400万バイトでも、コンピュータに、より具体的にはLinuxやMac OS、Windowsなどのオペレーティングシステムに返した方が、最終的にコンピュータがメモリ不足にならずに済む
メモリをもらったら、最後にメモリを解放する
free(t);
freeはmallocの出力を入力とする関数
メモリの扱い方が変わった
sというポインタ変数で指し示している「hi!」
tというポインタにmallocでもらった4バイトの最初の1バイトのアドレスを格納
sからtに文字をコピーすると、mallocでもらった空きメモリに1文字ずつコピーされる
前回のようにsとtは同じではなく、tはsのアドレスにあったものを1ステップずつコピーした独自のメモリの塊を指している
↑これが人間が言うところのコピー
実はcs50.hのget_stringもmallocを使っている
freeもcs50に仕込まれている⇒mainが終了したり、プロンプトに戻ったりしようとすると、最後の瞬間に私たちが書いた特別なコードが割り当てたメモリを解放し、メモリが不足しないようにしていた
メモリ関連のバグを追跡してくれるツール「Valgrind」
CS50 IDEにも、MacでもPCでもLinuxでもどこにでもあり、自分のコードで実行して、メモリの使い方が間違っていないかどうかを調べることができる
どこでメモリを触ってはいけなかったのかを把握するためのツールで、バグがあるコードの行に人間の注意を集中させることができる
mallocを使ったのにfreeを使わなかった＝メモリリーク…とかも検出できる
よくPCやスマホで多くのブラウザやソフトを同時に開いていると動作が重くなる現象←プログラマーがメモリを割り当てているのにfreeを呼んでいない、というバグがあるからかもしれない
皆さんがブラウザのタブを開くたびに皆さんが使っているChromeやEdge、Firefoxなどのあらゆるブラウザは、Mac OSやWindowsでmallocなどの関数を呼び出して、Webページのコンテンツを一時的に格納するためのメモリを確保しているはず
最近のコンピュータは賢くて、メモリ上のものを一時的に削除してスペースを空けることができる＝仮想メモリ←最終的には何かが壊れてしまう
valgrindをどう使うのか？
何の役にも立たないけどメモリ関連のミスを連発するプログラムを書いてみる
▼memory.c
#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);}
文字列を構築する最もマニュアル的なコード
ここで、mallocで確保するバイトを3にしてみる(nul文字分抜けてる)
char *s = malloc(3);
あえてfreeも呼ばないでおく
⇒コンパイルは成功し、「HI!」と表示され、問題なく動作しているように見える
視覚的に見えず、自分で動かしても体感できないようなバグがコードに潜んでいる⇒何度も実行するうちに最終的にはエラーが発生するかもしれない
↓valgrindでエラーを検出できる
valgrind ./memory
ものすごい量の出力がある
↓
~/ $ valgrind ./memory
==570== Memcheck, a memory error detector
==570== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==570== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==570== Command: ./memory
==570==
==570== Invalid write of size 1
==570== at 0x401171: main (memory.c:10)
==570== Address 0x4bd9043 is 0 bytes after a block of size 3 alloc'd
==570== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==570== by 0x401151: main (memory.c:6)
==570==
==570== Invalid read of size 1
==570== at 0x483EF54: strlen (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==570== by 0x4A60E94: __vfprintf_internal (vfprintf-internal.c:1688)
==570== by 0x4A62021: buffered_vfprintf (vfprintf-internal.c:2377)
==570== by 0x4A5EEA3: __vfprintf_internal (vfprintf-internal.c:1346)
==570== by 0x4A49EBE: printf (printf.c:33)
==570== by 0x401189: main (memory.c:12)
==570== Address 0x4bd9043 is 0 bytes after a block of size 3 alloc'd
==570== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==570== by 0x401151: main (memory.c:6)
==570==
HI!
==570==
==570== HEAP SUMMARY:
==570== in use at exit: 3 bytes in 1 blocks
==570== total heap usage: 1 allocs, 0 frees, 3 bytes allocated
==570==
==570== 3 bytes in 1 blocks are definitely lost in loss record 1 of 1
==570== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==570== by 0x401151: main (memory.c:6)
==570==
==570== LEAK SUMMARY:
==570== definitely lost: 3 bytes in 1 blocks
==570== indirectly lost: 0 bytes in 0 blocks
==570== possibly lost: 0 bytes in 0 blocks
==570== still reachable: 0 bytes in 0 blocks
==570== suppressed: 0 bytes in 0 blocks
==570==
==570== For lists of detected and suppressed errors, rerun with: -s
==570== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
~/ $
▼検証
①
==570== Invalid write of size 1
==570== at 0x401171: main (memory.c:10)
10行目を見てみる
無効な書き込み
s[3] = '\0';
mallocで3バイトしか取得していないのに4バイト目に入力しようとしている
取得していない1バイト先を見るだけでプログラムのクラッシュの可能性がある
②
Invalid read of size 1
printf("%s\n",s);
↑そもそも触ってはいけないバイトが含まれている文字列を読み取ろうとしている
③
freeを呼び出していない
これらのバグに気付いて理解するには、ある程度の練習と経験、そして自分自身のミスが必要
ちゃんと4バイト確保して、最後にfree(s);を追加して、再コンパイル
↓valgrindしてみると…
~/ $ valgrind ./memory
==722== Memcheck, a memory error detector
==722== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==722== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==722== Command: ./memory
==722==
HI!
==722==
==722== HEAP SUMMARY:
==722== in use at exit: 0 bytes in 0 blocks
==722== total heap usage: 1 allocs, 1 frees, 4 bytes allocated
==722==
==722== All heap blocks were freed -- no leaks are possible
==722==
==722== For lists of detected and suppressed errors, rerun with: -s
==722== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
~/ $
無効な読み書きに関する記述も無い
⇒バグを修正できた！
▼危険なコードの例
int main(void)
{
int *x; int型のポインタ変数を宣言
int *y; int型のポインタ変数を宣言
x = malloc(sizeof(int)); xにint型に必要なバイト＝4バイトのメモリを確保
*x = 42; xのアドレスに42を置く
*y = 13; yのアドレスに13を置く←yには何も代入していない！
y = x;
*y = 13;}
*y = 13;
yに値を割り当てていないのに、そのアドレスに値を代入しようとしている
(xには実際のアドレスを格納している)
yに値を与えていないことが問題
ここまでは、私たちがほとんど常にメモリを初期化していることを当然と考えてきた
charやint、文字列を与えたい時は、プログラム自体に入力して、必要なときにすぐに使えるようにする
皆さん自身が何かをそこに置いていない場合、コンピュータのメモリの内容を決して信用してはならない
ゴミのような値(garbage value)というプログラミング用語がある
自分自身がメモリのどこかに値を入れていない場合、安全のために、それは引用符で囲まれた「ゴミのような値」だと考えるべき
奇妙な値というわけではなく、ただの1や2やAやBといったものだが、皆さんはそれが何であるか知らない
プログラムは時間をかけて実行され、関数を呼び出し、関数が戻ってくる。他の関数を呼んでも、関数が返ってくる。コンピュータのメモリ内のこれらの値は常に変化しており、メモリは再利用される
「メモリを解放する」と言っても、メモリを消去したり、すべてを0に戻したり、すべてを1に戻したりするわけではない⇒再利用できるように残す
時間が経つと、皆さんのコンピュータにはプログラムで使用したすべての変数の残骸が、ここにもあそこにも残ることになる
今回のプログラムでは、yを明示的に初期化していないので、いわばゴミのような値がその場所にいると考えるべき
アドレスのように見えるが、有効なアドレスではないゴミのような値
*y = 13;
↑ありもしないアドレスに行って、そこに13という値を置いてくる、ということ
＝プログラムがクラッシュする可能性＝セグメンテーション・フォールト
初期化されていない変数を間接参照しようとすると、プログラムがクラッシュする可能性がある
ゴミのような値はどうやって見ることができるのか？
⇒自分のコードで見ることができる
▼garbage.c
#include <stdio.h>
int main(void)
{
int scores[3];
for(int i = 0;i < 3; i++)
{
printf("%i\n",scores[i]);
}}
scoresというint型でサイズ3の配列を用意するが、意図的に値を初期化せずに、
配列の1～3番目のそれぞれに入っている値を表示するプログラム
↓
1609595264
32766
0
これらの値はコンピュータが自動で初期化してくれるわけではない。
例外がある。
私たちはグローバル変数、つまりmainや他のすべての関数のコンテキスト外にある定数を使うこともある
グローバル変数は設定しなければ慣習的に0またはNULLに初期化される
しかし、一般的にはそのような動作に頼るべきではない
値を触ったり、printfやその他のメカニズムで読んだりする前に、常に初期化すべき
メモリを理解することによって解決できる問題もあるが、同時に新たな問題に遭遇する
▼swap.c
二つの値を交換するという非常にシンプルなプリミティブを考えてみる
例えば二つの整数をスワップする場合
#include <stdio.h>
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, y is %i\n",x,y);
swap(x,y);
printf("x is %i, y is %i\n",x,y);}
swap(x,y);
カスタム関数を実装する
どうやって値を交換する？
先週、ブライアンは数字を両手で取って入れ替えしていた
目の前に赤い液体が入ったグラスと青い液体が入ったグラスがあるとする
実は赤い液体が青いグラスに入っていて、青い液体が赤いグラスに入っている方が好ましい
⇒これを入れ替えるとすると？
グラス自体を持って入れ替えようとするブライアン←グラスをメモリの特定の場所と考えると、コンピュータの中のメモリチップを物理的に動かして入れ替えることはできない
一方の液体をもう一方のグラスの中に移動させてコンピュータのメモリのようにしてほしい←すでに2つのグラスにはどちらも液体が入っているので、入れ替えられない…？
⇒2つのグラスだけを使って何らかの入れ替えをしなければならないとしたら良い結果にはならない
⇒3つ目のグラスが必要
赤いグラスに青い液体を入れたいので、まず赤いグラスの中の赤い液体を3つ目の空のグラスに入れて、赤いグラスを空ける
⇒赤いグラスに青い液体を注ぐ
⇒3つ目のグラスに入れておいた赤い液体を青いグラスに入れる
グラスの位置は変えずに中身だけを入れ替えることができた
・コードの中に一時的な変数が必要になるということ
・最低で3つのステップが必要(1つを出して、もう1つを出して、もう1つを戻す)
⇒コードに変換してみる
▼swap()
3つ目のグラス＝変数tmp ※コードの中で2つのものを入れ替えたい時の慣習に従ってtmpと呼ぶ
void swap(int a,int b)
{
int tmp = a; tmp(3つ目のグラス)にa(グラス①)の中身を入れる
a = b; a(空になったグラス①)にb(グラス②)の中身を入れる
b = tmp; b(空になったグラス②)にtmp(3つ目のグラス)の中身を入れる
}
▼swap.c 修正版
#include <stdio.h>
void swap(int a, int b);
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, y is %i\n",x,y);
swap(x,y);
printf("x is %i, y is %i\n",x,y);}
void swap(int a, int b)
{
int tmp = a;
a = b;
b = tmp;}
↓
x is 1, y is 2
x is 1, y is 2
うまくいっていない！
カスタム関数swap()の中でaとbがどうなっているのか、printfで見てみる
↓！？
x is 1, y is 2
a is 1, b is 2
a is 2, b is 1
x is 1, y is 2
aとbは入れ替わっているのに、最後のxとyがまた入れ替わってる？
swap()の中ではうまくいっているのに、mainに反映されていない…？
debug50を実行して、swap()の中の最初の行にブレークポイントを設定し、1ステップごとに進んでswap関数にステップインする
メモリでは何が起きている？
コンピュータはメモリを割り当てる際に、完全にランダムな配置ではなく、標準的な方法を採用する
⇒例えばCS50 IDEやLinuxでプログラムを実行したり、Mac OSやWindowsでアイコンをダブルクリックしたりすると、ハードドライブに保存されているプログラムの0と1がここに読み込まれ、マシンコードと呼ばれる0と1のコードが生成される
皆さんのメモリが長方形の領域だと考えると、プログラムを構成する0と1のマシンコードは、メモリの一番上の部分(標準的な場所)に読み込まれる⇒その下にグローバル変数と関数の外側に置く定数がある⇒その下にヒープ(Heap)がある
Heap＝mallocが予備のメモリを確保するために使用する大きなメモリの塊
mallocを呼び出すたびに、マシンコードやグローバル変数の下にある、この領域のメモリの塊のアドレスが与えられる(一種の大きな区画)
しかし、メモリの他の部分は異なる方法で使用されている
ちょっと心配なのはHeapがここから下に向かって存在すると考えられているのに対し、stackがここから上に向かって存在すると考えられていること
つまり、mallocを呼んでメモリを要求すると、それはここ(Heapの部分)で割り当てられる
一方、関数を呼び出した場合、関数はHeap空間ではなく、Stack空間と呼ばれるものを使用する
main、swap、strlen、strcmpなど、今までに使った関数を呼び出すと、コンピュータは自動的にローカル変数やパラメータをここ(stack空間)に格納する
↑これは最適な状況ではない。Heap空間とstack空間の互いに向き合っている矢印は、2台の列車が線路上をお互いに向かって猛烈なスピードで走っているようなものだから。最終的には悪いことが起きそう
幸いなことに、通常は十分なメモリを持っているので、これらが衝突することはないが、それについてはまた後で説明する
swap()ではmallocを使っていない⇒Heapについては心配しなくても良さそう
グローバル変数やマシンコードについても使っていない
⇒stackについて考える必要がある
stackはメモリが利用され、再利用される動的な場所
例えば、このswapプログラムを実行するときのようにmainを呼び出すと、mainはこの図の一番下(stack空間)にある一片のメモリを使う
つまり、mainのローカル変数であるxやyは、この下の部分(下端)のメモリを使うことになる
swapを呼び出すと、swapは変数aやb、tmpなど、この図のmainのすぐ上にあるメモリの塊を使う⇒swapが戻ってきて実行が終わると、そのメモリの切れ端は基本的に使われなくなる←消えてしまうわけではなく、物理的には残る
⇒ここで再びゴミのような値の話になる
ゴミのような値はあちこちに散らばっており、どんな値かわからず、気にもしていない
しかし、何かしらの値は入っている(さっき初期化されていないスコアの配列を表示した時に謎の値が表示されたのもそのため)
メモリに見立てたオスカーのブロックを使って説明
一番下端の列をmainで使う⇒int型変数を2つ(xとy)用意したいので、サイズ4×2の分のオスカー(ゴミのような値)を除去し、それぞれに1と2という値を入れる
次にswap関数にaとbという変数を設ける
aとbは意図的にxとyのコピーになっているが、それはxとyを渡したから
swap関数がaとbを引数に取るように定義した
ここで物理的に必要なのは、下から二列目(mainの上の列)のメモリはmainではなくswap関数に属するものと考えること
二列目にもint型変数を2つ(xとy)用意したいので、サイズ4×2の分のオスカー(ゴミのような値)を除去し、1(xの値)と2(yの値)を入れる
↑しかし、swapには3つ目の変数がある
更に上の列にサイズ4の場所を作るためにゴミのような値を除去してtmpという変数を設ける
↓
tmpをaにする(aが1ならtmpも1)
aをbにする(bが2ならaも2)
bをtmpにする(tmpが1ならbも1)
aは2、bは1
↑swapはaとbの値を入れ替えている限りにおいては正しいことがわかる
しかし、swapが戻った瞬間、これらはゴミのような値に戻ってしまう
mainはまだ実行中、swapはもう実行されていないが、それらの値は同じ場所に留まっている
私たちはそれが何であるかをたまたま知っているが、それはもはや有効ではない
2回目にxとyを表示した時、xとyは同じだった(入れ替わっていなかった)
つまり、引数を取るコードを書いたり、ある関数から別の関数に引数を渡したりすると、それらの引数はある関数から別の関数にコピーされるということ
そして確かにxとyはaとbにコピーされる
コードを見ると一見正しく入れ替えできているように見えるが、それはswapの文脈で正しく入れ替えされているだけで、元の値には触れていない
そのため、基本的にはxとyの値を実際に変更するような形でswapを再実装する必要がある
swapの実装を概念的に変更して、xとyのコピーを変更するのではなく、xとyを変更することができるようにするにはどうしたらいい？
⇒ポインタを使う
ポインタがコンピュータのメモリ内の特定のアドレスへの宝の地図のようなものだとすると、mainからswapへの処理で実際にすべきことは、xとyを文字通り渡すのではなく、xとyのアドレスを渡すことではないでしょうか
そうすればswapはそれらのアドレスに行き、ブライアンが実演したようなスワップを行うことができるようになるはず
つまり、関数にそれらの値へのマップやポインタを与えて、それらの値へ行くようにする
コードを修正してみる
今回必要なのは、xとyのアドレスをswapに渡すこと
swapではaを整数ではなく整数へのポインタ、つまりint *変数として宣言すれば、これをaと呼ぶことができる←その中にxのアドレスを格納する
bも同様にポインタとして宣言し、yのアドレスを格納する
3つ目のグラスtmpはただの整数の変数を宣言すればOK
tmpにアドレスaにあるものを格納する(tmpにxの値1が入る)
aの値ではなく、aのアドレスにあるものをbのアドレスにあるものに変更する
(実際にxにyに入っていた値2が入る)
bが指し示すアドレス(つまりy)に行き、それをtmpの値に変更する
(yに元々xにあった値1が入る)
↓
単純に値のコピーを取得するのではなく、swapがこれらのアドレスに行くようにすることで、xとyのスワップに成功している
▼swap.c ポインタを使った修正版
#include <stdio.h>
void swap(int *a, int *b);
int main(void)
{
int x = 1;
int y = 2;
printf("x is %i, y is %i\n",x,y);
swap(&x,&y);
printf("x is %i, y is %i\n",x,y);}
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
b = tmp;
}
aとbの前にを付ける
swap(&x,&y);
swapに渡すのはxとyのアドレス
xとyのアドレスを渡して、swapがメモリ上のこれらの場所の内容にある種特別なアクセスをして、そこに変更を加えることができるようにしたい
ある関数から別の関数に値を渡すためには、コンピュータのメモリで何が起こっているかを理解する必要がある
ヒープが上から下へ、スタックが下から上へ進んで起きる問題
⇒ヒープオーバーフローやスタックオーバーフローと呼ばれる
スタックオーバーフローとは、ある関数を何度も呼び出してヒープをオーバーフローさせてしまうこと
つまり、今回のように関数を呼び出すたびに、いわばメモリの列をどんどん使ってしまうということ⇒たくさんの関数を何度も呼び出していると、最終的にはヒープと呼ばれるメモリの領域を使い切ってしまうかもしれない⇒プログラムがクラッシュする
マリオのピラミッドを作る方法
いくつかの異なる方法がある
1つは、week1のスタイルであるループを使った反復
↑それを使った簡単なソリューションを作ってみる
▼mario2.c
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
int height = get_int("height: ");
draw(height);
}
void draw(int h)
{
for(int i = 1; i <= h; i++)
{
for(int j = 1; j <= i; j++)
{
printf("#");
}
printf("\n");
}
}
height:4と入力
↑ちゃんと表示される
これを再帰的なものに変えてみる
再帰関数とは自分自身を呼び出す関数のこと
高さhのピラミッドを表示するにはどうすればいい？
高さh-1のピラミッドを表示し、さらに1列分のブロックを表示したことを思い出してください
void draw(int h)
{
draw(h-1);
for(int i = 0; i < h; i++)
{
printf("#");
}
printf("\n");
}
↑ここで何をしている？
高さが1の場合はこのループを1回だけ繰り返す
高さが2の場合は2回、3の場合は3回…と繰り返していきたい
↓コンパイルしてみると…
~/ $ make mario2
clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wextra -Wno-sign-compare -Wno-unused-parameter -Wno-unused-variable -Wshadow mario2.c -lcrypt -lcs50 -lm -o mario2
mario2.c:14:1: error: all paths through this function will call itself [-Werror,-Winfinite-recursion]
{
^
1 error generated.
make: *** [<builtin>: mario2] Error 1
「all paths through this function will call itself」
clangはdraw関数の中でdraw関数が呼び出されていることに気づいている
これはmakeに施されたチェックで、その過剰な補助輪を無効化する必要がある
clang -o mario2 mario2.c -lcs50
(clang -o コンパイル後のファイル名 コンパイル前のファイル名 -lリンク先)
↓
コンパイルできた
↓
./mario2を実行してみると…
↓
~/ $ ./mario2
height: 4
Segmentation fault
↑クラッシュしてしまった！
セグメンテーションフォールトとは、触ってはいけないメモリに触ってしまったということ
先ほどのオスカーのメモリ図で考えてみると、下端のmainの上にどんどんdrawが積み重なっていったイメージ
drawを呼び出すたびにdrawが呼び出されるとしたら、止まりようがない
上記の再帰バージョンには重要なディテールが欠けていた
⇒描画するものが無ければ＝高さが0であればすぐにリターンするようにする
再帰の場合、ベースケースが必要になる
高さが0、高さが1といったハードコードされた単純な値の場合に選択するもので、drawが自分自身を呼び出さないようにする
▼mario2.c 再帰ベースケース修正バージョン
#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 = 0; i < h; i++)
{
printf("#");
}
printf("\n");}
↓実行
~/ $ clang -o mario2 mario2.c -lcs50
~/ $ ./mario2
height: 4
↑出来た！
反復より再帰の方が優れている？←時と場合による
反復バージョンを使うときは、スタックをオーバーフローさせてヒープを叩くことはない
関数を何度も呼び出さないから(mainとdrawの呼び出しは1回だけ)
再帰はパワフルでエレガントな循環的な技法だが、危険が潜んでいる
実際、このベースケースでは永遠には続かないことが保証されているが、非常に長く続く可能性はある⇒10000回の呼び出しを試してみる
⇒実行はされるが、途中で遅くなってくる⇒ctrl+cで止める
20億回で試してみる⇒セグメンテーションフォールトになってしまう
再帰には固有の危険性がある
先週、マージソートを使ってさらに効率的に問題を解決することができたが、ブライアンの棚にそれほどたくさんの数字がなかったのは幸運だったと言える
というのも、再帰を使って自分を何度も何度も呼び出していると、たとえ有限回数であっても最終的に触ってはいけないメモリに触れてしまう可能性があるから
↑解決策は「それをしないこと」しかない
そのようなリスクがないようにアルゴリズムを設計し、入力を選択する
もう一つぶつかる問題がバッファオーバーフロー
今後数週間で必ず躓くことになる
↑配列を割り当てた時に、その配列の境界を超えてしまうこと
あるいは、mallocを使っていて、割り当てたメモリの塊の境界を超えてしまう場合
バッファとはメモリの塊で、自分の好きなように使うことができる
動画などでバッファリングという言葉がある
回転するアイコンがあって、イライラさせられるやつ
YouTubeやZoomやNetflixの文脈でのバッファとは、mallocなどで取得したメモリの塊で、動画を構成するバイトで満たされている←有限
だからこそ、何秒も何分もビデオをバッファリングすることができるが、最終的にはオフラインの場合、見るべきビデオコンテンツがなくなってしまう
そして、アイコンが出てきてもう見られなくなる⇒バッファは単なるメモリの塊であり、メモリの配列だから
NetflixやGoogleなどが安全でないコードを実装した場合、その境界を超えてしまう可能性がある
これまでCS50ライブラリの補助輪を少しずつ外してきた
CS50ライブラリにあるユーザーフレンドリーな関数は、例えばC言語のscanfなどに置き換えられるが、それらの古い関数を使うには危険が伴う
それを実演してみる
▼scanf.c
#include <stdio.h>
int main(void)
{
int x;
printf("x: ");
scanf("%i", &x);
printf("x: %i\n",x);
}
scanf("%i", &x);
get_intなどのように、ユーザーからの入力を受け取る関数
ユーザのキーボードから整数をスキャンして、それをxの場所に格納する
↑これを使うためにはポインタを理解している必要がある
なぜなら、swapの例を思い出してほしいが、aとb、xとyで行ったように、関数で変数の内容を変更したい場合、変更したい値を持つ変数のアドレスを渡さなければならない
＝x自体を渡すことはできない
最初にCS50ライブラリのget_intを使わなかったとしたら、これらの概念(ポインタ、アドレス、メモリの使われ方…)から学ばなければならなかった←最初はループや変数、条件などの基本的なことにしか興味がなかったのに、これでは多すぎる
scanf("%i",&x);
xのアドレスを渡すことで、scanfがそのアドレスに行き、ユーザーのキーボードから入力された整数をそこに置くことができる
↓50を入力してみる
~/ $ ./scanf
x: 50
x: 50
↑動作してるっぽい…
↓catを入力してみると
~/ $ ./scanf
x: cat
x: 0
↑0になってしまった
CS50ライブラリの特徴の1つは「協力してくれないユーザーには何度もプロンプトを出してintを返す」ということだった
get_stringはもっとパワフル
プログラムを文字列用に変更してみる
#include <stdio.h>
int main(void)
{
char *s;
printf("s: ");
scanf("%s", s);
printf("s: %s\n",s);
}
scanf("%s", s);
↑文字列はそもそもアドレスなので、&sにする必要はない
コンパイルしようとすると…
~/ $ make scanf
clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wextra -Wno-sign-compare -Wno-unused-parameter -Wno-unused-variable -Wshadow scanf.c -lcrypt -lcs50 -lm -o scanf
scanf.c:7:17: error: variable 's' is uninitialized when used here [-Werror,-Wuninitialized]
scanf("%s", s);
^
scanf.c:5:12: note: initialize the variable 's' to silence this warning
char *s;
^
= NULL
1 error generated.
make: *** [<builtin>: scanf] Error 1
↑ここで使われている変数sが初期化されていない状態であることを嫌がる
makeではなく、clangで直接コンパイルしてみる
~/ $ clang -o scanf scanf.c
~/ $ ./scanf
s: cat
s: (null)
↑nullになってしまった！
幸いなことにmakiが、ひいてはclangが私たちの助けになってくれた
それらはsを宣言したところを指摘していた
つまりポインタのために8バイトを宣言したが、そこには何もなく、ゴミのような値しか入っていなかった←置くべきものを置く場所がない
ありがたいことに、printfやscanfは賢いので、やみくもにcやa、tをnullの中に入れるようなことはしない⇒それらは放置され、(null)で「あなたは失敗した」と伝えてくる
ユーザーの入力を得たいなら更に賢くなる必要がある
まず4バイトを割り当てる必要がある
char *s = malloc(4); ※最後にfreeを使わなければならない
または
char s[4]; ※これならfreeを使わなくてもメモリは自動的に解放される
この方法だとスタック上の4バイトをmainのフレームのどこかに4バイト置くことになる
mallocだと上の方のヒープから4バイト割り当てられる
#include <stdio.h>
int main(void)
{
char s[4];
printf("s: ");
scanf("%s", s);
printf("s: %s\n",s);
}
↓実行してみると
~/ $ ./scanf
s: cat
s: cat
~/ $
ちゃんとcatと表示された
しかし、4バイトのメモリしか取得していないので、それを超える文字数が入力されると、超過分は切り捨てられてしまう
get_stringはこれを上手くやってくれていた
mallocを呼び出し、人間が入力した文字列と同じ大きさのメモリの塊を呼び出す
つまり、私たちは人間が入力した文字を一文字一文字見て、人間が入力した文字列に見合うだけのメモリを割り当てたり、再割り当てしたりするようにしなければならない
scanfは、CS50ライブラリのような関数が覆いの下でどのように動作するかを示している
このような補助輪、つまりライブラリを取り去ったとたんに、このような低レベルのものをもっと自分で実装しなければならなくなる
最後にもう一つの機能を紹介する
ファイルを探索して操作したり、コードを書いてその内容を変更したりする
そのためにはファイルI/Oについての最後のトピックが必要
ファイルI/Oとはファイルからの入出力を行うことを表す言葉
これまで書いてきたほとんどのプログラムは、メモリを使っているだけなので、メモリに何かを入れることはできる
しかし、プログラムを終了すると同時になくなる。メモリの中身は消えてしまう
ファイルとは、コンピュータの世界では私たちがエッセイや文書、履歴書などをコンピュータに永久保存する場所
C言語ではファイルを長期的に保存するコードを自分で書く事ができる
例えば、名前と番号をファイルに保存する電話帳プログラムを書いてみましょう
▼phonebook2.c ファイルに名前と番号を書き込んで保存するプログラム
#include <cs50.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
FILE *file = fopen("phonebook2.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);}
FILE C言語に付属する新しいデータ型で、ファイルを表す
fopen(開きたいファイルの名前,どんなモードで開くか)
どんなモードで開くか？↓3つの方法がある
①内容を見るだけの「読み取り」＝r
②内容を完全に変更する「書き込み」 =w
③1行ずつ追加していく「追加」 =a
csv コンサルティングや分析の世界ではよく知られている単なるスプレッドシートのこと(カンマ、セパレイテッド、ヴァリュー)
コンマで区切られたファイルで、エクセルやナンバーズ、Googleスプレッドシートなどで開くことができる
↑このファイルにprintfでなくfprintfで文字列、カンマ、文字列、改行を入力し、名前と数字を入力する
fprintf(文字列を送りたいファイルへのポインタ,"文字列")
fclose(閉じたいファイルへのポインタ)
↓
名前と番号を入力するとphonebook.csvというファイルができて、そこに追加されていく
↓
CS50 IDEのDownloadからファイルをダウンロードすることも可能
ポインタを自由に使えるようになった今、ファイルのようなものを実際に操作できるようになった
画像は有限の解像度があるピクセルで表現されている
CSIマイアミとかのドラマでは防犯カメラの映像を拡大してメガネに映りこんでいるものを特定したりしているが、元の映像の解像度を上げてそんなことをすることはできない
一方で、現在では小さい画像を大きな画像に見た目を変えずに拡大することができるようになっている
↑ある種のエンハンス処理を行っている
簡単に言うと、洗練されたアルゴリズムを使って、人工知能や機械学習を使ってデータを分析し、人間の目には必ずしも見えないパターンを見つけることができる
ハーバード大学の建物の水彩画⇒Photoshopでもある程度の拡大ができる
画像を機会学習ベースのソフトウェア、つまり人工知能にかけてみると、Photoshopでかなり拡大されている建物上部の窓だけでなく、より詳細を見ることができるようになる
必ずしもそこにあった情報を復活させるわけではないが、推測して表現することができる
ある意味では情報が無いところに情報を生み出しているようなもの⇒裁判で使えるかどうかは微妙
画像を操作するためには、先ほどのファイルポインタをはじめ、いくつかのプログラム機能がある
最後の例ではポインタやアドレス、ファイルや入出力について理解した上で、自分だけのグラフィカルなファイルを操作するという、来週からの活動の基礎を築く
▼jpeg.c
ウェブページに公開されている、先生が作ったコード
typedef uint8_t BYTE
uint8_tという難解な型を使ってBYTEを定義
int main(int argc, char *argv[])
week2のコマンドライン引数のアイデアを復活させて、ユーザーからの入力を受けることができるようにしている
if(argc != 2)
{
return 1;
}↑ユーザーから2つの引数が渡されなかったら1を返して終了
FILE *file = fopen(argv[1],"r");↑人間がコマンドラインで入力したファイル名を使ってファイルを開く
読み取りモードr
if(!file)
{
return 1;
}↑ファイルがない場合、「!file」、または「file == NULL」の場合(これらは同じ意味)、エラーを意味する1を返して終了する
↑ファイルの最初の3バイトだけ見れば、非常に高い確率で、そのファイルがJPEGであるかどうか判断できる
多くのファイルフォーマットでは、ファイルの先頭にマジックナンバーと呼ばれる番号が付けられている
業界標準の数字で、1、2、3またはそれ以上の数字がファイルの先頭にあることが期待されている
そうすればプログラムがすぐに「これはJPEG、これはgif、これはword、これはexcel…」とチェックすることができる
JPEGにはバイト列がある
BYTE bytex[3];
↑このコードはバイトのバッファ、具体的には3バイトの配列を自分で与えている
fread(bytes, sizeof(BYTE),3,file);↑次の週に見るこのコードはfreadと呼ばれている
ファイルからバイトを取得する
最初の引数であるこの①バッファには、この②データ型のサイズ、つまりバイトのサイズが読み込まれる
そして、この④ファイルからこの③データ型をこれだけ読み込みます
このファイルから3バイトを読み込み、bytesと呼ばれる配列、別名バッファに入れる
↑ファイルにデータを入れるのではなく、ファイルからデータを読み込むコードの書き方
if(bytes[0] == 0xff && bytes[1] == 0xd8 && bytes[2] == 0xff)
↑JPEGのマニュアルで調べたもので、すべてのJPEGはこれで始まらなければならない
MacでもPCでも、インターネット上のあらゆるJPEGファイルの最初の3バイトはこの3バイト
ファイルが本当にJPEGなのかどうかは4バイト目で決まる
このプログラムを実行する際に「./jpeg 引数＝ファイル名」とすると、そのファイルがJPEGなのかどうか判別してくれる
「Maybe」か「No」で
↑画像ファイルの個々のバイト、つまりピクセルにアクセスできるようになった！
最後にプログラムを紹介
cpというプログラムを再実装したもの
cpとはIDEやLinuxに搭載されているプログラムで、ファイルをコピーすることができる
「cp コピー元のファイル名 新しいファイル名」
1つのファイルを開き、そのファイルのすべてのバイトを繰り返しコピー元からコピー先へとコピーしている
JPEG
最近の法執行機関では、ハードドライブやメディアスティック、携帯電話などのデバイスのフォレンジックコピーを取り、紛失や破損、削除されたデータを分析することがよく行われている
⇒皆さんには、デジタルメモリーカードから誤って削除されたJPEG画像を復元するプログラムを書いてもらう
そして、フォレンジックイメージを作成して、メモリーカードのすべてのコピーをお渡しします
つまり、カメラから0と1をすべてコピーして、読み書き可能なファイルにしてお渡しする
BMP
Windows OSの壁紙などによく使われる形式
このファイルを使ってポインタとファイルI/Oで自分だけのInstagramのようなフィルタを実装してみる
例えば下の画像を脱色して白黒にするには、すべてのピクセルを上から下、左から右に繰り返し、赤や緑、青などの色を認識してグレーの色合いに変更する
この写真のすべてのピクセルの色を変更する手法を同様に適用することで、この写真が何年も前に撮られたものであるかのように見せることができる
左右反転も可能
こうして、ファイルが自分のハードディスクや携帯電話にどのように実装されているかを正確に理解することができる
ポインタは一般的にC言語、そしてプログラミング全般の中でも特に難易度の高い機能だと言われている
しかし、皆さんは今、あるいは近い将来、コンピュータサイエンティストなら誰でも見たことがあるXKCDのコミックでさえも理解できるようになっているでしょう