「ソフトウェア演習(B)Java言語」
ベーシックコース

第5回 ジェネリクス, マルチスレッドプログラミング(代表的なアルゴリズム例)(深さ優先探索、ソーティングなど)

クラスの継承における抽象クラスとインタフェース(復習)

これまでクラスの継承を幾つかの例を通して説明してきました。 特に、基底クラスが抽象クラスやインタフェースの場合、これらの インスタンスを直接作れないため、以下のように、派生クラスのオブジェクトを 作成し、これを基底クラスの変数に代入する方法が主として使われます。

基底クラスの変数 = 派生クラスのインスタンス(オブジェクト)

ただし、抽象クラスやインタフェースであっても、以下のように、 (N個の)配列を作ることはできます。

Shape2D[] shapes = new Shape2D[N];

このあとは、たとえば

shapes[i] = new Circle(center, radius);

のように、派生クラスのオブジェクトを代入することが期待されます。

通常、抽象クラスには、抽象関数が含まれます。 たとえば、抽象クラスShape2Dの実装例を以下のように書いたとします。

import java.io.PrintStream;
public abstract class Shape2D {
     private String name; /* 形状の名前: (注)private変数にはできない  */
     public abstract double area(); /* 面積を求める抽象メソッド */
     public abstract double perimeter(); /* 周囲長を求める抽象メソッド */
     public abstract void psPrint(PrintStream pStr);/* PostScript形式でプリントする抽象関数 */
     private String getName(){ return name; }/* 形状の名前を返す:抽象関数ではない */
     public void setName(String name) { this.name = name; }     /* 形状の名前を設定する */
     public void printHead(PrintStream cout){
		cout.printf( "%% %s 面積 = %5.3f\n", getName(), area());
		cout.printf( "%% %s 周囲長 = %5.3f\n", getName(), perimeter());
	}
}
ここで、area(), perimeter(), psPrint()の3つの関数を抽象関数として定義しています。 抽象関数は抽象クラスで実体を定義しないで、プロトタイプだけ定義します。 派生クラス側では、これらの関数の実体を必ず定義する必要があります。 一方、抽象クラスには、抽象関数以外に、通常の関数や変数を書くことが出来ます。

これに対して、インタフェースは、通常の関数や変数は書くことはできず、 すべての関数は派生クラス側で定義します。たとえば、

public interface Shape2D {
     public abstract double area(); /* 面積を求める抽象メソッド */
     public abstract double perimeter(); /* 周囲長を求める抽象メソッド */
}
のようにShape2Dをインタフェースとすることもできます。 この場合は、派生クラスでは、

public class Circle implements Shape2D { }

のようにimplementsを使って定義します。 インタフェースは抽象関数しか定義できない一方で、C++の多重継承のように、 複数のインタフェースを継承(実装)することができます。 たとえば、
import java.io.PrintStream;
public interface Ps {
     public abstract void psPrint(PrintStream pStr);/* PostScript形式プリントする抽象関数 */
}
とし、

public class Circle implements Shape2D, Ps { }

のように2つ以上のインタフェースを継承(実装)するクラスを定義できます。 抽象クラスでは、2つ以上のクラスを継承できないので注意してください。

総称型(Generic Type)(ジェネリックタイプ)(復習)

ジェネリクスはJavaのシステムが提供する重要なクラスやインタフェースで使用されているため、 これを正確に理解しておくことはとても重要です。 たとえば、 動的な線形リストを表現するArrayList (Listインタフェース)、 辞書(ハッシング)を表現するHashMapやTreeMap(Mapインタフェース)、 集合体を表現するHashSetやTreeSet(Setインタフェース)、ならびに Collectionインタフェース、 反復処理を行うIteratorインタフェース、 比較処理を行うComparatorインタフェース、 など多様な処理を行う場合に、1個(<V>)または2個(<K,V>)のオブジェクトを用いたジェネリクスを頻繁に利用します。 ジェネリクスの基本的な使い方を紹介しました。 たとえば以下のように、<T>を総称型(Generic Type)として、 いろいろなオブジェクトを<T>に代入して使用する例を示しました。 たとえば、<Interger>、<double[]>、 あるいは、<ArrayList<Double>>などの例を示しました。
public class GenericType<T> {/* 型Tを一般化したクラス */

    private T t;/* 型Tのデータ */
    public T get(){/* 型Tのデータを返す */
        return this.t;
    }
    public void set(T t){/* 型Tのデータをセットする */
        this.t = t;
    }
}
次に、これを以下のように拡張することを考えます。
public class MyArrayList<T> {/* 型Tを一般化したクラス */

    private final ArrayList<T> t;/* 型Tのデータ */
    public MyArrayList(ArrayList <T> t){
        this.t = t;/* コンストラクタでのみfinalオブジェクトに代入可能 */
    }
    public ArrayList<T> get(){/* 型Tのデータを返す */
        return this.t;
    }
}
ここでは、2つの重要な変更があります。 ひとつは、<T>がArrayList<T>に変わったことです。 もうひとつは、クラス内のprivateな変数がprivate final に変わったことです。 final修飾子がついた変数は、 コンストラクタ以外では値を変更できないことに注意してください。 これは、不可変(immutable)オブジェクトとも呼ばれます。 最初の例にあった、set関数はここでは使えません。 final修飾子がついた変数が保護されるという性質は、 後述するマルチスレッド環境下で、 スレッドセーフを実現する手法のひとつとして重要な働きをします。

一方、総称型では、通常のオブジェクトと違い、使う側での注意点があります。 通常のオブジェクトでは、以下のようなキャストが可能です。 なお、IntegerはObjectクラスを継承していることに注意してください。

◎ Object e = (Object)new Integer(10);

しかしながら、このキャストは以下のように、総称型の中での継承関係の場合は使えないという制限があります。

× List<Object> e = (List <Object>)new ArrayList<Integer>();

そこで、ワイルドカード(?文字)を使うことで、この問題を回避することができます。 ワイルドカードは、未知型(unknown type)と呼ばれることがあります。

List <?> e

ワイルドカードを使った未知型は、通常、関数のパラメータに使われます。以下が、その典型例となります。

public void printList(PrintWriter out, List<?> list){/* ワイルドカード型?を用いた関数例 */
    for (int i=0; n=list.size(); i < n ; i++){
        if (i > 0) out.print(", ");
        Object o = list.get(i);
        out.print(o.toString());
    }
}
上述の関数の定義であれば、呼び出し側で、List<String>であれ、List<Object>型であれ、 printList関数を呼び出すことが出来ます。 ワイルドカードの利用に当たっては、ある程度、型に制限をつけたいことがあります。 特に継承関係があるクラスの場合、これが顕著になります。 この制限には、上限下限の2種類があります。 たとえば、List型のワイルドカードだが、 Numberクラスを継承したもの(例:Integer, Double, Float)だけにしたい場合、 以下のように上限を設定できます。

 printList (PrintWriter out, List <? extends Number> list)

と書きます。 一方、 ソーティングをしたい場合等では、大小の比較演算ができるように、 Comparableインタフェースを継承すると同時に、その型または親クラスとして有するものだけが望ましく、 以下のように下限を設定できます。 下限をつける理由は、型Tがしばしば、 ユーザが作成したクラスで、ある親クラスを継承したものであることが多く、 <? super T>により、 その親クラスまで拡張して比較演算が適用できれば、この型でマッチするオブジェクトの柔軟性が高まります。

 printList (PrintWriter out, List <T extends Comparable <? super T> > list)

ちなみに、このようなジェネリクスの型制限は、 類似の機能があるC++言語のテンプレートでも、 BoostのBOOST_STATIC_ASSERTのようなライブラリで、親(基底)クラスをis_base_of宣言で制限したり、数値クラスに対してnumeric_limitsで値の範囲を指定したりといった型制限を行えることが知られています。

ワイルドカードを使う別の例を紹介します。 MyArrayListクラスで保持するデータをソーティングしたいとします。 データが(java.utilパッケージの)ArrayListクラスの変数であり、 ArrayListが(java.utilパッケージの)Listクラスを継承するクラスであるので、 通常は、

Collections.sort(List<T> list);

のようなプロトタイプのシステム関数でソーティングすることができます。 これを踏まえて、上述した「下限のワイルドカード」を用いた事例を紹介します。 なお、以下で利用するCollections型のsort関数の修飾子が、 プログラム5-1で記述するクラスのジェネリックタイプと同様であることに注意してください。 Collectionsのsort関数は、Listクラスのオブジェクトを昇順にソーティングします。 もし、降順に(逆順に)ソートしたい場合は、reverseという名前の関数で行います。
MySortedList.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
プログラム5-1: 比較演算を加えた下限のワイルドカードう含むソート実装例
*/
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.util.Random;
import java.util.Date;

public final class MySortedList <T extends Comparable<? super T>> {
    /* Tの基底クラスと、Comparableで比較できるクラスを継承したクラス(Tの例:Integer)に限定 */
    private final ArrayList<T> t;/* 不可変(immutable)のためprivate final */
    public MySortedList(ArrayList <T> t){
        this.t = t;/* コンストラクタでのみfinalオブジェクトに代入可能 */
    }
    public ArrayList<T> get(){/* 型Tのデータを返す */
        return this.t;
    }
    public void sort(){/* Collectionsのsortを呼ぶ */
        Collections.sort(t); /* ここで、Collections型のオブジェクトを昇順にソーティング */
    }

    public static void main(String[] args){
        Date date = new Date();
        Random rand = new Random(date.getTime()); /* 乱数発生 */
        final int MILLION = 1000000;
        final int NUMBER = 100;
        ArrayList <Integer> Iarray = new ArrayList<Integer>(); /* IntegerのArrayList */
        for (int i = 0 ; i < NUMBER ; i++)
            Iarray.add(new Integer(rand.nextInt()/MILLION));
        MySortedList<Integer> intList = new MySortedList<Integer>(Iarray);
        intList.sort(); /* ソーティング */
        Iarray = intList.get();
        for (int i = 0 ; i < (int)Iarray.size(); i++){
            System.out.print(Iarray.get(i)+" ");
        }
        System.out.print("\n");
        ArrayList <Double> Darray = new ArrayList<Double>(); /* DoubleのArrayList */
        for (int i = 0 ; i < NUMBER ; i++)
            Darray.add(new Double((rand.nextDouble()-0.5)*2.0));
        MySortedList<Double> realList = new MySortedList<Double>(Darray);
        realList.sort(); /* ソーティング */
        Darray = realList.get();
        for (int i = 0 ; i < (int)Darray.size(); i++){
            System.out.printf("%5.3f ",Darray.get(i));
        }
        System.out.print("\n");
    }
}
実行結果は以下のようです。

$ javacu MySortedList.java

$ javau MySortedList
-2072 -2039 -1870 -1824 -1791 -1718 -1654 -1652 -1578 -1546 -1484 -1409 
-1322 -1299 -1279 -1274 -1211 -1197 -1115 -1110 -1088 -1076 -951 -931 -907 
-886 -860 -767 -698 -674 -631 -630 -623 -573 -572 -564 -537 -499 -481 -404 
-368 -318 -262 -254 -199 -184 -171 -148 -128 17 28 39 68 82 119 150 245 274 
279 330 332 361 372 390 427 429 463 536 551 686 693 792 814 836 842 943 
1120 1142 1232 1274 1283 1357 1384 1458 1476 1499 1504 1598 1611 1620 
1634 1641 1717 1732 1751 1766 1915 1978 2071 2144

-0.998 -0.952 -0.924 -0.916 -0.817 -0.789 -0.761 -0.749 -0.735 -0.724 -0.719 
-0.696 -0.646 -0.645 -0.629 -0.625 -0.574 -0.573 -0.567 -0.543 -0.540 -0.524 
-0.507 -0.483 -0.391 -0.382 -0.362 -0.350 -0.340 -0.337 -0.320 -0.316 -0.312 
-0.292 -0.263 -0.233 -0.232 -0.222 -0.207 -0.203 -0.194 -0.142 -0.125 -0.116 
-0.106 -0.101 -0.012 0.001 0.003 0.011 0.035 0.044 0.071 0.079 0.084 0.108 
0.114 0.125 0.135 0.221 0.246 0.284 0.304 0.358 0.363 0.393 0.408 0.412 
0.501 0.511 0.515 0.556 0.578 0.640 0.668 0.688 0.702 0.706 0.715 0.725 
0.733 0.744 0.784 0.791 0.791 0.839 0.845 0.874 0.887 0.896 0.899 0.909 
0.921 0.931 0.940 0.941 0.944 0.946 0.958 0.961
下限ワイルドカードをもったジェネリック型のテストプログラムの実行結果

アルゴリズムの実装例(その1)

Vector, ArrayList, HashMap, Setなど、Java言語には、ジェネリクスに対応した有用なクラスが数多く用意されています。 しかしながら、 Collections.sortに代表されるシステム関数に頼る場合に 注意すべき事項があります。 ひとつは、ソーティングアルゴリズム自体の学習や動作の仕組みを理解できないことです。 もうひとつは、マルチスレッドプログラミングでの高速化など、 カスタマイズができなくなることです。 そこで、以下では、クイックソートを例にとり、 これに総称型(ジェネリック・タイプ)を導入したクラスの構築例を示します。
QuickSort.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
プログラム5-2: 比較演算を加えたジェネリクスをもつクイックソート実装例とArrays.sort
*/
import java.util.Arrays;
public class QuickSort <T extends Comparable<? super T>>{

    private boolean lessThan(T a, T b){/* 比較演算 */
        if (!(a.compareTo(b) > 0)) return true;
        else return false;
    }
    public void swap(T[] A, int i, int j){/* データの交換 */
        T temp = A[j];
        A[j] = A[i];
        A[i] = temp;
    }
    public int Partition(T[] A, int left, int right){/* Cormen et alを参考にしたデータの分割 */
        T pivot = A[right];
        int i = left - 1;
        for (int j = left ; j < right ; j++){
            if (lessThan(A[j], pivot)){/* A[j] < pivotのとき、交換 */
                i++;
                swap(A, i, j);
            }
        }
        swap(A,i+1,right);
        return (i+1);
    }
    public void Qsort(T[] A, int left, int right){/* クイックソート本体:再帰 */
        if (left < right){ /* 分割統治 (divide-and-conquer) */
            int pivot = Partition(A,left,right);
            Qsort(A, left, pivot-1);/* ピボットの左側を再帰的にソート */
            Qsort(A,pivot+1,right);/* ピボットの右側を再帰的にソート */
        }
    }

    public static void main(String[]args){
        Integer [] A ={ 3, 8, 7, 5, 2,    1, 9, 6, 4};/* 整数配列例 */
        String [] S = { /* String配列例 */
            "January", "February", "March", "April", "May", "June",
            "July", "August", "September",    "October", "November", "December"};
        int lenA=A.length;/* 配列Aの長さ */
        int lenS = S.length;/* 配列Sの長さ */

        /******1 Quicksort (Integer) ******/ System.out.println("整数のQuickSort");
        QuickSort<Integer> qsA = new QuickSort<Integer>();/* Integert型でクイックソート */
        qsA.Qsort(A,0,lenA-1);/* ソート実行 */
        for (int i = 0 ; i < lenA ; i++ )/* 結果のプリント */
            System.out.println(A[i]); System.out.println();

        /******2 Quicksort (String) ******/ System.out.println("文字列のQuickSort");
        QuickSort<String> qsS = new QuickSort<String>();/* String型でクイックソート*/
        qsS.Qsort(S,0,lenS-1);/* ソート実行 */
        for (int i = 0 ; i < lenS ; i++ )/* 結果のプリント */
            System.out.println(S[i]); System.out.println();

        /*****3 Arraysクラスのsortメソッドによる文字列のソーティング *****/
        System.out.println("Arrays.sortを使った文字列のソーティング ");
        Arrays.sort(S);/* システムソート:大規模データで高速動作するようチューニングされている */
        for (int i = 0 ; i < lenS ; i++ )/* 結果のプリント */
            System.out.println(S[i]); System.out.println();

        /*****4 Arraysクラスのsortメソッドによるdouble型実数値のソーティング *****/
        System.out.println("Arrays.sortを使ったdouble型実数値のソーティング");
        double[] D = { 5.2, -3.8, 0.05, 29.3, -19.5, 2.7, 31.24};
        Arrays.sort(D);/* 原始型でもArrays.sortでソーティングできる */
        for (int i = 0 ; i < D.length ; i++ )
            System.out.println(D[i]); System.out.println();
    }
}
実行結果は以下の通りです。

$ javacu QuickSort.java

$ javau QuickSort
整数のQuickSort
1
2
3
4
5
6
7
8
9

文字列のQuickSort
April
August
December
February
January
July
June
March
May
November
October
September

Arrays.sortを使った文字列のソーティング
April
August
December
February
January
July
June
March
May
November
October
September

Arrays.sortを使ったdouble型実数値のソーティング
-19.5
-3.8
0.05
2.7
5.2
29.3
31.24
手作りクイックソートとシステムソートを実行したところ


グラフ(Graphs)と深さ優先探索 (Depth-First Search)

ArrayListのような可変長のデータの保持ができるようになると、 それに適したデータ構造を持つアルゴリズムの実装が簡単になります。 ここでは、基本的なグラフのデータ構造に着目したアルゴリズムを紹介したいと思います。 グラフは「頂点」(vertex)と「エッジ」(edge)からなりますが、「エッジ」は、 向きがあるか無いかによって、 有向グラフ (Directed Graphs)無向グラフ (Undirected Graphs)に分かれます。 ここでは、以下にイラストするように、有向グラフを考えます。 今、イラストの左端にあるように、A,B,C,D,Eを0~5までの整数インデックス表現するとします。 ポピュラーなグラフの表現形式には、イラスト中央にある、 「隣接リスト」表現と「隣接行列」表現が知られています。 このうち、以下では、隣接リストの実装例を紹介します。

有向グラフとその表現例(隣接リストと隣接行列)


今、有向グラフが与えられたとき、このグラフに含まれる頂点を、 適当なスタート頂点から、連結関係を利用して、網羅的に列挙する問題を考えます。 当然、連結されていない頂点は漏れるわけですが、 漏れていたら、その頂点を再度スタート頂点として、同じように、 連結関係をもとに頂点を探していくとします。 結局、見つかった頂点を、決められた順序に並べる問題に帰着します。 もちろん、スタート頂点によって結果は変わりますが、 重要な要素として、エッジをたどる仕方の選択によって順番は変わります。 以下では、深さ優先探索(Depth-First Search)を行うとします。 深さ優先探索は以下のように再帰的なアルゴリズムで実装できます。
GraphTest.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
    プログラム5-3: グラフの深さ優先探索アルゴリズム
*/
import java.util.ArrayList;
import java.io.PrintStream;

public class GraphTest {
    final int BLACK = 0;/* 訪問終了 */
    final int WHITE = 1;/* まだ訪問していない頂点 */
    final int GRAY = 2;/* 訪れたが、深さ優先探索中の頂点 */
    int[] color;/* 色をフラグとして利用 */
    int[] p;/* predecessor (DAGの直前のノード)の保持 */
    int numV;/* number of vertices */
    int numE;/* number of edges */
    int time;/* グラフをトラバースするさいの時刻を保持 */
    int[] discoveryTime;/* DFSの開始時刻 */
    int[] finishTime;/* DFSの終了時刻 */
    ArrayList <ArrayList <Integer>>adjList; /* 隣接リスト */

    public GraphTest(int vertex, int edge){/* コンストラクタ */
        this.numV = vertex;
        this.numE = edge;
        color = new int[numV];/* 色 */
        p = new int[numV];/* 直前のノード:現在対象としているノードを指すノード */
        discoveryTime = new int[numV];/* 処理開始時刻 */
        finishTime = new int[numV];/* 処理終了時刻 */
        time = 0;
        adjList = new ArrayList <ArrayList<Integer>>(); /* numV個の隣接リスト用メモリ */
    }
    ArrayList <ArrayList<Integer>> getAdjList(){ return adjList; }
    void DFS(ArrayList <ArrayList <Integer>> G){ /* Depth-First Search */
        for ( int u = 0 ; u < numV ; u++) { 
            color[u] = WHITE; /* 未訪問ノードはWHITEにしておく */
            p[u] = Integer.MIN_VALUE; /* 最小値を適当に代入 */
        } 
        time = 0; /* 時刻のリセット */
        for ( int u = 0 ; u < numV ; u++) { 
            if (color[u] == WHITE) { 
                DFS_VISIT( G, u );  /* 深さ優先探索開始 */
            } 
        }
    }
    void DFS_VISIT(ArrayList <ArrayList <Integer>> G, int u){ 
        /* DFSで再帰的にコールする関数 */
        time = time + 1; 
        discoveryTime[u] = time; /* 深さ優先探索、その方向での作業開始 */
        color[u] = GRAY; /* 発見時はGRAYに */
        int size = G.get(u).size();
        for ( int v = 0 ; v < size ; v++ ) { 
            if (color[G.get(u).get(v)] == WHITE) { /* まだ未訪問 */
                p[G.get(u).get(v)] = u; /* 直前のノードに保持 */
                DFS_VISIT( G, G.get(u).get(v) ); /* 深さ方向に再帰的にコール */
            }
        }
        color[u] = BLACK; /* 終了時はBLACKに */
        time = time + 1; 
        finishTime[u] = time; /* 深さ優先探索、その方向での作業終了 */    
    }
    
    public static void main(String[] args){
        int numV=5, numE=9;/* 頂点数とエッジ数 */
        GraphTest graph = new GraphTest(numV, numE);/* グラフのオブジェクト作成 */
        ArrayList <ArrayList <Integer>>G = graph.getAdjList(); /* グラフの隣接リスト */
        int u, v; /* 頂点番号保持 */
        int[][] EdgeList = {{0,1},{0,2},{1,4},{2,1},{2,4},{3,0},{3,2},{3,4},{4,4}}; 
        String[]  name= {"A", "B", "C", "D", "E"};
        ArrayList <Integer> AL;/* ArrayList用変数 */
        for (int i = 0 ; i < numV ; i++){
            AL = new ArrayList <Integer>();/* 隣接リスト用ArrayList(縦方向)を作成 */
            G.add(AL);/* 隣接リストオブジェクトを頂点数だけ確保 */
        }
        for (int i = 0 ; i < numE ; i++){
            u = EdgeList[i][0];/* エッジの開始 */
            v = EdgeList[i][1];/* エッジの終端 */
            AL = G.get(u);/* uに対応するArrayListオブジェクトをセット */
            AL.add(v);/* uからvにエッジ(隣接リスト:横方向に追加) */ 
        }
        graph.DFS(G);/* 深さ優先探索 */
        PrintStream out = System.out;/* PrintStreamにセット */
        for (int i = 0 ; i < numV ; i++){/* DFSの結果プリント */
            out.println("["+ i+ "] : "+ name[i]+" d = "+graph.discoveryTime[i]+
                "  f = "+graph.finishTime[i]);
        }
    }
}
以下がコンパイルと実行例です。

$ javacu GraphTest.java

$ javau GraphTest
[0] : A d = 1  f = 8
[1] : B d = 2  f = 5
[2] : C d = 6  f = 7
[3] : D d = 9  f = 10
[4] : E d = 3  f = 4
グラフの深さ優先探索例


結果の意味としては、f(finishTime)の値の大きさより、Eが深さ優先では、最も早く処理が終わり、 次いで、B, C, Aで最後にDの処理が終わったことを示しています。


スレッド処理・マルチスレッドプログラミング

Java言語には、スレッド処理を記述できるクラスが標準に装備されています。 スレッド(Thread)とは、 プログラムの実行単位のことです。 スレッドは、軽量プロセス(Lightweight process)とも呼ばれ、 現代的なオペレーションシステムは、プロセスではなくスレッドをスケジューリングの単位として扱います。 スレッドを扱うプログラムでは注意が必須となります。 スレッドを誤って使用すると、わずかなエラーの結果、 プログラム全体をストップさせたり、実行結果が予期しないものになったりします。 一方、スレッドを正しく使うと開発とメンテナンスの費用が下がり、 複雑なアプリケーションの実行性能が飛躍的に上がります。 スレッド処理は、 GUIアプリケーションにおけるイベント処理や、 ネットワークアプリケーションにおける複数ホストとの接続処理などにおいて重要となります。 複数のスレッドを用いたマルチスレッドプログラミングは、 並列処理を実現するひとつの簡便な手法です。 2つ以上のスレッドが同時に実行される環境下では、注意も必要です。 共有される資源(オブジェクト)がある場合、 無秩序ににアクセスすると、資源が壊される危険を有しています。 それでもなお、共有される資源を持つことは、 スレッド間のコミュニケーションを実現する簡便な手段として多用されます。 実際、マルチスレッド化は、実用的に極めて有用な方法です。 排他制御などをしっかり行うことで、 共有資源へのアクセスのリスクを回避することもできます。 以下では、これらの概念をサンプルプログラムを通して理解することを目的とします。

最初に Threadクラスを用いたスレッドの実行方法、 次に Runnableインタフェースを用いたスレッドの実行方法を述べます。 これまで、インタフェースに関する簡単な説明と例を述べてきました。 その際、以下のように述べました。 インタフェースとは、 クラス同様、新たな参照型を定義できるものです。 しかし、通常のクラスとは違って、 インタフェースでは、 すべてのメソッド(関数)が抽象関数として定義されます。 抽象クラスでのクラスの継承では、 抽象関数以外の関数や変数を定義できましたが、インタフェースの場合は、 final修飾子のつく定数を除いては、 すべての関数が抽象関数とみなされます。 インタフェースを実装するクラスでは、 これらの抽象関数をすべて定義する必要があります。 たとえば、java.util.Listインタフェースは、 総称型のワイルドカードでも触れましたが、 これを実装するjava.util.ArrayListクラスは、 java.util.Listインタフェースが有する20種類以上の関数すべてを定義しています。 重要な概念なので反復になりますが、抽象クラスを定義した場合では、 それを継承するクラスで、すべての抽象関数を実装し、 その際、extends BaseのようにBaseクラスを継承するというextendsキーワードを使った継承関係が必要でした。 この継承関係の問題点は、 複数の便利な(抽象クラスで定義された)基底クラスがあったとしても、 その派生クラスは、そのうちどれかひとつの基底クラスしかextends(継承)できない、という点です。 インタフェースを定義した場合、抽象クラスと同様に、 それを使いたいクラスで(抽象)関数をすべて定義する必要があります。 しかし、抽象クラスと違って、 インタフェースでは、 B implements A のように記述します。 このとき、クラスBはAという名前のインタフェースを実装すると呼びます。 クラスの継承と違ってimplements A, B, C のように、いくらでも複数のインタフェースを実装している宣言が可能です。 また、 extends X implements A, B, C のように、Xというクラスを継承し、A,B,Cというインタフェースを 実装する、といったクラスを定義することも可能です。 マルチスレッドプログラミングでは、 複数のインタフェースをimplementsする例が普通に出てきます。

シングルスレッドとThreadクラスによるマルチスレッド

これまで紹介してきたJavaプログラムは、 シングルスレッド、つまり一つのスレッドで実行されるプログラムでした。シングルスレッドのプログラムでは、 プログラムの実行中、ソースコード上の常にどこか一か所だけ実行しています。

一方、マルチスレッドでは、 各スレッドが並列に動作します。 以下のシンプルなプログラムで例を示しましょう。
ThreadTest.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
    プログラム5-4 Threadクラスによるrun関数を用いたマルチスレッド
*/

public class ThreadTest extends Thread {

    public void run(){/* 子スレッド実行:Threadクラスのrun関数のオーバーライド */
        System.out.println("子スレッド実行しています");
    }
    public static void main(String[] args){
        int loops = Integer.valueOf(args[0]).intValue();/* ループ回数 */
        ThreadTest tt = new ThreadTest();
        System.out.println("スレッドテスト開始");
        tt.start();/* Threadクラスのrunメソッドを間接的に呼び出す */
        for (int i = 0 ; i < loops; i++);/* 何かの処理 */
        System.out.println("mainの終了");
    }
}
以下がこのプログラムの出力例です。

mp020:9 ma002$ javacu ThreadTest.java

mp020:9 ma002$ javau ThreadTest 10000
スレッドテスト開始
子スレッド実行しています
mainの終了

mp020:9 ma002$ javau ThreadTest 10000
スレッドテスト開始
mainの終了
子スレッド実行しています
この結果より、子スレッドが先に実行されることもあれば、mainが先に終了することもあることがわかります。 プログラム5-4でのポイントは、 なお、プログラム5-4の15行目では、適当な回数のループを意図的に加えており、 実行例では、このループに10000回を与えています。 これは、JVM(JavaのVirtual Machine)を実行するマシン環境で異なります。 このようなループがなくても、子プロセスと親プロセスの終了結果がまちまちになることがあります。 いずれにしても、 子プロセスのstart()メソッドを呼出すことで、 並列に2つのプロセスが走るようすることが可能となります。

Runnableインタフェースによるマルチスレッド

Threadクラスを継承するクラスからマルチスレッドを実現するする場合、 時として問題が生じます。 理由は、その子クラスはすでにThreadクラスを継承しているので、 他の基底クラスを継承できないことです。 そこで、最初に述べたインタフェースを用いることでこの問題を回避することができます。 具体的には以下のプログラムに示すRunnableインタフェースを利用します。
RunnableTest.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
    プログラム5-5 Runnableインタフェースによるマルチスレッド
*/
public class RunnableTest implements Runnable {

    int ID;/* スレッド識別用ID */
    public RunnableTest(int ID){ this.ID = ID;}
    public void run(){/* 子スレッド実行 */
        System.out.println("Runnableインタフェース:子スレッド ID = "+ID);
    }
    public static void main(String[] args){
        RunnableTest rt1 = new RunnableTest(1);/* 第一スレッド用 */
        Thread thread1 = new Thread(rt1);/* 第一スレッド生成 */
        thread1.start();/* 第一スレッドのrunメソッドの呼出し */
        RunnableTest rt2 = new RunnableTest(2);/* 第二スレッド用 */
        Thread thread2 = new Thread(rt2);/* 第二スレッド生成 */
        thread2.start();/* 第二スレッドのrunメソッドの呼出し */
        System.out.println("mainの終了");
    }
}
Runnableインタフェースを実装するクラスでは、 Threadクラスのオブジェクトを生成します。 その際、Runnableクラスを実装するクラスのオブジェクトをコンストラクタの引数として渡します。 このようなThreadクラスのインスタンスを複数生成し、 それぞれ、start関数を呼び出すことでマルチスレッドプログラミングすることが可能です。 実行結果は以下の通りで、Threadクラスを継承する場合と同様に、 Runnableインタフェースを実装する場合でも、 スレッドの処理の順番が、まちまちの結果になることがわかります。
mp020:9 ma002$ javacu RunnableTest.java

mp020:9 ma002$ javau RunnableTest
mainの終了
Runnableインタフェース:子スレッド ID = 2
Runnableインタフェース:子スレッド ID = 1

mp020:9 ma002$ javau RunnableTest
mainの終了
Runnableインタフェース:子スレッド ID = 2
Runnableインタフェース:子スレッド ID = 1

mp020:9 ma002$ javau RunnableTest
mainの終了
Runnableインタフェース:子スレッド ID = 1
Runnableインタフェース:子スレッド ID = 2

排他制御

マルチスレッドでのプログラムは、以上のように比較的簡単に作成することができますが、 気を付けないといけない場合があります。 それは、複数のスレッドが同じ資源(リソース)にアクセスし、 結果が、リソースのアクセス時点での値に依存する場合です。 以下では、ひとつの資源を2つのスレッドが競合して書き込みを行うことで、 実行結果が変化するサンプルプログラムです。
ThreadUnsafe.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
    プログラム5-6 資源を争うマルチスレッドプログラム例
*/
public class ThreadUnsafe implements Runnable {
    /* 以下の資源を2つのスレッドが奪い合う */
    int stackSpace;/* スタックスペース */

    public void run(){/* 子スレッド実行 */
        stackSpaceAlloc(10);
    }
    public void sleep(){
        try {
            Thread.sleep((int)(Math.random() * 100));/* 少しスレッドを待たせる */
        }
        catch (InterruptedException e){e.printStackTrace();}
    }
    public void stackSpaceAlloc(int n){/* runメソッドからアクセスされる関数 */
        sleep();
        stackSpace = 8 * n;/* double型n個の領域確保 */
        sleep();
        stackSpace = stackSpace - n;/* スタックをnバイト使用要求 */
        /* 8*n - nバイト残っているかプリントで確認 */
        System.out.printf("1: stackSpace = %d\n", stackSpace);
    }
    public void stackSpaceCleanRefill(){/* runメソッドからの呼び出しと異なる方法で同一資源にアクセス*/
        sleep();
        stackSpace = 0; /* リセット */
        sleep();
        stackSpace = stackSpace + 5000;/* スタックを一杯に満たす */
        System.out.printf("2: stackSpace = %d\n", stackSpace);
    }
    public static void main(String[] args){
        ThreadUnsafe tu = new ThreadUnsafe();/* 第一スレッド用 */
        /* 第二スレッド生成 */
        Thread thread = new Thread(tu);
        thread.start();/* 第二スレッドのrunメソッドの呼出し */
        /* 第一スレッドから共通の資源(stackSpace変数)にアクセス */
        tu.stackSpaceCleanRefill();
    }
}
以下がこのプログラムを5回独立に実行した際の出力例です。
mp020:9 ma002$ javacu ThreadUnsafe.java

mp020:9 ma002$ javau ThreadUnsafe
1: stackSpace = 70
2: stackSpace = 5070

mp020:9 ma002$ javau ThreadUnsafe
1: stackSpace = 70
2: stackSpace = 5070

mp020:9 ma002$ javau ThreadUnsafe
2: stackSpace = 5080
1: stackSpace = 5070

mp020:9 ma002$ javau ThreadUnsafe
1: stackSpace = 70
2: stackSpace = 5000

mp020:9 ma002$ javau ThreadUnsafe
1: stackSpace = -10
2: stackSpace = 4990
ある意味では、プログラム5-6は、わざとらしい例で、 もともと同じ資源を2つ以上のプロセスで競合させなければいいのですが、 実は、このようなことは、 サーバサイドのプログラムで、不特定多数のユーザが同時にアクセスするようなネットワークプログラムでは平気で発生する現象です。 たとえば、Webをアクセスするユーザに好きな数字を入力させて、それが偶数か奇数かにより、 何かの処理をさせるようなサーバサイドのプログラムを書くとするとき、複数同時アクセスにより、 サーバが確認したタイミングで、間違ってしまうことが頻繁に発生します。 より深刻な例として、ファイルをサーバにアップロードさせるプログラムが同時に複数クライアントから呼び出されたとき、 下手に制御すると、あるユーザのファイルのアップロードが、 あたかもまったく実行されなかったりします。 では、このようなとき、どうすればいいででしょうか?

Java言語では、資源の競合に関して、 synchronized というキーワードで、これをメソッドの前に修飾子としてつけて

public synchronized void spaceAlloc(int n)

のようにメソッドごとに、synchrnozied宣言をして、 排他制御(mutual exclusion)を行ったり、オブジェクトごとに

synchronized (オブジェクト) { ...}

のように排他制御をかけることができます。 この場合、synchronized宣言されたオブジェクトにロックがかかり、 ブロック内のプログラムが終了するまで、 他のスレッドからそのオブジェクトにアクセスできなくなります。 プログラム5-6では、stackSpaceという共通のオブジェクトを取り合っていましたから、 このオブジェクトに以下のようにsynchronizedで排他制御をかけてみます。
ThreadSafe.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
    プログラム5-7 スレッドセーフなマルチスレッドプログラム例
*/
public class ThreadSafe implements Runnable {
    int stackSpace;/* スタックスペース */

    public void run(){/* 子スレッド実行 */
        stackSpaceAlloc(10);
    }
    public void sleep(){
        try {
            Thread.sleep((int)(Math.random() * 100));/* 少しスレッドを待たせる */
        }
        catch (InterruptedException e){e.printStackTrace();}
    }
    public void stackSpaceAlloc(int n){/* runメソッドからアクセスされる関数 */
        synchronized(this){/* オブジェクトをロックし排他制御 */
            sleep();
            stackSpace = 8 * n;/* double型n個の領域確保 */
            sleep();
            stackSpace = stackSpace - n;/* スタックをnバイト使用要求 */
            /* 8*n - nバイト残っているかプリントで確認 */
            System.out.printf("1: stackSpace = %d\n", stackSpace);
        }
    }
    public void stackSpaceCleanRefill(){/* runメソッドからの呼び出しと異なる方法で同一資源にアクセス*/
        synchronized(this){/* オブジェクトをロックし排他制御 */
            sleep();
            stackSpace = 0; /* リセット */
            sleep();
            stackSpace = stackSpace + 5000;/* スタックを一杯に満たす */
            System.out.printf("2: stackSpace = %d\n", stackSpace);
        }
    }
    public static void main(String[] args){
        ThreadSafe tu = new ThreadSafe();/* 第一スレッド用 */
        Thread thread = new Thread(tu);/* 第一スレッド生成 */
        thread.start();/* 第一スレッドのrunメソッドの呼出し */
        tu.stackSpaceCleanRefill();/* 第二スレッド呼出し(runメソッドからの呼び出しと異なる方法で資源にアクセス) */
    }
}
以下がこのプログラムの出力例です。

mp020:9 ma002$ javacu ThreadSafe.java

mp020:9 ma002$ javau ThreadSafe
2: stackSpace = 5000
1: stackSpace = 70

mp020:9 ma002$ javau ThreadSafe
2: stackSpace = 5000
1: stackSpace = 70
以下に、ファイルから文字列を入力する2つのスレッドが ともに、読み込んだ文字列を共有するArrayListに追加しようとして 順不同に書き込まれる例を紹介します。 読み込むファイルの一方は、jQuery.txtというファイルで中身は以下のようです。
愛知県
コンビニ
マクドナルド
マイクロソフト
グーグル
株式
細胞
臨床
ゆるキャラ
豊橋
子育て
イベント
景気
衆院選
逮捕
積雪
師走
クリスマス
グランプリ
冬季五輪
もうひとつは、eQuery.txtというファイルで中身は以下のようです。
AKB
Apple
click-through
earthquake
email
Facebook
information
iPad
Japanese
jurisdiction
language
nuclear
policy
popularity
radioactive
Sony
statement
Twitter
vulnerable
Web
これらの2つのファイルを読み込み、 スレッドを用いてArrayListに書き込むことにします。
ThreadUnsafeIO.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
    プログラム5-8 資源を争うマルチスレッドプログラム例
*/
import java.util.ArrayList;
import java.io.FileReader;
import java.io.BufferedReader;

public class ThreadUnsafeIO implements Runnable {

    ArrayList <String> keyword = new ArrayList<String>();/* キーワードリスト */
    BufferedReader br1 = null;/* ファイル1のバッファリーダ */
    BufferedReader br2 = null;/* ファイル2のバッファリーダ */
    boolean finished1 = false;/* ファイル1を読み終わったかどうか */
    boolean finished2 = false;/* ファイル2を読み終わったかどうか */

    public void openFiles(String fname1, String fname2){
        try {
            FileReader fr1 = new FileReader(fname1);/* ファイル1のopen */
            FileReader fr2 = new FileReader(fname2);/* ファイル2のopen */
            br1 = new BufferedReader(fr1);/* ファイル1のバッファリーダ */
            br2 = new BufferedReader(fr2);/* ファイル2のバッファリーダ */
        }
        catch (Exception e){ e.printStackTrace(); }
    }
    public void run(){/* 子スレッド実行 */
        addArray();/* 第一ファイルの単語を追加 */
    }
    public void sleep(){/* sleepさせる */
        try {
            Thread.sleep((int)(Math.random() * 10));
        }
        catch (InterruptedException e){e.printStackTrace();}
    }
    public String readKeyword(BufferedReader br){
        try {
            String token = br.readLine();/* 行単位で単語を読みだす */
            return(token);/* 単語を返す:EOFならnull */
        }
        catch(Exception e){e.printStackTrace(); return null;}
    }
    public void addArray(){/* runメソッドからアクセスされる関数 */
        String data = null;
        while ((data = readKeyword(br1)) != null){
            sleep();
            keyword.add(data);/* ファイル1の単語を追加 */
        }
        finished1 = true;/* ファイル1がEOF */
    }
    public void addArray2(){/* runメソッドからの呼び出しと異なる方法で同一資源keywordにアクセス*/
        String data = null;
        while ((data = readKeyword(br2)) != null){
            sleep();
            keyword.add(data);/* ファイル2の単語を追加 */
        }
        finished2 = true;/* ファイル2がEOF */
    }
    public ArrayList<String> getKeyword(){
        return keyword;/* ArrayListを返す */
    }
    public void closeFiles(int n){
        try {
            while (!finished1) sleep();/* EOFでなければ待つ */
            br1.close();/* ファイル1のclose */
            while (!finished2) sleep();/* EOFでなければ待つ */
            br2.close();/* ファイル2のclose */
        }
        catch (Exception e){ e.printStackTrace();}
    }
    public static void main(String[] args){
	String fname1 = args[0];/* ファイル1の名前入力 */
	String fname2 = args[1];/* ファイル2の名前入力 */
	ThreadUnsafeIO tu = new ThreadUnsafeIO();/* 第一スレッド用 */
	tu.openFiles(fname1, fname2);/* ファイルのopen */
	Thread thread = new Thread(tu);/* 第一スレッド生成 */
	thread.start();/* 第一スレッドのrunメソッドの呼出し */
	tu.addArray2();/* 第二スレッド用(runメソッドからの呼び出しと異なる方法で資源にアクセス) */
	ArrayList<String> result = tu.getKeyword();/* ArrayListを得る */
	tu.closeFiles(10);/* ファイルのclose */
	for (int i = 0 ; i < result.size() ; i++)/* ArrayListのプリント */
		System.out.printf("ArrayList[%d] = %s\n", i, result.get(i));
    }
}
以下がこのプログラムの出力例です。英語のテキストと日本語のテキストが混在してしまっていることに気づくと思います。
$ javau ThreadUnsafeIO eQuery.txt  jQuery.txt
ArrayList[0] = 愛知県
ArrayList[1] = AKB
ArrayList[2] = コンビニ
ArrayList[3] = Apple
ArrayList[4] = マクドナルド
ArrayList[5] = click-through
ArrayList[6] = マイクロソフト
ArrayList[7] = earthquake
ArrayList[8] = グーグル
ArrayList[9] = 株式
ArrayList[10] = email
ArrayList[11] = 細胞
ArrayList[12] = 臨床
ArrayList[13] = Facebook
ArrayList[14] = information
ArrayList[15] = ゆるキャラ
ArrayList[16] = 豊橋
ArrayList[17] = 子育て
ArrayList[18] = iPad
ArrayList[19] = Japanese
ArrayList[20] = イベント
ArrayList[21] = jurisdiction
ArrayList[22] = language
ArrayList[23] = 景気
ArrayList[24] = 衆院選
ArrayList[25] = nuclear
ArrayList[26] = policy
ArrayList[27] = popularity
ArrayList[28] = radioactive
ArrayList[29] = 逮捕
ArrayList[30] = Sony
ArrayList[31] = 積雪
ArrayList[32] = 師走
ArrayList[33] = statement
ArrayList[34] = Twitter
ArrayList[35] = クリスマス
ArrayList[36] = vulnerable
ArrayList[37] = グランプリ
ArrayList[38] = Web
ArrayList[39] = 冬季五輪

スレッド(Thread)の状態

マルチスレッドでの処理は、一種の並列処理を与えるため、 資源をうまく利用すれば、高速なアルゴリズムを実現できます。 一方で、たとえば、デッドロックや、無限待ち状態などの不測の状況をさけるため、 各スレッドが現在どのような状態であるかを把握しておく必要があります。 これは、Threadクラスのオブジェクトを生成したあと、 Thread.State を調べることでわかります。 スレッドの状態としては6種類の状態があり、図示すると 以下のような関係にあります。

Thread(スレッド)の状態遷移図。一度start関数で起動したスレッドはRunning状態となる。その後、sleep関数でSleeping状態に、wait関数でWaiting状態に、I/OリクエストでBlocked状態に、関数の終了でTerminated状態のいずれかに遷移する。

final classとprivate finalなクラス変数事例

次に、サーバーサイドJavaで有効なfinalクラス、 およびprivate final変数で、スレッドセーフにする例を紹介します。 このような手法を不可変(immutable)オブジェクトと呼びます。 不可変(immutable)オブジェクトはスレッドセーフです。 クラス変数をprivate finalにすると、コンストラクタで値をセットすることしかできなくなります。 これによりサーバ上で動作するプログラムの場合、 同時アクセスによる値の非一貫性を防御することができます。 クラスをfinalにすると、そのクラスを継承することは決してできなくなります。 換言すると、「もう継承しなくていいですよ」という場合、finalにして結構です。 また、finalなクラス変数をint型やdouble型のような原始型にすると、 代入ができなくなります。 しかし、オブジェクト変数の場合は、代入以外の方法で値を変更することができます。 具体的には、以下のプログラムでは、クラス変数として、 HashSetを用いています。 HashSetの場合、add関数でクラス変数に値を追加することはできます。
FreeMusketeers.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
	プログラム5-9 FreeMusketeersクラス
	Java Concurrency in Practice (Brian Goetzら)参照
*/
import java.util.*;
/**
 * FreeMusketeers (自由騎士クラス)
 * 不可変クラス(Immutable class):スレッドセーフとなりロックしなくてもいい
 *クラスや変数をfinalとする。これにより、1度しかオブジェクトは生成されない
 */
 public final class FreeMusketeers {/* finalな自由騎士クラス */
    private final Set<String> Musketeers = new HashSet<String>();

    public FreeMusketeers(Set<String> set) { /* 注:Musketeers = set;とはできない */
        for (Iterator i = set.iterator(); i.hasNext();)/* ループで騎士に追加 */
            Musketeers.add((String)i.next());
    }
    public boolean isMusketeers(String name) {/* いるかどうか */
        return Musketeers.contains(name);
    }
    public String toString(){ return Musketeers.toString(); }
    public void add(String name){/* 追加はできる。代入はできないので注意 */
        Musketeers.add(name);
    }
}
以下は、マルチスレッドで上のクラスを呼び出す例です。
RunnableFreeMusketeers.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
	プログラム5-10 Runnableインタフェースによる自由騎士マルチスレッド
*/
import java.util.*;
public class RunnableFreeMusketeers implements Runnable {

    private FreeMusketeers data;/* 自由騎士データ */
    private String newName = "誰か";/* 別な騎士 */
    public RunnableFreeMusketeers(FreeMusketeers data){ 
        this.data = data;
    }
    public void setNewName(String name){ newName = name;}
    public FreeMusketeers getMusketeers(){ return data;}
    public void run(){/* 子スレッド実行 */
        data.add(newName);/* dataにある名前を追加 */
        System.out.println("Runnableインタフェース:子スレッド = "+data.toString());
    }
    public static void main(String[] args){
        HashSet<String> set1 = new HashSet<String>();
        set1.add("ハリー・ポッター");
        set1.add("ハーマイオニー・グレンジャー");
        set1.add("ロナルド・ウィーズリー");
        FreeMusketeers instance1 = new FreeMusketeers(set1);
        RunnableFreeMusketeers rt1 = new RunnableFreeMusketeers(instance1);/* 第一スレッド用 */
        Thread thread1 = new Thread(rt1);/* 第一スレッド生成 */

        HashSet<String> set2 = new HashSet<String>();
        set2.add("アトス");
        set2.add("ポルトス");
        set2.add("アラミス");
        FreeMusketeers instance2 = new FreeMusketeers(set2);

        RunnableFreeMusketeers rt2 = new RunnableFreeMusketeers(instance2);/* 第二スレッド用*/
        Thread thread2 = new Thread(rt2);/* 第二スレッド生成 */

        thread1.start();/* 第一スレッドのrunメソッドの呼出し */
        rt1.setNewName("ネビル・ロングボトム");
        thread2.start();/* 第二スレッドのrunメソッドの呼出し */
        System.out.println("mainの終了");
    }
}
実行結果は以下のようです。実行のタイミングにより、 スレッド1が早く終わったり、あとで終わったりします。

$ javacu RunnableFreeMusketeers.java

$ javau RunnableFreeMusketeers
Runnableインタフェース:子スレッド =
 [ネビル・ロングボトム, ハリー・ポッター, ハーマイオニー・グレンジャー, ロナルド・ウィーズリー]
Runnableインタフェース:子スレッド = 
[アラミス, ポルトス, 誰か, アトス]
mainの終了

$ javau RunnableFreeMusketeers
Runnableインタフェース:子スレッド = 
[アラミス, ポルトス, 誰か, アトス]
mainの終了
Runnableインタフェース:子スレッド = 
[ネビル・ロングボトム, ハリー・ポッター, ハーマイオニー・グレンジャー, ロナルド・ウィーズリー]

$ javau RunnableFreeMusketeers
mainの終了
Runnableインタフェース:子スレッド = 
[アラミス, ポルトス, 誰か, アトス]
Runnableインタフェース:子スレッド = 
[ネビル・ロングボトム, ハリー・ポッター, ハーマイオニー・グレンジャー, ロナルド・ウィーズリー]
final classならびにprivate finalなクラス変数を用いたマルチスレッドプログラム例

さらに強固なクラスで、データの改変を許さないようにする事例を紹介します。 以下の「三銃士クラス」がそれです。 Collections.unmodifiableSetという関数を使うと、 Collections型Setインタフェースの改変を禁止することができます。 なお、ここでは、Arrays.asList()という配列オブジェクトの初期化を与える関数を使っています。
ThreeMusketeers.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
    プログラム5-11 ThreeMusketeersクラス
    Java Concurrency in Practice (Brian Goetzら)参照
*/
import java.util.*;
/**
 * ThreeMusketeers (三銃士クラス)
 * 不可変クラス(Immutable class):スレッドセーフとなりロックしなくてもいい
 *クラスや変数をfinalとする。これにより、1度しかオブジェクトは生成されない
 */
 public final class ThreeMusketeers {/* 三銃士クラス */
    private final Set<String> Musketeers = 
        Collections.unmodifiableSet(/* 修正を一切許さないようにする場合 */
          new HashSet<String>(
            Arrays.asList(
              "アトス","ポルトス","アラミス"/* 有名な三銃士 */
            )
          )
        );
    public boolean isMusketeers(String name) {
        return Musketeers.contains(name);
    }
    public String toString(){ return Musketeers.toString(); }
    public void add(){
        Musketeers.add("誰か");
    }
    public void add(String name){
        Musketeers.add(name);
    }
}
これを呼び出す側は以下のようです。
RunnableMusketeers.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
    プログラム5-12 改変できないデータを使ったマルチスレッド
*/
import java.util.*;
public class RunnableMusketeers implements Runnable {

    ThreeMusketeers data;/* スレッド識別用ID */
    String name;/* 名前 */
    int ID;/* スレッドのID */
    public RunnableMusketeers(){ }
    public RunnableMusketeers(ThreeMusketeers data){ 
        this.data = data;
    }
    public ThreeMusketeers getMusketeers(){ return data;}
    public void run(){/* 子スレッド実行 */
        //data.add();(コメントアウトすると実行エラーが出る)
        System.out.println("Runnableインタフェース:子スレッド"+ID+" = "+data.toString());
    }
    public static void main(String[] args){
        ThreeMusketeers instance1 = new ThreeMusketeers();
        RunnableMusketeers rt1 = new RunnableMusketeers();/* 第一スレッド用 */
        rt1.data = instance1;
        rt1.ID = 1;
        rt1.name = "スレッド1";
        Thread thread1 = new Thread(rt1);/* 第一スレッド生成 */

        ThreeMusketeers instance2 = new ThreeMusketeers();
        RunnableMusketeers rt2 = new RunnableMusketeers();/* 第二スレッド用 */
        rt2.data = instance2;
        rt2.ID = 2;
        rt2.name = "スレッド2";
        Thread thread2 = new Thread(rt2);/* 第二スレッド生成 */

        thread1.start();/* 第一スレッドのrunメソッドの呼出し */
        thread2.start();/* 第二スレッドのrunメソッドの呼出し */
        System.out.println("mainの終了");
    }
}
データを改変できないようにしたため、16行目をコメントアウトすると、実行時エラーが発生します。 実行結果は以下のようです。

$ javacu RunnableMusketeers.java

$ javau RunnableMusketeers
mainの終了
Runnableインタフェース:子スレッド2 = [アラミス, ポルトス, アトス]
Runnableインタフェース:子スレッド1 = [アラミス, ポルトス, アトス]
より強固なデータ保護を用いたマルチスレッドプログラム例

$ javacu RunnableMusketeers.java

$ javau RunnableMusketeers
Exception in thread "Thread-1" mainの終了
Exception in thread "Thread-0" java.lang.UnsupportedOperationException
        at java.util.Collections$UnmodifiableCollection.add(Collections.java:1055)
        at ThreeMusketeers.add(ThreeMusketeers.java:25)
        at RunnableMusketeers.run(RunnableMusketeers.java:16)
        at java.lang.Thread.run(Thread.java:748)
java.lang.UnsupportedOperationException
        at java.util.Collections$UnmodifiableCollection.add(Collections.java:1055)
        at ThreeMusketeers.add(ThreeMusketeers.java:25)
        at RunnableMusketeers.run(RunnableMusketeers.java:16)
        at java.lang.Thread.run(Thread.java:748)
16行目をコメントアウトすると実行時にエラーが出る


並列化ソーティング

以下は、Java8から導入された並列化(マルチスレッド)ソーティングを、 高解像度画像(270,144,000~2億7千万ピクセル)の画素を整数として、 Arrays.sortによるシリアルなソーティングと、 Arrays.parallelSortによるパラレルなソーティングを行った例です。 興味があれば、自宅等、Windows環境で実行してみてください。
Java8Sort.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
	プログラム5-13 Java8から導入された並列ソーティング例(以下のURL参照)
	http://www.drdobbs.com/jvm/parallel-array-operations-in-java-8/240166287
*/
import java.awt.image.*;
import java.io.File;
import java.util.Arrays;

public class Java8Sort {
    public void sortIt(int[] src, boolean parallel) {
        try {
            System.out.println("--配列サイズ: " + src.length);
            long start = System.currentTimeMillis();
            if ( parallel == true ) 
                Arrays.parallelSort(src);/* Java8で導入された並列ソーティング */
            else 
                Arrays.sort(src);/* Java7までで使用できるシステムのソーティング */
            long end = System.currentTimeMillis();
            System.out.println(
                "--ソーティング経過時間: " + (end-start)+" ミリ秒");
        }
        catch ( Exception e ) {
            e.printStackTrace();
        }
    }
     
    private int[] getData(String fname) {
        try {
            File file = new File(fname);
            BufferedImage image = javax.imageio.ImageIO.read(file);
            int w = image.getWidth();/* 画像の横サイズ */
            int h = image.getHeight();/* 画像の縦サイズ */
            int[] src = image.getRGB(0, 0, w, h, null, 0, w);
            int[] data = new int[src.length * 20];
            for ( int i = 0; i < 20; i++ ) {/* 画像を20倍(反復的に)コピーする */
                System.arraycopy(src, 0, data, i*src.length, src.length);
            }
            return data;
        }
        catch ( Exception e ) {
            e.printStackTrace();
        }
        return null;
    }

    public static void main(String[] args) {
        System.out.println("画像ファイル名:"+args[0]);
        Java8Sort mySort = new Java8Sort();

        int[] src = null;
         System.out.println("\nシリアルなソーティング:");
        src = mySort.getData(args[0]);
        mySort.sortIt(src, false);
 
        System.out.println("\n並列化ソーティング:");
        src = mySort.getData(args[0]);
        mySort.sortIt(src, true);
    }
}
この例では、 Java5から導入されたBufferedImageというクラスを用いています。 画像の読み込みには、javax.imageio.ImageIOクラスread関数を使っています。 実行結果は以下のようです。

$ javacu Java8Sort.java

$ javau Java8Sort Fuji.jpg
画像ファイル名:Fuji.jpg

シリアルなソーティング:
--配列サイズ: 16884000
--ソーティング経過時間: 770 ミリ秒

並列化ソーティング:
--配列サイズ: 16884000
--ソーティング経過時間: 214 ミリ秒
並列化ソーティング事例




Javaによるマルチスレッド・プログラミングに関して、 今回の資料で紹介したのは、 ほんの氷山の一角にすぎません。 たとえば、java.util.concurrentパッケージには、様々な並列化のためのクラスや関数が用意されています。 興味があれば、たとえば「Java並列処理プログラミング」 (ブライアン・ゲーツ、ダグ・リー著、岩谷宏訳) ソフトバンク社)などの書籍で更に勉強してください。

アルゴリズムの実装例(その2)

アルゴリズムの実装例その2として、クラスタリング(clustering)を紹介します。 クラスタリングはデータマイニングの基本技術のひとつです。 一般に多次元の数値データ \[ x_{i} = (x_{i,1}, x_{i,2}, ..., x_{i,n}), \;\; i=1,...,N \] が全体でN個与えられたとき、これをk個のグループに分けたい、という場合に使用するアルゴリズムを広くクラスタリング・アルゴリズムと呼びます。 もっとも有名なアルゴリズムはk-means法(k-平均法)と呼ばれるものです。 古典的なk-means法は以下にリストするような手順で動作します。

  1. k個の重心点をランダムに生成する。
  2. 以下を重心点の移動がなるなるか、あるいは、反復回数がある一定以上になるまで繰り返す。
    1. 各データ点に対してすべての重心までの距離を再計算し、最も近い重心を含むクラスターに再割当する
    2. 新たなデータで重心を再計算する
以下では、2次元の点群に対して、距離をユークリッド距離で与え、k-means法でクラスタリングするアルゴリズムを紹介します。 最初は、2次元の点を表すPointクラスです。
Point.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
	プログラム5-14 Point.java
*/
import java.util.ArrayList;/* ArrayListクラス */
import java.util.List;/* Listクラス */
import java.util.Random;/* Randomクラス */
 
public class Point {
    private double x = 0;/* x座標 */
    private double y = 0;/* y座標 */
 
    public Point(double x, double y) {/* コンストラクタ */
        this.setX(x);
        this.setY(y);
    }
    public void setX(double x) {   this.x = x;  }
    public double getX()  {  return this.x;  }
    public void setY(double y) {   this.y = y; }
    public double getY() { return this.y; }
    public String toString() { 
       	return 
   		"("+	String.format("%5.2f",x)
   		+","+	String.format("%5.2f",y)
   		+")";   

    /*2点間の距離を計算するstaticメソッド */
    public static double distance(Point p, Point centroid) {
        return 
        	Math.sqrt(Math.pow((centroid.getY() - p.getY()), 2) + 
        	Math.pow((centroid.getX() - p.getX()), 2));
    }

    /* ランダムに点を生成する */
    public static Point createRandomPoint(int min, int max) {
    	Random r = new Random();
    	double x = min + (max - min) * r.nextDouble();
    	double y = min + (max - min) * r.nextDouble();
    	return new Point(x,y);
    }

	/* ランダムに点を生成し、ArrayListで保持する */
    public static List <Point> createRandomPoints(int min, int max, int number) {
    	List <Point>points = new ArrayList<Point>(number);
    	for (int i = 0; i < number; i++) {
    		points.add(createRandomPoint(min,max));
    	}
    	return points;
    }
}
次に、重心などのデータをメンバー変数として持つClusterクラスを作ります。
Cluster.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
	プログラム5-15 Cluster.java
*/
import java.util.ArrayList;
import java.util.List;
 
public class Cluster {/* クラスタークラス */

	public List <Point> points;/* Pointクラスのオブジェクトからなる可変長List */
	public Point centroid;/* 重心 */
	public int id;/* クラスターID */

	public Cluster(int id) {/* コンストラクタ */
		this.id = id;
		this.points = new ArrayList <Point>();
		this.centroid = null;
	}

	public List <Point> getPoints() { return points;}/* Listを返す */
	public void addPoint(Point point) { points.add(point);	}/* Listに追加 */
	public void setPoints(List <Point> points) { this.points = points;}/* 点Listを代入 */
	public Point getCentroid() {return centroid;}/* 重心を返す */
	public void setCentroid(Point centroid) {this.centroid = centroid;}/* 重心をセット */
	public int getId() {return id;}/* IDを返す */
	public void clear() {points.clear();} /* Listをクリア */

	public void printCluster() {/* クラスター情報をプリント */
		System.out.println("[クラスター: " + id+"]");
		System.out.println("[重心: " + centroid + "]");
		System.out.println("[点リスト情報: \n");
		for (Object o : points) {
			Point p = (Point)o;
			System.out.println(p);/* PointクラスのtoStringを呼び出す */
		}
		System.out.println("]");
	}
}
上述したシンプルなアルゴリズムで動作するkmeans法の本体部分の実装例を紹介します。
KMeans.java
1 
2 
3 
4 
5 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
	プログラム5-16 KMeans.java
*/ 
import java.util.ArrayList;
import java.util.List;
 
public class KMeans {/* kmeans法クラス */
 
    private int NUM_CLUSTERS = 3;    /* ここでは生成するクラス数k=3と固定 */
    private int NUM_POINTS = 20;/* ランダムに生成する点の数 */
    private static final int MIN_COORDINATE = 0;/* 最小値 */
    private static final int MAX_COORDINATE = 10;/* 最大値 */
    private static final int MAX_LOOP = 100;/* 最大ループ数 */
    private static final double THRESHOLD = 0.001;/* 閾値 */

    private List <Point>points;/* 点の可変長リスト */
    private List <Cluster>clusters;/* クラスターの可変長リスト */

    public KMeans() {/* コンストラクタ */
    	this.points = new ArrayList <Point>();
    	this.clusters = new ArrayList <Cluster>();    	
    }
    public void init() {/* 初期化 */
    	/* 点の生成 */
    	points = Point.createRandomPoints(
    		MIN_COORDINATE,MAX_COORDINATE,NUM_POINTS);
    	/* (初期)クラスターの生成 , 重心はランダムに生成 */
    	for (int i = 0; i < NUM_CLUSTERS; i++) {
    		Cluster cluster = new Cluster(i);
    		Point centroid = Point.createRandomPoint(MIN_COORDINATE,MAX_COORDINATE);
    		cluster.setCentroid(centroid);/* 重心のセット */
    		clusters.add(cluster);/* リストへ追加 */
    	}
    	printClusters();/* 初期クラスターのプリント */
    }
	private void printClusters() {/* クラスターのプリント */
    	for (int i = 0; i < NUM_CLUSTERS; i++) {
    		Cluster c = clusters.get(i);/* ArrayListからデータをゲット */
    		c.printCluster();
    	}
    }
    private void clearClusters() {/* クラスター情報のクリア */
    	for(Cluster cluster : clusters)	cluster.clear();
    }
     private List <Point> getCentroids() {/* 重心の計算 */
    	List <Point> centroids = new ArrayList <Point>(NUM_CLUSTERS);
    	for (Cluster cluster : clusters) {
    		Point cent = cluster.getCentroid();
    		Point point = new Point(cent.getX(),cent.getY());
    		centroids.add(point);/* 再計算した重心を重心リストに追加 */
    	}
    	return centroids;
    }
    private void assignCluster() {/* クラスターの割当 */
        double max = Double.MAX_VALUE;
        double min = max; 
        int cluster = 0;                 
        double distance = 0.0; 
        for (Point point : points) {/* 点リスト内のすべての点でループ */
        	min = max;
        	for (int i = 0; i < NUM_CLUSTERS; i++) {
          		Cluster c = clusters.get(i);
          		distance = Point.distance(point, c.getCentroid());
          		if (distance < min){/* より近い重心が見つかった! */
              		    min = distance;
             		    cluster = i;/* クラスターの再割当 */
         		}
       		}
                clusters.get(cluster).addPoint(point);
        }
    }
    private void calculateCentroids() {/* 重心計算 */
        for (Cluster cluster : clusters) {
            double sumX = 0;
            double sumY = 0;
            List <Point> list = cluster.getPoints();
            int n_points = list.size();

            for (Point point : list) {/* 足しこむ */
            	sumX += point.getX();
            	sumY += point.getY();
            }
            Point centroid = cluster.getCentroid();
            if (n_points > 0) {/* 平均をとる */
            	double newX = sumX / n_points;
            	double newY = sumY / n_points;
              centroid.setX(newX);
              centroid.setY(newY);
            }
        }
    }
    /* k-means本体 */
    public void calculate() {
        int iteration = 0;
        while (true) {
        	clearClusters();/* クラスター情報のリセット*/
        	List <Point> lastCentroids = getCentroids();
        	assignCluster();/* クラスターの割当 */
        	calculateCentroids();/* 重心の再計算 */
        	iteration++;
        	List <Point> currentCentroids = getCentroids();
        	/* 新重心と旧重心との距離差計算 */
        	double distance = 0;
        	for (int i = 0; i < lastCentroids.size(); i++) {
        		distance += Point.distance(lastCentroids.get(i),currentCentroids.get(i));
        	}
        	System.out.println("#################");
        	System.out.println("反復回数: " + iteration);
        	System.out.println("重心までの距離: " + String.format("%5.2f",distance));
        	printClusters();
        	if (Math.abs(distance) < THRESHOLD || iteration>MAX_LOOP) break;
        }
    }

    public static void main(String[] args) {
    	KMeans kmeans = new KMeans();
    	kmeans.init();/* 初期化 */
    	kmeans.calculate();/* kmeans本処理 */
    }
}
実行結果は以下のようです。

$ javacu Point.java
$ javacu Cluster.java
$ javacu KMeans.java
$ javau KMeans
[クラスター: 0]
[重心: ( 6.30, 5.40)]
[点リスト情報:

]
[クラスター: 1]
[重心: ( 8.41, 3.92)]
[点リスト情報:

]
[クラスター: 2]
[重心: ( 8.20, 7.46)]
[点リスト情報:

]
kmeans法のコンパイルと実行の様子
#################
反復回数: 6
重心までの距離:  0.00
[クラスター: 0]
[重心: ( 0.88, 4.11)]
[点リスト情報:

( 0.05, 3.72)
( 0.77, 7.78)
( 0.61, 3.49)
( 1.14, 4.28)
( 1.85, 1.29)
]
[クラスター: 1]
[重心: ( 7.15, 2.77)]
[点リスト情報:

( 8.83, 3.12)
( 6.61, 0.83)
( 5.26, 2.81)
( 6.87, 3.03)
( 9.49, 3.33)
( 5.86, 3.47)
]
[クラスター: 2]
[重心: ( 6.30, 6.83)]
[点リスト情報:

( 4.57, 5.70)
( 7.47, 5.76)
( 8.62, 9.48)
( 4.96, 8.52)
( 4.31, 7.09)
( 6.87, 6.08)
( 4.35, 8.19)
( 8.39, 5.70)
( 7.15, 5.00)
]
収束したときのクラスターの様子