導入

今回から「データ構造とアルゴリズム」という大きなテーマの中から、次の4つのトピックをとりあげます。

• 配列とコレクション
• サーチ
• ソート
• 再帰

現在主流となっているほとんどの高級言語やデータベースはこれらの仕組みをあまり意識しないで利用できるようになりました。むしろ下手に自作することは「車輪の再発明」と揶揄されてしまうぐらいです。

しかしながら、ソフトウェア開発の規模が大きくなるにつれ、用意された道具では足りない状況が生じてきます。そうなると車輪をカスタマイズすることになるでしょう。あるいは用意された道具の働きや速度に疑問がある場合、検証する知識が必要です。これらの内容はソフトウェアを専門とする学生が必ずクリアすべき関門です。

今回はその第1回目として「配列とコレクション」について説明します。

展開

配列からコレクションへ

どのプログラミング言語を学習する人も、複数の変数を調子よく取り扱うための仕組みとして配列を学習します。その後クラスやオブジェクトについて学び、便利なクラスの例としてArrayListやHashMapといったコレクションのクラスを学習するでしょう。配列とArrayListを比較すると、初学者の方には違いやメリット、使い分けの意図が分かりにくいものです。ここでは、その点に注目しながら説明します。

配列

配列（はいれつ）は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め、要素を区別します。配列によってまとめられた、一つひとつの変数を要素（ようそ）と呼びます。要素を区別するために添えた数字を添字（そえじ）と呼びます。

配列は大変シンプルで、コレクションクラスに比較すると必要とするメモリ量が少なく、アクセスが高速なことがメリットです。データを単純に格納して、順番に参照する程度の用途であれば、コレクションクラスに比較して配列のほうが有利です。

最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し、配列の添字を明記して要素に値を代入し、添字を指定して要素の値を呼び出します。

String[] names = new String[4];

names[0]= "Tim Bray";
names[1] = "Brian Kernighan";
names[2] = "Jon Bentley";
names[3] = "Karl Fogel";

for(int i = 0; i < names.length; ++i){
  println(names[i]);
}

上のコードは配列要素の設定に何度もnames[*] =を入力します。これが基本であることを確認した上で、無駄な入力を省くために次のような要素の値の代入方法が用意されています。

String names[] = {"Tim Bray",        // 0番目の要素
                  "Brian Kernighan", // 1番目の要素
                  "Jon Bentley",     // 2番目の要素
                  "Karl Fogel"};     // 3番目の要素

for(int i = 0; i < names.length; ++i){
  println(names[i]);
}

さらに、添字を指定して要素にアクセスする必要がない場合のために、拡張for文があります。拡張for文を使うことで、添字を指定するためのカウンタ変数を使用せずにシンプルに列挙できます。つまり、上のコードは次のFundamentalFor2.pdeのように書けます。

String names[] = {"Tim Bray",
                  "Brian Kernighan",
                  "Jon Bentley",
                  "Karl Fogel"};

for(String name : names){
  println(name);
}

配列のソートとサーチ

一つの名前でたくさんの値を取り扱うことができる配列は大変便利な仕組みです。しかし、配列に代入した値を特定の順番に並べ替える「ソート」や、目的の値の位置を探す「サーチ」などの仕事をするために、プログラマはコードを書かなければなりません。もちろん、配列を使わない場合に比べればずいぶん楽な仕事なのですが、それでも新しいコードを書くということは、バグを作成する可能性を生んでしまうのですから、なるべく避けたいところです。

毎度必要になるのが分かっている仕事をプログラマがその度に用意するのは効率がよくありません。そこで、これらの仕事をしてくれるメソッドをまとめたユーティリティクラスであるArraysが用意されています。Arraysクラスを用いると、およそ配列に必要な基本的な操作が、新たにコードを組むことなくメソッドを呼び出すだけで実行できます。

import java.util.Arrays;

String names[] = {"Tim Bray",
                  "Brian Kernighan",
                  "Jon Bentley",
                  "Karl Fogel"};

println("toString > " + Arrays.toString(names));
Arrays.sort(names);
println("* Sorted");
println("toString > " + Arrays.toString(names));
println("* Search");
println("Position of 'Jon Bentley' is " + 
        Arrays.binarySearch(names,"Jon Bentley") );

ソートやサーチについては次回以降で詳しく学習します。今回の演習では最も基本的なソートとサーチのコードを書く演習を示します。予習として取り組んでください。

コレクション

配列は変数に添字と呼ばれる番号を振ることで要素を区別しています。場合によっては添字が不要であったり余計であったりします。例えば、番号で区別するのではなく名称で区別したい場合があるでしょう。あるいはそもそも番号など必要なく、とにかく値を溜め込みたいだけという場合もあるかもしれません。それらに対応するために、コレクションという仕組みが考えられました。

また、実際的な問題として、配列は宣言したときに配列の長さ、すなわち取り扱うことのできる要素の数が決まってしまいます。いったん宣言すると、配列の長さを変更するためには「別の配列」を宣言しなければなりません。これは少々面倒です。コレクションは宣言した後で自在に大きさを変更し、要素の追加や削除が可能です。その他、便利なメソッドが数多く用意されています。

コレクションクラスを利用する場合の欠点は、少量のデータを格納して、順番に参照するだけのような用途に利用すると、必要のないメソッドのためのメモリ領域を消費することです。オブジェクトの生成にかかる時間も必要です。

通常、コードの読みやすさが最優先されるため、よほど実行速度を高速にする必要があるとか、ほんの少数の要素をすこしだけ取り扱いたいなどの場合の他は、なるべく配列以外のコレクションの仕組みを使いましょう。

コレクションについて、Java言語のバイブル『プログラミング言語Java』では次のように説明されています。

コレクション（collection）（⁠時には、コンテナー（container）と呼ばれます）は、効率的なアクセスのために有用な方法で、オブジェクトを保持してまとめる入れ物です。

『プログラミング言語Java』（⁠ピアソン・エデュケーション版）第4版、P.499より

この意味では、配列も広い意味でコレクションの一種です。Java言語の言語要素としてのコレクションは、同書のクラス継承関係図（P.500）に掲載されているクラス群です。ここでは図の引用は省きますので、各自で『プログラミング言語Java』の該当箇所をお読みください。以下にその図をリストに書き換えたものを示します。

* Iterable
    * Collection
        * Set
            * SortedSet 
                * TreeSet
            * EnumSet
            * HashSet 
                * LinkedHashSet
        * Queue
            * PriorityQueue
            * LinkedList
        * List
            * ArrayList
            * LinkedList
* Map
    * SortedMap
        * TreeMap
    * HashMap
        * LinkedHashMap
    * WeakHashMap
    * EnumMap
* Iterator
    * ListIterator

このリストの中から代表的なクラスを2つとりあげて紹介します。

ArrayList

ArrayListは配列のオブジェクト版です。配列に比較した最大のメリットは、要素追加・削除が自由自在なことです。

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

String n[] = {"Tim Bray",
              "Brian Kernighan",
              "Jon Bentley",
              "Karl Fogel"};
ArrayList<String> names = new ArrayList(Arrays.asList(n));


//配列と同様の方法、添字で要素にアクセスします。
println("* Access with FOR *");
for(int i = 0; i<names.size(); ++i){
  println(names.get(i));
}

names.add(1,"Eliotte Rusty Harold"); // 2番目位置に要素を挿入します。
names.remove(2); // 3番目の要素を削除します。

//コレクションクラスならではの方法で要素にアクセスします。
println("* Access with ITERATOR *");
Iterator<String> it = names.iterator();
while(it.hasNext()){
  println(it.next());
}

HashMap

HashMapは配列では簡単に出来ない事をあっさり実現してしまう便利なクラスです。添字の代わりに好きなデータをキー（key）として指定します。そしてそのキーに対応する値（value）を指定します。要素の呼び出しはキーを指定するだけです。この仕組みを配列から組み上げようとすれば、ずいぶん面倒でしょう。

HashMap hm = new HashMap();

hm.put("Brian Kernighan","A REGULAR EXPRESSION MATCHER");
hm.put("Karl Fogel","SUBVERSION'S DELTA EDITOR: INTERFACE AS ONTOLOGY");
hm.put("Jon Bentley","THE MOST BEAUTIFUL CODE I NEVER WROTE");
hm.put("Tim Bray","FINDING THINGS");

println("Get a Element > " + hm.get("Brian Kernighan") );
println("Get a Element > " + hm.get("Jon Bentley") );

インタフェイスの活用

さらに便利なことに、コレクションクラスはCollectionやMapというインタフェイスを実装しています。Java言語の仕組み上、インタフェイスのオブジェクトにはそのインタフェイスを実装したクラスのオブジェクトへの参照を持たせることができます。

次のスケッチのように、カチッ！カチッ！とコードを切り替えて、ほとんど同じコードで全く別のデータを取り扱えます。これこそコレクションクラスを利用するメリットです。もっと言えば、オブジェクト指向プログラミングのメリットです。

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

HashMap hm = new HashMap();
Map m;
m = hm;
m.put("Brian Kernighan","A REGULAR EXPRESSION MATCHER");
m.put("Karl Fogel","SUBVERSION'S DELTA EDITOR: INTERFACE AS ONTOLOGY");
m.put("Jon Bentley","THE MOST BEAUTIFUL CODE I NEVER WROTE");
m.put("Tim Bray","FINDING THINGS");

HashMap hm2 = new HashMap();
m = hm2;
m.put(1,123);
m.put(2,223);
m.put(3,323);

m = hm;
println("Get a Element from Interface m > " + m.get("Tim Bray") );
m = hm2;
println("Get a Element from Interface m > " + m.get(2) );

m = hm;
Set s = m.keySet();
for(Object o : s){
  println("Element is " + m.get(o) );
}
m = hm2;
s = m.keySet();
for(Object o : s){
  println("Element is " + m.get(o) );
}

演習

演習1（難易度：middle）

ArraysSortAndSearch.pdeをArraysクラスのメソッドを使用せずに、配列の要素をソートし、目的の要素の添字を検索するコードに書き換えてください。どれだけのコードを書くことになるかを再確認してください。ソートには直接選択法、サーチには逐次検索法を使いましょう。ファイル名はYourArraysSortAndSearch.pdeとしてください。

演習2（難易度：easy）

MapInterface.pdeのコード末尾にあるforループを切り分けましょう。そして、Mapインタフェイスを実装したクラスであれば何であれ、受け取って要素に格納された値を列挙するメソッドにしてください。ファイル名はUsefulMapInterface.pdeとしてください。

まとめ

• 配列はシンプルで高速なアクセスが可能です。要素数が少なく、ごく単純な操作しか必要ない場合に活用すると良いでしょう。
• コレクションは柔軟な取り扱いができるよう工夫された仕組みです。特に意味がなければ、配列ではなくコレクションを用いましょう。

学習の確認

それぞれの項目で、Aを選択できなければ、本文や演習にもう一度取り組みましょう。

1. 配列の仕組みと用途が理解できましたか？
   1. 理解できた。気持ちよく納得した。
   2. 理解できた。しかし、今ひとつスッキリしない。
   3. 理解できない。
2. コレクションの種類と用途を理解できましたか？
   1. 理解できた。
   2. 理解はできるがイメージがわかない。
   3. 理解できない。

参考文献

• 『プログラミング言語Java』（⁠ケン アーノルド、デビッド ホームズ、ジェームズ ゴスリン 著、東京電機大学出版局⁠）⁠
  • Java言語のバイブル。通読は大変ですが、Java言語を使う人は必携です。今回は本書の第21章を読むことを宿題にします（半分冗談です⁠）⁠。
• 『Java言語で学ぶ　デザインパターン入門』（⁠結城浩 著、ソフトバンクパブリッシング⁠）⁠
  • デザインパターンを学ぶなら、まず本書から。コレクションクラスに実装されたイテレータについて、本書のイテレータパターンの節を読むと理解が深まります。

演習解答

1. YourArraysSortAndSearch.pde
2. UsefulMapInterface.pde