データ型とデータ構造まとめ

おことわり

筆者個人のアイデアを整理するために書いた記事です。

明確な出典があるわけではなく、内容の正確性は検証されていません。ご了承ください。

基本データ型

真偽値型

真偽値を 1 bit で表します。 0 が false、1 が true です。

引数としては分岐命令（GOTO 命令）に、演算結果としては比較命令に使用されます。

他のデータ型と異なり、 CPU 上ではフラグレジスタという専用のレジスタに格納されたものを使用します。

数値型

有限桁の 2 進数で表現できる数値を表現します。表現できる範囲や意味によってさらにデータ型が分かれます。

真偽値型（フラグレジスタ）が使用される場面以外ではあらゆる演算の引数、演算結果で使用されます。

符号

符号ありのものと符号なしのものがあります。

符号ありの場合、符号は最上位桁が 0 (+) か 1 (-) かで表します。負の数は 2 の補数で表現します。

小数

2 進数の列（基数）とは別に小数点の位置（指数）を指定することで小数を表現します。

データの後半の数 bit 使って小数点の位置（指数部）を指定する、浮動小数点という形式が一般的に使用されます。

2 の補数によって負の指数を表現することができます。

精度

数値表現に使用する bit 数が多ければ多いほど精度が出せます。

単精度 (32 bit) と倍精度 (64 bit) が主に使用されます。

浮動小数点数の指数部の開始ビット位置も精度によって異なります。

文字型

特定の文字コードで、その文字に対応する数値を保存します。

演算によって大文字と小文字を変換したり、別の文字コードで表現したバイナリに変換したりできます。

バイナリ型

0 と 1 の羅列で、任意のバイナリデータ（圧縮データ、暗号データなど）を表現します。

ポインタ型（メモリアドレス型）

メモリ上の位置をチャンク単位で指し示す符号なし整数です。ハードウェアの設計によって 1 チャンクの長さ (byte 数) が異なります。

読み込み・書き込みの対象になるメモリ上の位置を指定したり、次に実行される命令の位置を指定したりします。

命令型

演算を指定するデータ型です。

メモリの連続領域に確保され、基本的に順に実行されます。

分岐命令（GOTO 命令）で引数の真偽値が true の場合は、指定のメモリアドレスに移動して次の命令を実行します。

データ構造

メモリ配列型（ベクトル型）

メモリ上に確保された固定長の連続領域に、同一データ型のデータを連続で格納します。

また、開始位置のポインタ、データ 1 つ辺りの長さ、要素数（または終了位置のポインタ）などのメタ情報を管理します。

一般的に文字型やバイナリ型はそれ単体で使用されず、メモリ配列型のデータ構造で使います。

多次元メモリ配列型（テンソル型）

メモリ上に確保された固定長の連続領域に、同一データ型のデータを連続で格納します。

ここまではメモリ配列型と同一ですが、多次元メモリ配列型は連続で格納されたデータを多次元に区切って管理します。

メモリ配列型のメタ情報をさらにメモリ配列に格納することで多次元を表現します。

3D描画処理やニューラルネットワークなどにも使用され、このデータ型を扱う処理が得意な専用のプロセッサ (GPU) があります。

連結リスト型

一連の複数のデータを、データと次のデータへのポインタで表現します。

メモリ配列型と異なり固定長である必要がないため、要素の切り取りや挿入が容易です。また、要素が同一のデータ型である必要はありません。

一方で、ポインタを使ったアクセスを繰り返す必要があるため、アクセス速度はメモリ配列型に劣ります。

構造体型

メモリ上の固定長の連続領域に、複数の異なる型の値を格納します。

それぞれの値には名前を付ける必要があり、メモリ確保のために事前に構造を宣言する必要があります。

マップ型（ハッシュマップ型）

複数のデータに名前（キー）を付け、データ（バリュー）にアクセスするためのポインタに紐づけます。

通常はキーに文字列型を使用しこれをハッシュ化して比較するため、ハッシュマップと呼ばれます。

マップ付き連結リスト型

連結リストを作成しつつ、各要素に対するマップも作成することで、互いの欠点を補いあうデータ型です。

連結リスト型の、「特定のデータを検索するために先頭から順にアクセスしなければならない」という欠点と、マップ型の、「要素を列挙することが苦手で、順序が保証されない」という欠点を解消します。

関数型

命令型とその開始位置を示すポインタ型で、命令の中に呼び出し元に戻るための GOTO 命令を持っています。

任意の数の引数と戻り値を指定することができ、これらの値はメモリ上の位置を呼び出し元と呼び出し先で共有することでやり取りします。

コールスタック

ポインタ型の連結リストで、関数の命令中に別の関数が呼び出される（= 開始位置への GOTO 命令が実行される）とき、移動元のメモリアドレスが末尾に追加されます。

移動先の関数の処理の最後に、コールスタック末尾のポインタに対して GOTO 命令が実行され、呼び出し元の位置（の次の命令）に戻ってきます。