こんにちは。
最近、プログラムはなぜ動くのか 第2版を読んでいるので内容を忘れないように学んだことを要約したメモを載せます。
このエントリは完全な個人のメモです。
お勉強のためにこの本を読んでいるので、内容を覚えるために以前のエントリで紹介したSummarizing(サマライジング)を行います。
第1章 プログラマにとってCPUとはなにか
CPUの構成要素
CPUの構成要素は制御装置、演算装置、クロック、レジスタの4つ。
この中でも、レジスタには種類いくつかの種類がある。
レジスタの種類は、アキュムレータ、フラグレジスタ、プログラムカウンタ、ベースレジスタ、インデックスレジスタ、汎用レジスタ、命令レジスタ、スタックレジスタ。
プログラムが実行されるときの流れ
プログラムがCPUによって実行されていくときは以下のような流れ。
プログラムをメモリにロード
プログラムカウンタにロードされたメモリの先頭が設定される
順次実行されていく
プログラムは順次実行、条件分岐、繰り返しが基本
これらは機械語のジャンプ命令で実現される
フラグレジスタとは
演算結果が正か負か0かを保持するフラグ
関数呼び出しの仕組み
ジャンプ命令ではなく、コール命令とリターン命令で実現される
関数呼び出し元(return先)のアドレスはスタックに保持される
ベースレジスタ、インデックスレジスタとは
ベースレジスタの位置からインデックスの分だけ移動したレジスタを操作することができる
プログラミングでいうところの配列
機械語の命令の種類
データ転送命令、演算命令、ジャンプ命令、コール/リターン命令の4つ
CPUは複雑そうに見えるが、基本的なところは意外とシンプルにできている
第2章 データを2進数でイメージしよう
なぜPCで扱うデータは2進数なのか
メモリには32本または64本のピンがあり、それぞれが電圧0Vまたは5Vの状態を持っている
0か5Vしか状態を持てないので、入出力できるデータは2種類だけ
なので2進数が適している
2進数の概要、計算方法
詳細な計算方法はここでは割愛
論理shift、算術shift
算術右shiftはshiftしたときに符号ビットを補完する
その方が計算で都合がいいため
その他、2章で面白かったこと
bit = binary digitの略
byte = biteのもじり。ひとまとまりの、という意味
排他的論理は"排他的"なので、bitが異なるときに1(真)になるという説明文
第3章 コンピュータが小数点数の計算を間違える理由
小数点を2進数で表すには
小数点第一位から2^(-1), 2^(-2)と重みを変化させていく
2新数での整数の表し方と同じ
何故誤差が生まれるのか
2^(-1)や2^(-2),2^(-3)をいくら足してもぴったり表現できないものがある
10進数でも1/3(0.33333333...)を正確に表現できないのと同じ
PCの中で扱うデータはある程度の桁までしか扱えないので、どこかで切り捨てや四捨五入が行われて誤差になってしまう
浮動小数点数の説明
浮動小数点数には倍精度浮動小数点数(double)と単精度浮動小数点数(float)がある
サイズが違うだけで基本は一緒
浮動小数点数の表現方法
符号bit(1bit)、指数部(doubleは11bit, floatは8bit)、化数部(残りのbit)
化数部は整数第一位が1になるようにする
指数部はイクセス表現
※イクセス表現＝表現できる範囲の真ん中を0として扱う表現方法
誤差を回避するためには
そもそも小さい誤差なので間違いを無視する
少数を整数に置き換えてから計算する
BCDを使う
BCDは金融システムとかではこれが使われるらしい
4bitで1～9を表現する
第4章 四角いメモリーを丸く使う
メモリICの仕組み
メモリICは電源、アドレス信号を入出力するするピン、データ信号を入出力するピン、制御信号(R or W)を入出力するピンでできている
メモリのイメージ
メモリの論理的なイメージはビル
1つのフロア(階)につき1byteのデータを格納できる
データ型は、フロアの数の指定
charなら1byte(フロア)、shortなら2byte、intなら4byteなど
Intelなどのメモリはリトル・エンディアン方式を採用している
リトル・エンディアン方式とは、データの下位バイトをメモリの下位アドレスに格納する方式
ビッグ・エンディアン方式はデータの上位バイトをメモリの下位アドレスに格納する
ポインタとは
ポインタはメモリのアドレスを指すもの
ポインタの型はアドレスから何バイトのデータを読むかの指定
で宣言されたものはポインタで示されたアドレスから4バイト読み書きするという意味
メモリの効率な使い方
配列がそのままメモリの構造になっているため、メモリの基本的な使い方は配列
CPUにはベース・レジスタとインデックス・レジスタがある
この2つのレジスタの説明は1章にある
CPUに効率的に配列を処理するための仕組みがあるということ
その他のメモリの使い方
スタック、キュー、リングバッファがある
いずれも配列の応用
スタックはLIFO、キューはFIFO
キューはリング・バッファで実装されることが多い
インデックスが最後まで行ったら最初にもどる方式
(著者曰く、四角いメモリを丸く使う。らしい。。。)
リストの説明
ここでいうリストとはLinkedListのこと
途中のデータの削除や、データの挿入が楽
配列の場合、途中にデータを挿入したり、途中のデータを削除した場合、後ろのすべてのデータを移動させなければいけないので効率が悪い
2分探索木の説明
詳細な説明はここでは割愛
また、データの検索が早い
データの追加や削除も容易
大体こんな感じです。
5章～8章の内容はこちら。
9章～12章の内容はこちら。
おわり。