Manhattan life

ここまでで、Javaコア・パッケージで提供されているデータ構造について一通り紹介しました。C/C++やJavaのようなライブラリ指向の言語 では、実証されたライブラリ提供のコードを組み合わせて使うべきであり、濫りに自分でアルゴリズムを考案したり実装することは厳重に慎むべきです。しかし ながら、そこで実装されているアルゴリズム／データ構造の動作特性をコードレベルで理解していないと、適材適所に活用することはままなりません。ここで は、データ構造に特異なアルゴリズムとして、並べ替え（ソート）と探索（サーチ）について紹介します。

整列

要素を並べ替えるアルゴリズムには多くのものがあり、代表的なものには挿入ソート(Insertion Sort)、櫛ソート(Comb Sort)、シェルソート(Shell Sort)、バブルソート(Bubble Sort)、クイックソート(Quick Sort)、マージソート(Merge Sort)、ヒープソート(Heap Sort)などが挙げれれます。ここでは、最も基本的なアルゴリズムとしての挿入ソートと、コア・パッケージでも実装している高級なアルゴリズムとしての マージソートを紹介します。

挿入ソート

極めて簡単なソート方法で、実行時間は要素の個数の二乗に比例します。例えば、{1,7,8,5,9,2}という配列があるとき、先頭から逐次的に 評価して、前のものよりも小さい要素である5を取り除き、5より大きな要素を後ろにまわして{1,5,7,8,9,2}とします。同じく、2を取り除き、 {1,2,5,7,8,9}として並べ替えが完了します。要素がオブジェクトである場合は、当該オブジェクトは、インタフェース java.lang.Comparableを実装して、「自然順序付け(natural ordering)」と呼ばれる順序をサポートしている必要があります。コア・パッケージの多くのクラスはComparableを実装していますが、自分 で作ったクラスの場合は、Comparableを明示的に実装する必要があるかもしれません。

class InsertionSortDemo {
	public static void main(String[] args) {
		int[] src = {1,9,8,6,5,3};
		for (int i = 0; i < src.length; i++) {
			int j, w = src[i];
			for (j = i; j > 0 && src[j - 1] > w; j--) {
				src[j] = src[j - 1];
			}
			src[j] = w;
			for (int k = 0; k < src.length; k++) {
				System.out.print(src[k] + " ");
			}
			System.out.println("");
		}
	}
}

要素数が10個未満程度の並べ替えであれば、挿入ソートで十分だといえます。特に、a[j - 1] > wによる繰り返しの回数に着目すると、順序が逆転している場所が少ない場合は極めて高速であることが分かります。要素数3つの場合は極めて直感的なのです が、そこまでブレーク・ダウンする前に挿入ソートのアルゴリズムの利用が検討できるはずです。

>javac InsertionSortDemo.java
>java InsertionSortDemo
1 9 8 6 5 3
1 9 8 6 5 3
1 8 9 6 5 3
1 6 8 9 5 3
1 5 6 8 9 3
1 3 5 6 8 9

挿入ソートは、殆ど整列したリスト型データ構造の場合は極めて高速であり、後続で紹介するマージソート、クイックソートと組み合わせることで、パフォーマンスの劇的な向上が期待できます。

マージソート

マージソートでは、整列すべき配列を中央で二つに分けて、更に半分に分けて要素一つになるまで分割していくことで並べ替えを実施して、各々を併合す るときに並べ替えます。つまり、並べ替えたい配列鋳型のデータ構造に対して、前半部分と後半部分を別々に並べ替えて、最後に各々を順番を保持するように併 合するアルゴリズムとなります。

例えば、要素が一つならば、何もしません。二つならば、二つのに分けて、小さい方を前に、大きい方を後ろに置くことで並べ替えられます。三つであれ ば、一つと二つの前半と後半に分割して、要素が二つの方を、先ほどと同じく並べ替え、一つの方には何もしません。並び替えられた二つの要素からなる配列に 対して、適切な順序にもう一方の一つの要素を挿入します。四つの要素の場合は、前半と後半の二つずつの要素に分割して、各々を並べ替え、最後に適切な順序 にマージ（併合）します。五つの場合は三つと二つに分割してソートすることになるので、それ以上要素数の場合も同様のアルゴリズムで並べ替えが可能という ことになります。帰納法的には、要素数が二つの場合の並べ替えを定義して、三つの場合の併合方法を定義できれば、四つ以上の分割方法は、それらの再帰的な 繰り返しになるため、任意の要素数の配列型データ構造の要素をソートできるようになります。

コア・パッケージでは、配列に対する高級な操作を提供するクラスjava.util.Arraysで実装しているstaticメソッドsort (Object[] a)や、コレクション・クラスのユーティリティ・クラスであるjava.util.Collectionsが実装するsort(List list)で利用されています。

マージソートのロジックの例を挙げると、次のリストのようになります。

public static void mergeSort(Object src[], Object dest[],
                              int low, int high) {
	int length = high - low;
	// 要素が2個以下になったら並べ替え
	// ここでは二つの要素の大小を比較して入れ替えているが、
	// 実際には10未満程度の十分小さな要素数になったら挿入ソートなどで並べ替えることで高速になる
	if (length <= 2) {
		for (int i=low; i

探索

データ構造に密接に関係するアルゴリズムとして、ソートのほかに探索（サーチ）が挙げられます。探索とは、要素の集団の中から、指定した要素を探し 出すことです。最も単純な方法は、要素を一つずつ取り出して、指定した条件に一致するかどうか評価する方法が挙げられます。これを逐次探索法 (Sequential Search)と呼びます。ここでは、より現実的なアルゴリズムとして、二分探索法(Binary Search)と自己組織化探索法(Self-organizing Sequential Search)を紹介します。他にも、補間探索法(Interpolation Search)、ハッシュ法(Hashing)、二分木探索法(Binary tree search)、B-treeなど、低級なものから高級なものまで膨大に挙げられます。

二分探索法

二分探索法は、ソートされた一次元のリスト型データ構造を高速に探索する方法です。要素が何らかの順番でソートされたリスト構造は頻繁に利用される ので、いたるところで実装されているアルゴリズムです。コア・パッケージでは、クラスArraysのbinarySearch()、クラス CollectionsのbinarySearch()などで実装されています。

まず、中央の値との大小を比較して、大きければ後半の中央値と比較します。小さければ前半の中央値と比較します。これを繰り返して、目的の値を探索する方法です。アルゴリズムの香りのするものでは、最も単純なものの一つです。

public static int binarySearch(int[] a, int key) {
	int low = 0;
	int high = a.length-1;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (a[mid] < key) {           // キーよりも中央値が小さければ
			low = mid + 1;            // 上半分を探索
		} else if (a[mid] > key) {    // キーよりも中央値が大きければ
			high = mid - 1;           // 下半分を探索
		} else {                      // キーと中央値が等しければ
			return mid;               // 発見した要素の索引番号を返す
		}
	}
	return -(low + 1);                // 見つからなければ負値を返す
}

自己組織化探索法

要素数がそれほど多くない、順序が不定のリストであれあば、先頭から順番に評価して探し出す、逐次探索（線形探索）が便利です。しかし、先頭から順 番に要素を探していくので、後ろにあるものほど時間が掛かることになります。自己組織化探索法は、自分自身の要素の並び順を探索試行毎に入れ替えて、より 頻繁に探索されるものほど先頭に置かれるようにします。

複数の要素が無作為に保持されているリスト構造の場合は、頻繁に探索されるものと、稀にしか探索されないものがあるものです。頻繁に探索される要素 をできるだけ高速に探索するためには、探索された要素はその都度先頭に配置することが最適です。しかし、一度探索されただけで先頭に置かれてしまうので、 稀にしか探索されない要素がたった一度探索されただけで一等地の先頭に移動してしまいます。このようなことがたまたま繰り返されると、頻繁に探索される要 素が順次後ろ送りになって、期待したパフォーマンスが一時的に阻害されることになるかもしれません。これを避けるために、探索される毎に一つ前に移動する という方法も考えられます。ここで、前者の、先頭に送る方法は先頭移動法(move-to-front method)と呼び、後者の、一つ前の要素と入れ替える方法は置換法(transpose method)と呼ばれます。

ここでは先頭移動法のコード例を紹介します。先頭移動法では先頭に要素を挿入することになるので、Javaのデータ構造では、配列やクラスArrayLisyよりも、クラスLinkedListを使った方が高速です。

public static LinkedList organizingSearch(LinkedList list, Object key) {
	int i = 0;
	int max = list.size() - 1;
	list.add(key);                        // リストの最後にキーと同じ要素を番人を追加
	while (!list.get(i).equals(key)) {    // キーと同じ要素に遭遇するまで全要素を比較
		i++;
	}
	list.remove(max + 1);                 // 番人を削除
	
	if (i > max) {                        // 番人であれば
		return null;                      // null を返す
	} else if (i != 0) {                  // 先頭でなければ
		list.addFirst(list.remove(i));
		return list;                      // 要素を入れ替えてリストを返す
	} else {
		return list;                      // 先頭であればそのままリストを返す
	}
}

Javaに限らず、プログラミングではデータ構造が重要な役割を果たします。コレクション・フレームワークとは、Java 2でデータ構造を取り扱うための設計のことです。J2SE 1.3/1.4には、コレクション・フレームワークに基づいたクラス／インタフェースが大量に実装されていますが、数が多いので最初は戸惑うことも多いで しょう。

Q. コレクション・フレームワークとは何？

データの集合を扱うためのコア・パッケージです。次の図のインターフェースと抽象クラスを駆使して設計されており、実装クラスの変更が容易になっています。

図：コレクション・フレーワークのインタフェース

Q. コレクションション・フレームワークと古いAPIの違いは？

古いAPIは処理が遅く、データ構造の変更負荷が高くなります。

古いデータ構造のインタフェース／クラスは、コレクション・フレームワークの導入に伴い、以下のように後継となるインタフェース／クラスが追加されました。

• 可変長配列：Vector→ArrayList
• ハッシュテーブルの設計：Dictionary→Map
• ハッシュテーブルの実装：Hashtable→HashMap
• スタック：Stack→LinkedList
• プロパティ：Properties→パッケージjava.util.profsのクラス群
• 列挙のインタフェース：Enumeration→Iterator

古いコレクション・クラス自身も、それまでのJDKとの互換性を保ちつつ、コレクション・フレームワークの枠組みを満たすように再設計されたうえでパッケージに含められています。

古いデータ構造の特徴は、同期化されていることと、コレクション・フレームワーク以前のAPIをサポートされていることです。その結果、古いデータ 構造は、動作が遅く、ほかのデータ構造に変換しようとした際に手間がかかるかもしれません。このことから、データ構造を扱う際には、Java 2 SDK以降で導入されたコレクション・クラスの利用を検討するべきでしょう。

例えば、クラスVectorを使いたい場合は、配列やクラスArrayListなどを使えないかどうかを検討します。Vectorも ArrayListも、サイズが自動的に拡張される可変長配列ですが、サイズの拡張が不要ならば配列のほうが高速ですし、同期化の必要がないのならば ArrayListを使ったほうが高速なことがあります。

また、古いコレクション・クラスで古いAPIを使う場合は、別のデータ構造への変更負荷が大きくなります。コレクション・フレームワークにのっとる ことで、共通のインタフェースに従うことになるため、データ構造を変更する際に、コードの変更範囲を最小限度に抑えることが可能になります。

パフォーマンス、変更、一貫性の観点から、古いAPIではなくコレクション・フレームワークを使うことを強くお勧めします。

Q10. コレクション・クラスと配列はどっちが良い？

コレクション・クラスの方が高機能で柔軟ですが、配列の方が早いことがあります。

Listと配列の最大の違いはサイズが拡張可能であることです。事前にサイズの拡張を回避できるのであれば、ArrayListオブジェクトと配列 オブジェクトにはデータ構造上は、大きな違いはありません。クラスVectorでもArrayListでも、サイズの拡張は一次オブジェクトの生成と破棄 を含む負荷の高い処理なので、最初にオブジェクトを生成するときに、要素サイズを適切に見積もり、拡張を伴わないように配慮してください。

実運用時に近い環境でプロファイリングを行ったうえで、コレクション・フレームワークの一貫性と、配列の速さの間のトレードオフを考慮して、どちらを使うかを判断するということになります。

なお、配列でもクラスArraysを使うことで、二分探索（バイナリ・サーチ）や並べ替え（ソート）などのアルゴリズムを利用することができます。

Q11. EnumerationとIteratorの違いは？

Enumerationは古いAPIです。コレクション・フレームワークではIteratorを使います。Vectorなどの古いAPIでEnumerationが使えますが、他のコレクションへの変更時には、その部分のコードが使えなくなるので不便です（リスト3）。

▼リスト3

String[] products = {"TV", "Stereo", "Video", "Camera"};
int prodLen = products.length;
// ArrayListの生成
List prodList = new ArrayList(prodLen);
// リストへ要素を追加
for (int i =0; i < prodLen; i++) {
    prodList.add(products[i]);
}
// Iteratorの取得
Iterator prodIt = prodList.iterator();
// Iteratorから要素を取得
while (prodIt.hasNext()) {
    System.out.println(prodIt.next());
}

IteratorはEnumerationの後継です。Vectorを使う場合でもEnumerationは使わず、Iteratorを使います。Enumerationは、他のパッケージや古いクラスから要求されるときだけ使うことになります。

Iteratorはその途中にwhileループの真偽判定メソッドを含みます。メソッド呼び出しはスタックからヒープを探索するため、多くの場合、 少ない方がパフォーマンスは向上します。速度が重要なコードでは他の方法も検討してください。ArrayListの場合は、次のようにforループと get()メソッドの組み合わせが使えます。

for (int i = 0; i < proList.size(); i++) {
    System.out.println(prodList.get(i));
}

Q12. ArrayListに挿入を繰り返すと遅くなる？

リストに対する挿入、削除を繰り返す場合、LinkedListを使うと動作速度が向上することがあります。リストの途中の要素に挿入／削除が繰り返される場合、ArrayListは再配列を必要とするため、パフォーマンスが悪化します。

LinkedListの要素は前後の要素への参照を持ち、2重にリンクされたデータ構造（リンク・リスト）です。その結果、任意の要素へのランダムアクセスではArrayListの方が高速であり、順次アクセスや要素の挿入／削除ではLinkedListの方が高速です。

また、LinkedListには特定の索引への挿入／削除に特化したメソッドも用意されています。push()/pop()を使えばスタックにな り、addLast()/removeFirst()を使えば先入れ先出し(FIFO)キューになり、addFirst()/removeLast()を 使えば後入れ後出し(LILO)キューとして実装できます。

順次アクセス、途中への要素の挿入／削除が必要な場合はLinkedListの方が高速です。索引によるランダム・アクセスではArrayList が高速です。HashMapとLinkedHashMap、HashSetとLinkedHashSetでも同様のことが言えます。例えば、エントリー数 が増える場合は、HashMapよりもLinkedHashMapの方が高速なことがあります。

Q13. IteratorとListIteratorの違いは？

コレクションはIteratorを使うためのインタフェースを備えていますが、List実装クラスではListIteratorインタフェースも使えます。ListIteratorでは、要素の削除／置換／追加のほか、2方向のカーソル移動をサポートします（リスト4）。

▼リスト4

import java.util.*;
class ListIteratorDemo {
    public static void main(String[] args) {
        String[] products = {"TV", "Stereo", "Video", "Camera"};
        int prodLen = products.length;
        // ArrayListの生成
        List prodList = new ArrayList(prodLen);
        // リストへ要素を追加
        for (int i =0; i < prodLen; i++) {
            prodList.add(products[i]);
        }
        // ListIteratorの取得
        ListIterator plit = prodList.listIterator();
         
        String s;
        plit.next();    // | TV
        s = (String)plit.next();    // TV | Stereo
        // 直前のnext()が返した要素を削除
        plit.remove();  // TV | Video
        plit.next();    // TV Video | Camera
        // カーソルの直前に挿入
        plit.add(s);    // TV Video Stereo | Camera
        plit.next();    // TV Video Stereo Camera |
        s = (String)plit.previous();    // TV Video Stereo | Camera
        // 直前のprevious()が返した要素を削除
        plit.remove();  // TV Video Stereo |
        plit.previous();    // TV Video | Stereo
        plit.previous();    // TV | Video Stereo
        plit.previous();    // | TV Video Stereo
        plit.add(s);    // Camera | TV Video Stereo
        // Iteratorの取得
        Iterator pit = prodList.iterator();
        while (pit.hasNext()) {
            System.out.println(pit.next());
        }
    }
}

リスト4の出力結果は次のようになります。

Camera
TV
Video
Stereo

Q14. Setは何に使える？

Setは数学における集合の概念を定義します。特定のオブジェクトが、既存のオブジェクトの集合に含まれるかどうかを調べるときに便利です。

HashSetとTreeSetは、どちらも重複を許さない集まりである集合を定義するSetインタフェースの実装クラスであり、TreeSetは 要素がソートされる点が異なります。SetがListと異なるのは、その要素に重複を含まないことであり、数学上の集合の概念を実装するものです。そのた め、オブジェクトが集合に含まれるかどうかをチェックするには、HashSet.contains()の方がArrayList.contains()な どよりも、高速に実装されています。

Q15. コレクションの一部分だけ扱える？

コレクションの一部分を取り出して操作するためには、各々のクラスのメソッドを使います。

Listの場合

部分リストのビューを取得するメソッドが用意されています。

subList(int fromIndex, int toIndex)

fromIndex以上、toIndex未満の範囲の部分リストのビューを返します。

Setの場合

順序を持つTreeSetでだけ、部分集合のビューを取得できます。

headSet(Object toElement)

toElement（含まない）未満の要素からなる部分集合のビューを返します。

tailSet(Object fromElement)

fromElement（含む）以上の要素からなる部分集合のビューを返します。

subSet(Object fromElement, Object toElement)

fromElement（含む）以上、toElement（含まない）未満の要素からなる部分集合のビューを返します。

Mapの場合

TreeMapでだけ、ハッシュ全体の部分ハッシュのビューを取得できます。そのメソッドはTreeSetの場合とほぼ同じです。というのも、TreeSetのコンストラクタでは、実はTreeMapを使ってインスタンス化しているからです。

headMap(Object toKey)

toKeyより小さいキーを持つ部分のハッシュのビューを返します。

tailMap(Object fromKey)

fromKeyより大きいキーを持つ部分のハッシュのビューを返します。

tailMap(Object fromKey, Object toKey)

キーがfromKey（含む）からtoKey（含まない）までの部分のハッシュのビューを返します。

最後に配列の場合を紹介します。部分配列の取得には、System.arraycopy()が使えます。System.arraycopy()は5 つの引数を持ち、それぞれ、順番にソース配列、ソース配列の要素の索引の開始位置、転送先配列、転送先配列内の開始位置、コピーされる要素の個数になりま す。これは別の配列の生成なので、ソース配列と転送先配列の間に関係はありません。forメソッドでも同じことができますが、こちらの方が高速です（リス ト5）。

▼リスト5

class ArrayCopyDemo {
    public static void main(String[] args) {
        // ソース配列
        Object[] src = {"Let", "there", "be", "light",
            ";", "and", "there", "was", "light"};
        int size = src.length;
        int srcPos = 6;
        int destPos = 0;
        int length = size - srcPos;
        // 転送先配列
        Object[] dest = new Object[length];
        // 配列のコピー
        System.arraycopy(src, srcPos, dest, destPos, length);
        for (int i = 0; i < length; i++) {
            System.out.print(dest[i] + " ");
        }
    }
}

リスト5の出力結果は次のようになります。

there was light

Q16. コレクションを同期化するには？

同期をとるオブジェクトの生成にはCollectionsクラスのファクトリ・メソッドを使います。 コレクション・クラスは同期化されていないから早いのだと強調してきましたが、複数のスレッド間で共有したいこともあります。複数スレッドからの同時更新 による不整合から保護するためには、synchronized()ブロックでくくっても良いのですが、生成時に同期化オブジェクトにラップすることで、煩 雑な作業を減らし、同期化し忘れることにも備えられます。

同期化のラップはCollectionsクラスのsynchronizedXxx()メソッドを使うことで、簡単に実現できます。コードの混乱を避けるために、コレクション・オブジェクトの生成直後に行うのが良いでしょう。

SortedSet ids = new TreeSet();
SortedSet unmodIds = Collections.synchronizedSortedSet(ids);

ここで生成されたunmodIdsはスレッド・セーフです。マルチスレッドの共有オブジェクトとして使うときにはunmodIds、同期化の必要が なければidsと使い分けることもできます。多くの場合は、共有オブジェクトだけが必要です。このときは、代入先をunmodIdsではなくidsにすれ ば、同期化されたオブジェクトだけしか存在しなくなります。

但し、こうして作ったオブジェクトは、Iteratorによる変更に対してはスレッド・セーフではありません！従って、Iteratorを使うときには、明示的にsynchronized()ブロックを使わなければなりません（リスト6）。

▼リスト6

import java.util.*;
class SynchronizedDemo {
    public static void main(String[] args) {
        // 同期オブジェクトの取得
        SortedMap customers = Collections.synchronizedSortedMap(new TreeMap());
        String[] names = {"Sugai", "Ito", "Ueda", "Kawai"};
        int[] ids = {1066, 5543, 9581, 2742};
        // キーと値の代入
        for (int i = 0; i < names.length; i++) {
            customers.put(names[i], new Integer(ids[i]));
        }
        // 同期化開始
        synchronized (customers) {
            Object obj;
            // Setビューで取得したキーのIterator取得
            Iterator i = customers.keySet().iterator();
            // イタレーション
            while (i.hasNext()) {
                obj = i.next();
                System.out.println(obj + ": " + customers.get(obj));
            }
        }
    }
}

リスト6の結果は次のようになります。

Ito: 5543
Kawai: 2742
Sugai: 1066
Ueda: 9581

Q17. コレクションを不変オブジェクトにするには？

不変オブジェクトの生成にもCollectionsクラスのファクトリ・メソッドを使います。

不変オブジェクトは、その名のとおりsetterメソッドなどの変更のためのAPIを持たないオブジェクトです。変更したければ、別のオブジェクト を生成して代入し直す他なく、不用意に作ると負荷が高くなるので、取り扱いには注意が必要です。ともあれ、生成したオブジェクトを外部から保護したいこと も良くあります。

不変オブジェクトの取得は同期化オブジェクトの取得と同様、Collectionsクラスを使います。

SortedSet branches = new TreeSet();
...branchesオブジェクトの編集
// 変更不能なビューの取得
SortedSet unmodBranches = Collections.unmodifiableSortedSet(branches);

例えば、外部にはunmodBranchesだけ提供して変更を許さず、内部ではbranchesを変更するというように使い分けができます。その ような使い分けが必要なく、一切の変更を禁止するためには、代入先をunmodBranchesではなくbranchesにすれば、変更不可能なオブジェ クトだけが存在することになります。

Q18. リストの検索は高速化できる？

並べ替えや検索のアルゴリズムは古くから研究されており、コレクション・フレームワークでもいくつか利用できます。ここでは、リストの要素の検索を高速にする2分探索法を紹介します。

2分探索法は、データがソートされているときに有効な探索法です。まず、データの中央の値と目的の値を比較し、上半分と下半分のどちらに含まれてい るかを決定します。仮に上半分であれば、先ほど中央に合った値の一つ上から最大の値までの間で中央の値をとり、目的の値と比較し、同じことを繰り返してい きます。

CollectionsクラスのbinarySearch()は、同じくCollectionsクラスのsort()メソッドなどでソート済みのリ スト・オブジェクトに対して、2分探索を実行します。ソート済みのリスト・オブジェクトの場合、通常はindexOf()よりも非常に高速です（リスト 7）。

▼リスト7

void insert(List list, Object obj) {
    // ソート
    Collections.sort(list);
    // 2分探索法
    // 存在すれば索引(≧0)。
    // 存在しなければ"- 挿入位置 - 1" (<0)。
    int index = Collections.searchBinary(list, obj);
    // 存在しない場合、挿入位置に挿入
    if (index < 0) {
        list.add(- index - 1, obj);
    }
}

プリミティブ型とラッパー・クラスの違いは？

数値、ブール代数、文字を表現するデータは、ラッパー・クラスと呼ばれる参照型のオブジェクトでも表現できます。しかし、これはオブジェクト生成を含むコストの高い方法です。

基本的なデータには参照型でない（オブジェクトでない）データ型が用意されています。プリミティブ型と呼ばれるこれらのデータ型には、対応するクラ スも用意されており、ラッパー・クラスと呼ばれます。ラッパー・クラスは、プリミティブ型データを格納する不変オブジェクトを生成します（表1）。

Javaアプリケーションは、メモリ上の、スタックとヒープと呼ばれる領域で実行されます。プリミティブ型データはスタックに格納されます。オブ ジェクトは、インスタンス（メソッドや型、及びデータ）がヒープに格納され、そのポインタがスタックに格納されます。ラッパー・クラス型オブジェクトよ り、プリミティブ型の方がメモリ・コストもパフォーマンスも良くなります。ラッパー・クラスでなければならない事情として、次のことが挙げられます：

• ラッパー・クラスのメソッドを使いたい。
• VectorなどのAPIに入出力したい。

他のクラスのメソッドから、オブジェクトが要求されているなど、止むを得ないとき以外は、ラッパー・クラスを使わない方が良いでしょう。

浮動小数点の比較は危険？

浮動小数点の計算結果は、数学的に完全に同じになることは滅多にありません。ほとんどの場合、微小な誤差を含んでいます。例えば、1.0 - 0.9 と 1.0/10.0 は異なり、0.1 は 10 回足しても 1.0 にはなりません。次の単純な例を見てください。

class FloatingDemo {
	public static void main(String[] args) {
		double d = 0.0;
		// 0.1 を 10 回加算
		for (int i = 0; i < 10; i++) {
			d += 0.1;
		}
		System.out.println(d);
		System.out.println(1.0 - d);
		// 16進数表現
		System.out.println(Long.toHexString(Double.doubleToRawLongBits(d)));
	}
}

>javac FloatingDemo.java

>java FloatingDemo
0.9999999999999999
1.1102230246251565E-16
3fefffffffffffff

コンピュータは内部的には二進数で表現して演算しています。つまり、小数の場合は、1/2 + 1/2² + 1/2³ + 1/2⁴ という形式で表現しています。10 進数で考えた場合と、殆ど、概ね、正確に変換できますが、ほんのわずかだけ異なることがあります。

例えば、0.1 の 10 倍は 1 です。float 型でも double 型でも同じです。しかし、先ほどの例で見たとおり、0.1 を 10 回足しても、わずかに 1 に足りません。例えば、0.1 を 2 進数で表現すると次のようになります。

100110011001100110011001100110011001100110011001...

これを 2 の累乗の分数で表現すると、次のようになります。

1/10 = 1/16 + 1/32 + 1/256 + 1/512 + 1/4096 + 1/8192 + ...

これは無限級数であり、厳密な値を求めるためには、無限に演算する必要があります。

一般に、2 進数では、数を Σi ai · 2i (-∞ < i < ∞) という、2 の級数で表現するため、実際には途中で計算を打ち切ることになり、微小な誤差が生まれます。厳密な値との誤差を打切り誤差と呼びます。一般に、算術計算では切り捨て／四捨五入／切り上げが必要になることが殆どで、そのために生じる誤差を丸め誤差と呼びます。

よって、浮動小数点数同士を比較するときは、比較対照の絶対値に対して十分に大きな差による大小比較は安全ですが、== による等しいことの判断は危険です。簡単な計算の結果、等しくなるつもりでも、演算順序や値の受け取り方によって誤差が生じ、== の評価結果が変わってしまう可能性があるからです。

可能であれば、浮動小数点同士の比較は避けた方が無難です。一般には、次のような回避策が挙げられます。

• 10 の n 乗を掛けて整数にする
• クラス BigDecimalM などのラッパーを使う
• 丸め誤差が出ないようにする。（乗除算の順番を変えるなど）
• 出ても影響しないくらい大きく比較する（相対誤差で有為な値を求めるなど）

もっと厳密に計算できる？

浮動小数点に関する誤差は、二進数と十進数の差に起因するもので、BigDecimalクラスを使うことで回避できます。

一般に、算術計算時には様々な誤差が発生します。古くから計算機の計算結果を正しく評価する試みが続けられてきました。注意が必要な代表的な誤差には次のものがあります。

オーバーフロー／アンダーフロー（桁あふれ）

大き過ぎたり小さ過ぎたりする数値が、表現できる桁からはみ出ること

丸め誤差

無限小数などを有効桁内に収めるための、切り捨て／四捨五入／切り上げなどによって生じる誤差

打切り誤差

無限に演算する必要があるものを、有限回数で打ち切ることによって生じる誤差

桁落ち

絶対値が微小な差しかない数値間での加減算で、結果が有効数字の桁より小さいために、無意味な出力が得られること

情報落ち

絶対値の大きな数と小さな数の間の加減算で、有効数値の桁より小さい数値が計算結果に含まれないために、出力が無意味となること

java.mathパッケージの BigInteger や BigDecimal は、これらの問題を解決する一つの方法です。

BigInteger と BigDecimal は、String やラッパー・クラスと同様、不変オブジェクトです。BigInteger は任意精度の整数を表現することができます。BigDecimalは任意精度の符号付小数点数を取り扱え、丸め誤差を制御できます。

Javaのプリミティブ型では、浮動小数点数はIEEE 754規格の2進数で表現されます。これは要するに、小数を2のn乗の級数で表現する方法の一つであり、float型の32ビットや倍精度のdouble 型64ビットを、何のために何ビット使うかを指定したものです（図1）。

図1. IEEE 754規格倍精度浮動小数点数（数値は光速度[m/s]）

BigDecimal を使えば、任意精度の小数を厳密に表現できます。指定した精度の桁数内で、厳密な結果を保証し、計算時に丸めモードを定数として指定することで、丸め誤差を制御できます（表2）。

BigDecimal では四則演算をメソッドで実行します。例えば、BigDecimal の値 a を同じく b で割るとき、丸めモードを ROUND_DOWN で実行する場合は次のようになります。

// a/bの実行
a.divide(b, BigDecimal.ROUND_DOWN);

有効数字の指定は簡単で、コンストラクタに与える引数の桁数で揃えられます。例えば、リスト1を見てみましょう。ここでは、rate が 0.250、掛け算対象の unit は 1 で初期化しています。一方が小点数以下 3 桁、一方が 0 桁なので、この場合の計算結果は小点数以下 3 桁で出力されます。この結果にもう一度 unit を掛けると、両方とも 3 桁になりますので、結果は 6 桁になります。以下、乗算の都度 3 桁ずつ増えていき、無限に桁が出力されることになります。

▼リスト1

// java.math.BigDecimal の import
import java.math.*;
class BigDecimalDemo {
    public static void main(String[] args) {
        // インスタンス化
        BigDecimal rate = new BigDecimal("0.250");
        BigDecimal unit = new BigDecimal("1");
    	
        for (int i = 0; i < 10; i++) {
            // BigInteger 型オブジェクトの乗算
            unit = unit.multiply(rate);
        	System.out.println(unit);
        }
    }
}

リスト1の実行結果は次のようになります。

0.250
0.062500
0.015625000
0.003906250000
0.000976562500000
0.000244140625000000
0.000061035156250000000
0.000015258789062500000000
0.000003814697265625000000000
0.000000953674316406250000000000

桁数を指定できることは便利なのですが、逆に言うと、この桁数の指定が足りないと、ROUND_HALF_DOWN などでばっさりと数字が落とされるので、無意味な結果が得られることもあります。そのため、設計の時点で、有効数字が何桁あれば良いのか、計算結果が何桁 になるのかを正しく把握しておくことが重要です。

プリミティブ型ではサイズが小さい、精度が低い、丸め誤差が許容できないという場合には、BigInteger、BigDecimal の利用を検討します。但し、不変オブジェクトであることに起因する、オブジェクトの生成とコピーの繰り返しが発生します。そのため、サイズも計算速度もプ リミティブ型よりも格段に悪化します。パフォーマンスと精度のトレードオフであることを理解した上で使ってください。

最小の値はいくつ？

最小の正の整数は、プリミティブ型の浮動小数点数では、MIN_VALUE で指定できます。

最小の表現なのでビット列だと "1" です。32 ビットの float 型だと 1.4E-45 で、64 ビットの double 型だと 4.9E-324 です。これより小さい値は 0 と区別できません。

次のコードは、この考え方で、float 型と double 型の最小の正の整数（0 と区別できる最小の正の整数）を計算するものです。確かにビット 1 に対して、求める値が計算できることが確認できます。

class FloatingEpsilon {
	public static void main(String[] args) {
		float fe = 1.0F;
		while (fe / 2.0F > 0) {
			fe = fe / 2.0F;
		}
		String intBits = Integer.toBinaryString(Float.floatToRawIntBits(fe));
		System.out.println(fe);
		System.out.println(intBits);

		double de = 1.0;
		while (de / 2.0 > 0) {
			de = de / 2.0;
		}
		String longBits = Long.toBinaryString(Double.doubleToRawLongBits(de));
		System.out.println(de);
		System.out.println(longBits);
	}
}

C:\java>javac FloatingEpsilon.java

C:\java>java FloatingEpsilon
1.4E-45
1
4.9E-324
1

x > y のとき、x - y >= + ε である最小の正の数 ε は仮数の基数と桁数に依存して決定し、 MIN_VALUE とは異なります。 1 + ε > 1 である最小の ε は次のようになります。64 ビット以上の浮動小数点数を計算可能なマシンでは、CPU によらず同じ値が得られます。MIN_VALUE よりもだいぶ大きいことに注意してください。

class MachineEpsilon {
	public static void main(String[] args) {
		float fe = 1.0F;
		float f = 1.0F + fe;
		while (f > 1.0F) {
			fe = fe / 2.0F;
			f = 1.0F + fe;
		}
		String intBits = Integer.toBinaryString(Float.floatToRawIntBits(fe));
		System.out.println(fe);
		System.out.println(intBits);

		double de = 1.0;
		double d = 1.0 + de;
		while (d > 1.0) {
			de = de / 2.0;
			d = 1.0 + de;
		}
		String longBits = Long.toBinaryString(Double.doubleToRawLongBits(de));
		System.out.println(de);
		System.out.println(longBits);
	}
}

C:\java>javac MachineEpsilon.java

C:\java>java MachineEpsilon
5.9604645E-8
110011100000000000000000000000
1.1102230246251565E-16
11110010100000000000000000000000000000000000000000000000000000

1.1102230246251565E-16 という数は、このページの最初の方で一回出てきました。0.1 を 10 回足した値と 1.0 との差異が同じ値です。つまり、この値以下の値は 1.0 との差として認識できないという閾値になっていることが分かります。

浮動小数点数の比較では、2つの数が完全に同じになることはまずありえないので、相対誤差がある値以下だったら等しいものと考えます。「ある値」の最小値が ε です。

絶対誤差 = | x - y |,

           | x - y |
相対誤差 = ---------
               y

例えば、x = 3.1415, y = 3.14 の場合、絶対誤差 = 0.0015, 相対誤差 = 4.7747891134808212637275187012574e-4 （約0.0048）です。

J2SE 5.0 以上では、BigDecimal.ulp() を用いて、最終桁単位 (unit in the last place) のサイズを得られます。その桁内の最小刻み幅（この値と、次に大きい絶対値および同じ桁数を持つ BigDecimal 値の間の正の距離）を返してくれます。その桁内では、その戻り値よりも小さな値 0.5ulp 以下は区別できません。1なら刻み幅 ulp は1であり、1.0なら刻み幅は0.1です。

import java.math.BigDecimal;

class MachineEpsilonUlpDemo {
	public static void main(String[] args) {
		BigDecimal unit = new BigDecimal(Double.MIN_VALUE);
		System.out.println(Double.MIN_VALUE);
		System.out.println(unit.ulp());
	}
}

C:\java>javac MachineEpsilonUlpDemo.java

C:\java>java MachineEpsilonUlpDemo
4.9E-324
1E-1074

数値計算における相対誤差、最終桁単位 (ulp)、マシン・イプシロン (machine epsilon) については、詳しくないのでこれ以上説明しません。他のページを参照してください。

数値のフォーマットは指定できる？

BigDecimalなどで結果が厳密なことは良いことなのですが、帳票印刷などで出力枠の桁数が決まっている場合には、そのままでは使えません。 このようなときは、java.text.NumberFormat とそのサブクラスである java.text.DecimalFormat を使ってみましょう。

リスト2は年間の利子0.000300から月ごとの利子を計算し、12ヵ月分の残高を計算したものです。月利を算出するときに丸め誤差を ROUND_HALF_DOWNで計算しています。何も指定しなければ、計算するごとに6桁ずつ増えていくはずですが、それでは非常に不恰好です。ここで はフォーマットを指定して、利率はx.xxxx%、残高は￥x,xxxと出力されるようにしています。

残高では、getCurrencyInstance() メソッドによって、実行コンピュータのロケールから貨幣の出力フォーマットを取得しています。一方、% の出力では、DecimalFormat クラスを使って、自分でフォーマットを指定しています。

▼リスト2

// java.math.BigDecimal の import
import java.math.*;
// java.text.NumberFormatとjava.text.DecimalFormat の import
import java.text.*;
class BigDecimalDemo2 {
    public static void main(String[] args) {
    // インスタンス化
    BigDecimal rate = new BigDecimal("0.000300");
    BigDecimal MONTH = new BigDecimal("12");
        BigDecimal balance = new BigDecimal(100000000);
    // 丸めモード ROUND_HALF_DOWN を指定した除算
    BigDecimal monthlyRate = rate.divide(MONTH, BigDecimal.ROUND_HALF_DOWN);
        
        // 小数点以下4桁のフォーマットを指定
        NumberFormat nf = new DecimalFormat("0.0000%");
        
        // BigDecimal値をdoubleに変換し、フォーマットを適用
        System.out.println("年利: " + nf.format(rate.doubleValue()));
        System.out.println("月利: " + nf.format(monthlyRate.doubleValue()));
        // 当該コンピュータのロケールに応じた通貨単位のフォーマットを指定
        nf = NumberFormat.getCurrencyInstance();
        for (int i=0; i < 12; i++) {
            // 乗算
            BigDecimal interest = balance.multiply(monthlyRate);
            // 加算
            balance = balance.add(interest);
            // BigDecimalをdouble値に変換し、フォーマットを適用
            System.out.println("残高: " + nf.format(balance.doubleValue()));
        }
    }
}

リスト2の実行結果は次のようになります。

年利: 0.0300%
月利: 0.0025%
残高: ￥100,002,500
残高: ￥100,005,000
残高: ￥100,007,500
残高: ￥100,010,000
残高: ￥100,012,501
残高: ￥100,015,001
残高: ￥100,017,501
残高: ￥100,020,002
残高: ￥100,022,502
残高: ￥100,025,003
残高: ￥100,027,503
残高: ￥100,030,004

ロケールなどで既存のフォーマットが利用できるときはNumberFormat、単位などを独自にカスタマイズしたい場合は DecimalFormat を使いましょう。

数値判定の方法は？

入力値などが数値であるかどうかを判定したいことがあります。

• 正規表現 java.util.regex を使う
• Character.isDigit() を使う
• 例外 NumberFormatException をキャッチする

「例外を例外的事象の処理以外では使わない」というのは例外処理の鉄則です。しかし、isDigit() を使うためには小数の処理などが面倒です。ちょっとしたテスト・コードのときなどには、次のようにして例外をキャッチする手法が良く使われます。

class ExceptionPrintDemo {
	public static Integer formatInt(String value) {
		if (value == null) {
			return null;
		}
		try {
			return new Integer(value);
		} catch(NumberFormatException e) {
			e.printStackTrace();
			return null;
		}
	}
	public static void main(String[] args) {
		if (formatInt(args[0]) != null) {
			System.out.println(args[0] + "は整数です。");
		} else {
			System.out.println(args[0] + "は整数ではありません。");
		}
	}
}

>javac ExceptionPrintDemo.java

>java ExceptionPrintDemo 1
1は整数です。

>java ExceptionPrintDemo 1.1
java.lang.NumberFormatException: For input string: "1.1"
        at java.lang.NumberFormatException.forInputString(Unknown Source)
        at java.lang.Integer.parseInt(Unknown Source)
        at java.lang.Integer.(Unknown Source)
        at ExceptionPrintDemo.formatInt(ExceptionPrintDemo.java:7)
        at ExceptionPrintDemo.main(ExceptionPrintDemo.java:14)
1.1は整数ではありません。

システムにおいて文字列の処理は重要な機能です。Javaでも文字列操作の処理は重要であり、基本機能、正規表現、国際化などの役割を持つ標準クラ スが多数用意されています。ここでは、文字列処理に関わるパフォーマンス上の問題を解決する、基本的なクラスの使い方を紹介します。

Q1. StringとStringBufferの違いは？

String型オブジェクトは内容の文字列を変更できませんが、StringBuffer型オブジェクトでは可能です。

String型オブジェクトのように、内容／状態を変更できないものを不変オブジェクト(immutable object)と呼びます。文字列は頻繁に使われるオブジェクトなので、Java実行環境は特別な取り扱いをします。基本データ型の振る舞いに似せるため に、リテラル "〜" の記述により、オブジェクト生成が行われます。更に、記述した文字列リテラルが、既に生成された文字列と同じであれば、既存の文字列への参照が代入されま す。

例えば、

String str = "Hello";

の場合、"Hello"という文字列が既に存在しないか調べます。存在すれば、strには作成済みの同じ文字列への参照を代入します。存在しなければ、新たにプールして、その参照を代入します。

オブジェクトの生成はコストが高い処理なので、オブジェクトをプールして再利用するこの方法は非常に効果的です。

StringBuffer型オブジェクトのように、内容が変更可能なものを可変オブジェクトと呼んで不変オブジェクトと区別することがあります。変 更用の余分なメモリ領域（つまりバッファ）を持っているので、String型オブジェクトに比べると、メモリ領域を余分に消費することになります。

しかし、StringBuffer型オブジェクトは、バッファ内で不定長の文字列を操作できるために、Stringオブジェクトのように、変更の都度、一時オブジェクトを生成する無駄がなくなります。

一般に、参照型変数に代入された不変オブジェクトを変更するには、別のオブジェクトの生成、新しい参照の代入、古いオブジェクトの破棄という手順が 必要になります。一方、可変オブジェクトの変更は、既存のオブジェクト用のメモリ領域内での作業です。このため、不変オブジェクトの変更はコストが高くな ると言えます。

変更しない文字列の代入にはString型オブジェクトが簡単です。変更する文字列にはStringBuffer型オブジェクトを使うことで、一時 的に生成されるオブジェクトの数を減らすことができます。不変オブジェクトの変更コストの高さは、Stringオブジェクトに限った話ではなく、Java のコア・パッケージ定義されている多数の不変オブジェクトに共通することです。

Q2. 文字列の連結で遅くなる？

+演算子で文字列の連結を繰り返していると、パフォーマンスが悪化することがあります。これを避けるためにStringBufferが有効です。

Javaの二項演算子の一つである+演算子は、文字列を演算対象としても機能するようにオーバーロードされています。二項のうち一方でも文字列であれば、連結子として機能します。例えば、

String str = "Java" + "World" + 2003;

となっていれば、strには"JavaWorld2003"が代入されます。文字列の連結では、メモリ消費量を抑制するために、コンパイル時に StringBufferのappend()を使うステートメントに変換されます。今の場合は、次のステートメントと等価になります。

String str = new StringBuffer().append("Java").append("World").append(2003).toString();

バッファを使うことで、一時文字列の生成を抑えています。自動的に行われる便利な仕組みなのですが、次の例を考えてみましょう。

String str = "Hello";
str = str + "World";
str = str + 2003;

先ほどの例とまったく同じことをしているように見えますが、コンパイル結果は次のステートメントと等価なバイト・コードとして生成されます。

String str = "Hello";
str = new StringBuffer().append(str).append("World").toString();
str = new StringBuffer().append(str).append(2003).toString();

都合三つのオブジェクトが作られています。オブジェクトの生成はコストの高い操作であり、パフォーマンス上好ましくありません。

文字列の連結操作は、一つの行内で行うべきです。ステートメントを分けてはいけません。止むを得ずステートメントを分けなければならないこともあるでしょう。例えば、次のようにブロック内で連結する場合です。

String str = "count";
for (int i =0; i < 100; i++) {
    str = str + i;
}

このようなときは、事前にStringBufferを生成して、ブロックの外でStringに変換します。

String str = "count";
StringBuffer sbuf = new StringBuffer(str);
for (int i =0; i < 100; i++) {
    sbuf.append(i);
}
str = sbuf.toString();

文字列の連結は一つのステートメント内（行内）で行い、複数ステートメントに分割される場合は、StringBufferを使います。

Q3. 文字列バッファのサイズは？

文字列バッファのサイズは自動的に拡張されますが、パフォーマンスの悪化を招くコストの高さを認識しておく必要があります。

StringBuffer型オブジェクトのサイズの省略時値は16です。足りなくなると、倍のサイズの別のオブジェクトが生成され、内容をコピー し、古いオブジェクトは廃棄対象になります。ここにもオブジェクトの生成と廃棄のプロセスが潜んでおり、パフォーマンスを悪化させます。

ほとんどの場合、必要なサイズが見積もれるはずなので、最初からバッファ領域の追加が発生しないように、オブジェクト生成時に指定しておいた方が良いでしょう。次の例は、必要となる最大サイズを500未満と見積もった場合です。

StringBuffer sbuf = new StringBuffer(500);

文字列バッファのサイズについて注意すべき局面があります。一般に、パフォーマンス向上の原則は、オブジェクトを生成しないことであり、そのために オブジェクトの再利用が推奨されます。しかし、StringBuffer型オブジェクトは再利用しない方が賢明です。StringBufferの文字列 バッファの容量は、一度増えたら減らないため、長期間にわたって再利用を繰り返すと、予想以上にバッファ・サイズが拡張されており、メモリ使用率をむやみ に圧迫する可能性があるためです。

StringBufferを使うときは、その都度必要なサイズを見積もって生成し、無闇に再利用を試みない方が良いでしょう。これは、StringBufferに限った話ではなく、自動的にサイズが拡張されるようなクラスについては等しく言えることです。

Q4. 文字列分割は簡単にできる？

クラスStringBufferは、文字列の連結をはじめ、文字列操作のための汎用的なメソッドを数多く備えており、文字列の操作に関しては万能です。しかし、文字列の分割について特化したクラスも存在します。それが、クラスjava.util.StringTokenizerです。

詳細については、APIドキュメントをご覧いただくとして、そこには、以下のような例が載っています。

StringTokenizer st
	= new StringTokenizer("this is a test");
while (st.hasMoreTokens()) {
	println(st.nextToken());
}

このコードでは、「this is a test」という文字列をクラスStringTokenizerのコンストラクタに渡しています。続くwhile文で使用しているメソッド hasMoreTokensは、分割した要素（トークン）を返せるのであればtrueを返し、さもなければfalseを返します。メソッド nextTokenは分割した要素を返し、次の要素へ移動します。文字列の分割に使う区切り文字（デリミタ）を指定していない場合、空白や改行文字がデ フォルトの区切り文字になります。このプログラムの出力は次のようになります。

this
is
a
test

もちろん、クラスStringTokenizerでは、コンストラクタに任意の区切り文字を渡すことができますし、戻り値に区切り文字自身を含めるかどうかを指定することもできます。 　StringTokenizerはとても便利なクラスですが、これを使用する際には注意が必要なケースがあります。典型的な例が、CSV（Comma Separated Value）形式のデータです。最も簡単なCSV形式のデータは次のようになります。

A,B,C

区切り文字としてカンマを指定すれば、「A」と「B」と「C」が得られます。それに対し、次のようなデータには工夫が必要です。

"A,B",C,D

このようにカンマを含む要素があると、「"A,B"」、「C」、「D」の3つの文字列ではなく、「"A」、「B"」、「C」、「D」の4つに分割さ れてしまいます。このような場合は、区切り文字を含んだかたちで分割し、さらにダブル・クォーテーションに対する条件分岐を使って文字を連結しなおす必要 があります。 　別法として正規表現の利用も検討できます。HTML, SQL, CSVなどで、特殊文字や改行文字を無効な文字に置換することをサニタイジング（無害化）と呼び、古くから正規表現で実現されてきました。Java 2 SDK 1.4以上であれば、パッケージjava.util.regexで実装されています。

簡単な場合にはStringTokenizerが便利です。パフォーマンス上の厳しい要件がある場合や、複雑なデータを取り扱う場合は、クラスStringBufferを使ったほうが有利です。J2SE 1.4以上では、パッケージjava.util.regexのほか、staticメソッドString.split()でも正規表現による文字列分割がサポートされています。