いつ決まるの？後でしょ！！ データの格納方法について[配列編]

はじめに

この文書は、javaを書き始めた人が最初に躓きそうなデータの持ち方について説明していきます。概念から段階的に詳細に落とし込んでいきますので、楽しく読んでみてください。貴方の理解の助けになったらうれしいな。

また、この文章は特定の言語実装、プロセッサの仕様を論じてはいません。あくまでも概念とアイデアの説明だと割り切って読んでください。

データを集合として扱う

データをひと固まりで扱いたいというのは昔からある欲求です。たとえば、小学校、あるクラスの出席状況。

boolean shuseki_hattarikun = true
boolean shuseki_kaibutsukon= false
boolean shuseki_magurafukuzo=false
.....
boolean shuseki_solu = true

でもいいんですが。

学級全員の出席を確認して出席した人の人数を知りたい

となると厄介なんですよね。こんな感じになります。

int shuseki=0;

if(shuseki_hattarikun){
    shuseki++;
}
if(shuseki_koibutsukon){
    shuseki++;
}
if(shuseki_magurafukuzo){
    shuseki++;
}
....
if(shuseki_solu){
    shuseki++;
}

これってもう、**自分の指折って数えたほうが早くね？**となるわけです。できればもっとすっきり書きたい。コンピュータはあほみたいに繰り返し強いので、繰り返しで書きたい。

int shuseki=0;

for(学級の生徒全員分){
    if(出席ナンバー){
        shuseki++;
    }
}

みたいに。つまり「学級」という集合で出席データを扱いたいという欲求が生まれてくるのです。

コンピュータ言語はこの「データを集合として」扱うための仕掛けとして、配列を用意しています。例えば出欠情報を「学級」の集合で扱いたい場合、配列を使うと。。。

public class Sample{
    private static final int HATTARI_KUN=0;
    private static final int KOIBUTSU_KUN=1;
    private static final int MAGURA_FUKUZO=2;
    …
    private static final int SOLU=36;
    public static void main(String[] args){
        boolean[] gakkyu = new boolean[37];

        /** 入力ブロック**/
        gakkyu[ HATTARI_KUN ] =true;
        gakkyu[KOIBUTSU_KUN] =false;
        gakkyu[MAGURA_FUKUZO]=true;
        gakkyu[SOLU]=true;

        /**集計ブロック**/
        int counter=0;
        for(int i=0;i<gakkyu.length;i++){
             if(gakkyu[i]){
                counter++;
             }
        }
    }
}

こんな風に書くことがでるわけです。では配列ってなんでしょう？「配列はいくつかの箱を並べて・・・」ってよく言われますね。でもそれなら配列以外の仕掛けと決定的に何が違うのかって話が見えなくなってくるので、もうちょっと解像度を上げてみます。

配列ってどういうこと？

古くからあるいわゆる配列は「同じ型」のデータを「一続きのアドレス」でメモリ上に格納するデータ格納方法です。配列関係の名称についておさらいすると。

boolean a[] = new boolean [10];

とした場合、プログラマが利用する形は以下の図の様になります。

それぞれの要素の名称と使われ方はこんな感じです。

No.	要素	名称	使われ方
1	a	配列の名前	プログラマはこの名称を用いて、プログラムを書く
2	0	インデックス(添字)	プログラマはこの値を用いて、利用するデータを決定します。以後indexと記載

で、多くのプログラマが意識していないのですが、indexを配列の「箱の番号」とか「箱の名前」とかざっくり理解しているわけです。さて「箱の番号」をもうちょっと解像度上げて見てみましょう。

boolean a[] = new boolean[10];

とすると、10個の箱が用意されると思ってしまいます。ちょうどこんな感じでしょうか。

でも、実は違います。 正確には「10個分のデータを格納できるメモリ領域」が用意される。のです。こんな感じ。

この「連続領域が用意されるだけ」ってのが割とポイントなんですよね。

箱の名前とか番号がなければ添字使ってアクセスできないじゃん？？ と思いますよね？それは正しい感覚です。ただ、配列からデータを取得する時に実際に何が行われているのかイメージすると、割と問題なくアクセスできる事が分かります。

データを使うということ

では、配列のデータを使うとはどういうことでしょうか？誰が使うのでしょうか？プログラマ？いいえ違います。プログラマは「この処理にはこのデータを使ってね」とお願いするんです。では、だれがこのデータを利用するのでしょうか。それは、プロセッサです。何かを処理する。つまりプログラムが動くということは、

1. プロセッサがやるべきことを命令列から取得するする。(インストラクションフェッチ)
2. プロセッサがやるべきことを理解する。（インストラクションデコード）
3. プロセッサが処理実行を開始する。（実行）
4. プロセッサが処理に必要なデータを取得する。(メモリフェッチ)
5. 実行結果をメモリに書き戻す。（ライトバック）

この5段階で実行するのです。配列からのデータ取得と書き戻しは4. 5.になります。今回はこの4. 5.の解像度を上げていきます。

まず、プロセッサが何も教えずにメモリに対して「データ頂戴」っていってみます。もちろん、「どのデータ」だか分からないので、データを取得することなんてできません。

主記憶からデータを持ってくるためには、そのデータが格納されているメモリ上の「アドレス」を教えてあげる必要があります。

プロセッサが命令を実行するためには、データをプロセッサが直接触れる場所「レジスタ」に乗せる必要があります。最終的にはデータをレジスタに載せてあげて処理を実行することが目的です。ところが、主記憶空のデータ転送はとてもコストのかかる作業（物理的に遠い）ので、よく使うデータはキャッシュとしてとっておきます。だからメモリフェッチは

1. 対象アドレスのデータが既にキャッシュに乗っていないか確認する
2. キャッシュにのっていればその値をそのまま使う。なければあらためて主記憶上の指定アドレスからデータを取得します。(開始のアドレスとデータのサイズで取得)
3. 取得した値をキャッシュに設定し、
4. 最終的にレジスタに載せて、実行の準備は完了します。

の手順で行われます。つまり、データの「場所」を示すアドレスとそのデータのサイズが分かればデータのフェッチは可能なのです。 ¹

配列のイメージと実体

さて、話を配列に戻しましょう。一般的なドキュメントとか、入門書で書かれている、配列のイメージってこんな感じじゃないですかね？

まるでa[] が並んだ箱全体を表してるかのような書かれっぷりで、a[0],a[1],a[2]...と別の変数がくっついているように見える。でもね。これa[]は配列=つまり連続したメモリ上の領域の開始位置の情報だけで、[0][1][2]も **箱の名前なんかじゃないんです。**ちょうど↓の感じ。

**それぞれの箱に名前がなくてなんでデータを格納したり、とり出せたりするの？**と思ったそこのあなた！！！すばらしい疑問です。次はその話に移りましょう

配列のデータを使おう

配列の添字ってindexっていうんですよね。indexって本の索引の事ですよ。気にする人少ないですがこれすごく大事な情報なんです。本を思いだしてください。indexから必要なことが書いてあるページに行きたいんです。

1. 索引ページを開く
2. 必要なindexを探す。
3. ページを得る
4. 指定のページを開く

大事なのは2. 3. です。indexは必要な情報をえるための「ページ」そのものではないけど、indexを使えば、必要な情報を得ることができるんですよね。ヒントは 「情報のアドレスとデータの大きさが分かればデータは取得できる」という事実です。

booleanの例

boolean[] a = new boolean[10];

if(a[4]) {
//↑この値を取得してくることを考える。
}

を例に考えましょう。

前提条件

• bolean は2値(true or false)が必要なので1bitのデータ長とする。²
• true = 1 false = 0 とする。

データを取得しよう

まず、aを起点にして考えます。ここでのbooleanのデータサイズは1bitで しかも「配列は連続したメモ
リ領域」なので、単純に右側に1bitを4回分(14)ずらしてあげれば、対象のアドレスとなります。つまり。a + 14(0x***4)から、boolean の1bit分のデータ(0 or 1)を取ってきます。

intの場合

1bit booleanの場合の話は前述のとおりです。次はint型について見てみましょう。

int [] a = new int[10];

int sum  = a[4]+a[0];
               //↑ここの値の取得方法についてです。

前提条件

• int は 4byte=32bitで表現する
• 記載は16進表現とする。(0x は16進数表現ですよ。。の意味)

booleanとほぼ同じです。違うのは1つのデータのサイズが4byteと32倍になっていることです。(配列のデータサイズは320bit)

データを取得しよう

これも基本的な手順は同じです。

1. indexを利用して、何bitずらせばいいかを考える
2. 先頭アドレスa[] に 1の値を加算（右にずらす）して、データの始まるアドレスを決定する。
3. 2で決定したアドレスからデータ長分（今回は4byte=32bit)取り出す。

実際にやってみましょう。

1. index=4 データ長　4byt=32bitですから、4*32=128(16進表記で0x0080)
2. 先頭アドレス0x000に1で割り出した値、0x0080を足す。= 0x080
3. 0x080 ～0x09Fの32bit分のデータ取得する

配列のメリット・デメリット

配列の仕掛けは分かってきましたね。ここから考えられる配列のメリットとデメリットは

メリット

• 機能実装が容易
• 高速に動作する

機能実装というのはアプリケーションプログラマから見た視点ではありませんよ？言語処理系として機能実装が容易であるということです。だって、「アドレスとindexと型おしえてくれ。あとは決まりに従って「ずらす」から。」って相当簡単ですからね。

また、実装自体がシンプルなのでデータ取得、書き込みの動作も高速です。

デメリット

• サイズの動的変更ができない
• プログラムの可読性が悪い

最初に連続した領域を確保するので、あとから変更できません。「変更すればいいじゃん」と思われるかもしれませんが。1つの配列でメモリ使ってるわけじゃないので、後ろ側に余裕がない場合拡張できません。「後ろが空いてたら」とかチェックするのもあれなので、「できない」としているのでしょう。

まとめ

ホントはマップまで行きつきたかったのですが長くなりすぎるので、分割していきます。

• データを集合として扱う基本的なやり方は配列だよ
• 配列は箱と名前がくっついたものじゃないよ
• 配列は指定数のデータを格納できる連続したメモリ空間だよ。
• 先頭アドレスと、ずれを表すindex、データ型（サイズ)がわかれば、データを取り出したり格納したりすることは可能だよ。
• 連続していないといけないら、実行時にサイズを変えることはできないよ。

最後になりますが、処理系によって例えばperl等のようにアドレス+index方式の「配列」を持たない言語もあります。どの言語の実装もこうではありませんので。概念とアイデアの理解のためにご活用ください。

1. 書き戻しはおおむね呼び出しの逆ですので今回は詳細の記載を省きます。 ↩

2. 実際には実装の都合上1byte=8bitが利用される。 ↩