第 4 回計算量、クラスライブラリの利用

本日の内容

4-1. 計算量
4-2. 例外
4-3. Java のクラスライブラリ
4-4. ラムダ式

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

4-1. 計算量

プログラムの実行時間や、使用するメモリ量を評価するには注意が必要です。よく行われる例として、特定の入力、特定のコンピュータでの実行時間の計測値を示すことがあります。これは、特定のアルゴリズムの実用性などを示す目安にはなりますが、二つのプログラムの比較にこの特定条件下の測定値を使うことはできません。

これは、特定の処理をするためのプログラムが無限に存在するということと、特定の入力に対する出力を覚えておいて、それを出力するだけのプログラムが作れるという事実によります。さらに、同時に処理するプログラムの処理数を変えることにより、プログラムの実行速度を定数倍速くできます。これは、現在のパソコンが 32bit から 64bit に移行していますが、これは扱えるメモリの量が増えるだけでなく、プログラムの処理速度も向上します。このように、特定の入力、特定のコンピュータによる実実行時間の比較はプログラムの性能を正確に示せません。

そこで、プログラムの計算速度や、プログラムのメモリの使用量などを比較するのにオーダ表示を使用します。

関数のオーダ

オーダの厳密な定義は次の通りです。

定義

関数 $T_{1} (n)$ 、 $T_{2} (n)$ が $T_{1} (n) = O (T_{2} (n))$ であるとは次を満たすことを言う。ある定数 $N_{0}$ が存在し、すべての $N > N_{0}$ に対して $T_{1} (N) < c T_{2} (N)$ が成り立つような定数 c を見つけられることである。

直感的には $T_{1} (n) = O (T_{2} (n))$ は、増え方の意味において $T_{1} (n) \leq T_{2} (n)$ を意味します。つまり、 $T_{1} (n)$ n が大きくなるにつれ、増大するスピードがせいぜい $T_{2} (n)$ 程度であるという関係です。但し、直接の大小関係ではなく、増加の速度の比較になっています。

このオーダには次のような性質があります。

$c T_{1} (n) = O (T_{1} (n))$
$T_{1} (n) = O (T_{2} (n))$ なら、 $T_{1} (n) + T_{2} (n) = O (T_{2} (n))$

1 番目の性質は、定数倍は無視できるという性質です。つまり、 $2 n^{3} = O (n^{3})$ となります。一方、 2 番目の性質は、複数の項がある時、もっとも増加速度の速い項以外は無視できるという性質です。つまり、 $n^{3} + n^{2} = O (n^{3})$ となります。

このオーダがプログラムの実行速度を表すのに都合が良いのは以下の点です。まず、定数倍を無視できることで、コンピュータの bit 数による違いを無視できることです。さらに、増え方に注目しているため、特定の入力に対して高速に出力するようなプログラムに対しても、総合的な性能を示すことができます。

例4-1

それではここでプログラムの実行速度のオーダを求めてみましょう。ここでは厳密な計算量を求めるのではなく、 if 文の実行回数を求めることにしましょう。


class Rei31 {
    private static int search1(int key, int[] array){
	int i;
	for(i=0; i<array.length; i++){
	    if(key==array[i]){break;}
	}
	return i;
    }
    private static int search2(int key, int[] array){
	int s=0, e=array.length-1, m;
	while(s<=e){
	    m=(s+e)/2;
	    if(key==array[m]){return m;}
	    if(key<array[m]){e=m-1;}
	    else{s=m+1;}
	}
	return array.length-1;
    }
    private static int search3(int key, int[] array){
	int i;
	while(true){
	    i=(int)(Math.random()*array.length);
	    if(key==array[i]){return i;}
	}
    }
    private static int search4(int key, int[] array){
	int i;
	if(key==8){return 3;}
	while(true){
	    i=(int)(Math.random()*array.length);
	    if(key==array[i]){return i;}
	}
    }
    public static void main(String[] arg){
	int[] array = { 1,2,4,8,16,32 };
	System.out.println(search1(8,array));
	System.out.println(search2(8,array));
	System.out.println(search3(8,array));
	System.out.println(search4(8,array));
    }
}

まず search1 は素朴な線形探索と呼ばれるものです。長さ n の配列に対して、平均で n/2 回、最悪で n 回 if 文が実行されますので、 $O (n)$ となります。
search2 はバイナリーサーチです。したがって、 $O (log n)$ となります。
search3 は配列の要素をランダムに選択して、たまたま求める値が見つかったらその添字を返すものです。最悪は永遠に止まりませんが、その確率は 0 です。そこで、平均値を求めます。要素数 n の配列の値が k 回目に見つかる確率は、 k-1 回外して最後に当てる確率なので次のようになります。
$Pr [k, 回目に見つかる] = {(\frac{n - 1}{n})}^{k - 1} \frac{1}{n}$
したがって、見つかるまでに繰り返す平均回数を求めると次のようになります。
$平均回数 = \sum_{k = 1}^{\infty} k Pr [k, 回目に見つかる] = \sum_{k = 1}^{\infty} k {(\frac{n - 1}{n})}^{k - 1} \frac{1}{n}$
ここで、 $S_{m} = \sum_{k = 1}^{m} k {(\frac{n - 1}{n})}^{k - 1} \frac{1}{n}$ と置きます。
$S_{m} = \frac{1}{n} + 2 \frac{n - 1}{n} \frac{1}{n} + 3 {(\frac{n - 1}{n})}^{2} \frac{1}{n} + ... + m {(\frac{n - 1}{n})}^{m - 1} \frac{1}{n}$
これから $\frac{n - 1}{n} S_{m} = \frac{n - 1}{n} \frac{1}{n} + 2 {(\frac{n - 1}{n})}^{2} \frac{1}{n} + ... + (m - 1) {(\frac{n - 1}{n})}^{m - 1} \frac{1}{n} + m {(\frac{n - 1}{n})}^{m} \frac{1}{n}$ を辺々から引くとつぎのようになります。
$(1 - \frac{n - 1}{n}) S_{m} = \frac{1}{n} + \frac{n - 1}{n} \frac{1}{n} + {(\frac{n - 1}{n})}^{2} \frac{1}{n} + ... + {(\frac{n - 1}{n})}^{m - 1} \frac{1}{n} - m {(\frac{n - 1}{n})}^{m} \frac{1}{n}$
これを辺々整理すると次のようになります。
$\frac{1}{n} S_{m} = \frac{1 - {(\frac{n - 1}{n})}^{m}}{1 - \frac{n - 1}{n}} \frac{1}{n} - m {(\frac{n - 1}{n})}^{m} \frac{1}{n}$
$S_{m} = n - n {(\frac{n - 1}{n})}^{m} - m {(\frac{n - 1}{n})}^{m}$
これに対して、 m に対する極限をとると、 $lim_{m \to ∞} S_{m} = n$ となるので、平均実行速度は $O (n)$ となります。

4-2. 例外

プログラムの処理において目的の処理の失敗などの異常な動作が起きます。想定内の状況と、想定外の状況が存在します。つまり、プログラムの流れにおいて必然的に生じる異常な状況と、必然ではなく例外的な異常な状況です。この必然性に応じてプログラミングの形態を変えるようにします。

例えば、ファイルから文字を読むとき、ファイルが終了したら処理を終える必要があります。この場合、ファイルは必ず終わりますので、必然的に生じる異常事態です。このような場合は、文字を読むたびごとにファイルの終了を検査し、終了したら他の処理をするようにプログラムを書きます。つまり、異常事態は常に想定すべき状況なので、プログラムの流れに異常状態での処理を組み込みます。

例4-2


while(ファイルが終了するまで一文字読み込む){
    読み込んだ文字の処理
}

一方で、ファイルを読み込む際にファイルが存在しなかったときなどは、プログラムの流れからして、必然の状況ではありません。しかし、通常、ファイルが存在しなかった時はもう一度ファイル名を再入力させるなど、処理を戻して繰り返すようにします。このファイルが存在しないような異常事態は、本来のプログラムの流れではありません。

Java ではプログラムの本来の流れと、それ以外に必要な異常事態への対処のためのプログラムを分けるために、例外処理という概念があります。 Java では例外を表すオブジェクトクラスがあります。それは java.lang.Exception クラスのサブクラスになっています。これらは例外が生じたとき、その例外を表すクラスのオブジェクトが発行され、例外処理に送られます。一方、例外オブジェクトを throw することで、意図的に例外を発生させることができます。

プログラムの例外処理には次の二つの方法があります。

想定される例外のクラスを、あらかじめメソッドの定義文に throws で記述しておくと、例外が発生した時にメソッド中の処理を中断して、そのメソッドの呼び出し側へ同じ例外を投げます。
try 文で囲まれた中で例外が発生した場合は、対応する例外クラスを補足する catch 節に処理を移します。

原則的には例外を投げるメソッドを扱う場合はこのどちらの措置がされていないとコンパイル時にエラーがでます。

例4-3

下記はコンパイルするとエラーが出ます。


class SomeException extends Exception {
    public SomeException(){
	super();
    }
}
class Rei {
    private static void foo() throws SomeException {
	throw new SomeException();
    }
    public static void main(String[] arg){
	foo();
    }
}

main で throws を付けるとエラーが消え、Exception が発生すると、例外が表示されます。


    public static void main(String[] arg) throws SomeException {

C:\work> java Rei
Exception in thread "main" SomeException
	at Rei.foo(exception.java:8)
	at Rei.main(exception.java:11)

一方、try により例外を受け付け、処理を行うようにもできます。


    public static void main(String[] arg){
	try{
	    foo();
	}catch(SomeException e){
	    System.err.println(e);
	}
    }

java.lang.Exception の toString 関数はクラス名を返すようです。

但し、 java.lang.RuntimeException のサブクラスの例外に関してはこのような措置をしなくてもよいことになっています。このような措置しなくてもよい例外の中には IndexOutOfBounds(配列の領域を越えてしまった) や NullPointerException(なにも参照していない) など、プログラムを動かさないと分からないけど、生じたときは重大な誤りとなるものが含まれます。つまり、これらは正しいプログラムの実行時に起こり得ない例外です。これらは「想定内の例外処理」で解決させるのではなく、プログラムの誤りとして一切発生しないようにプログラムを修正する必要があります。

4-3. Java のクラスライブラリ

今回は多用するクラスライブラリを俯瞰します。

java.lang.String

C 言語では配列として扱った文字列ですが、 Java ではオブジェクトとして扱います。 String 型は変更のできない文字列オブジェクトです。また、StringBuffer と Java 5 から追加された StringBuilder はともに文字の挿入や追加ができる可変長文字列の型です。文字列を1文字ずつ生成していくような場合は StringBuilder を用います。なお、 StringBuilder は制約がありますが、 StringBuffer より高速なようです。

String オブジェクトは他のオブジェクトと異なり、"abc" など定数の表現があります。しかも、文字列定数にもメソッドを適用できます。また、 + 演算子で連結した新しい String オブジェクトを生成します。

文字配列的な処理

文字配列的な処理として、指定した位置の文字を返す charAt メソッドや、長さを返す length メソッド、空かどうかを調べる isEmpty メソッドがあります。

例4-4


String str = "xyz";
int x = 0;
if(!str.isEmpty()){
  char c = str.charAt(2);
  x = str.length();
}

文字列処理

substring は文字列の特定の位置を指定して部分列を String オブジェクトとして生成するメソッド、 replace は文字の入れ替えた、 toUpperCase, toLowerCase はそれぞれ大文字、小文字へ変換した文字列を String オブジェクトとして返します。

例4-5


String str1 = "abcdefg".substring(3,5);
String str2 = "abcdefg".replace('c','x');
String str3 = "abcdefg".toUpperCase();

比較

通常比較したい文字列を引数にとり、条件を満たすかを調べるメソッドがいくつかあります。 compareTo は辞書的な順序を結果として-1, 0, 1 を返すメソッド。 equals は文字列の中身を比較します。 equalsIgnoreCase では大文字小文字の区別をしない比較になります。 startsWith, endsWith はそれぞれ与えた文字列と先頭部分、終端部分が等しいか判定します。

また、indexOf は特定の文字を探して、該当個所の位置を返すメソッドです。

例4-6


String str="abc";
int value=0;
if(str.compareTo("aaa")<0){
  if(str.endsWith("bc")){
    value=str.indexOf("bc");
  }
}

データ変換

データ変換には char[] 型の配列から文字列を生成するコンストラクタの他に、 byte[] 型の配列と文字コードを指定して、文字コード変換をしながら文字列オブジェクトにするコンストラクタもあります。これは、getBytes メソッドと組み合わて使うと、ファイルの文字列の漢字変換などに使用できます。例えば、ファイルから一行読み込んだとき、文字列変数 str は String 型になります。しかし、内部の文字コードが Shift_JIS の場合、そのまま表示しようとすると文字化けを起こし、正常に処理できません。そのような時、一旦、データ表現を byte[] 型に直した後、文字コードを指定して String コンストラクタにあたえると、正常な文字列に変換される。なお、 byte[] 型に変換する際、文字列を表現してる byte の列がすべてそのまま無変換で出てくるように、文字コードとして 8bit が 1 byte になっている文字コードを指定します。この文字コードには例えば ISO-8859-1 (西ヨーロッパ圏の文字コード)があります。

例4-7


// br は java.io.BufferedReader を想定
String line = br.getline();
byte[] code = line.getBytes("iso-8859-1");
String str = new String(code,"shift_jis");

この他、valueOf() クラスメソッドは基本型を文字列表現に変換します。さらに、 format クラスメソッドは C 言語の sprintf と同様の引数を取り、データから文字列を作ります。

例4-8


System.out.println(String.valueOf(1)+String.valueOf(0.123));
System.out.println(String.format("%2.3f",3.141592));

構文解析

正規表現という文字列のパターンを決める表現が存在します。そのような表現に対して、 matches はそのパターンに適合するかを調べます。一方、 split はそのパターンにより文字列を区切り、文字列の配列を返します。但し、文字列の先頭が区切り文字の場合、得られる配列の最初は空の文字列になります。なお、正規表現はデータ構造とアルゴリズム II で詳しく説明します。

例4-9


String str = "齊藤";
if(str.matches("(齊藤|斎藤|斉藤|齋藤)")){
    System.out.println("さいとう");
}

例4-10


class Rei {
    public static void main(String[] arg){
	String str = "abc123 def 456ghi-789";
	String[][] data = new String[3][];
	data[0] = str.split("\\s+"); // 空白の一文字以上の連続
	data[1] = str.split("\\D+"); // 非数字の一文字以上の連続
	data[2] = str.split("\\W+"); // 英数字以外の一文字以上の連続
	for(String[] strArray : data ){
	    for(String s : strArray){
		System.out.println(s);
	    }
	}
    }
}

ラッパクラス

基本型をオブジェクトにするために使うのが本来のラッパクラスです。そのため、基本型の値を取るコンストラクタと、値を取り出すメソッドがあります。通常は基本型の一文字目を大文字にしたのがラッパクラス名ですが、 int は Integer になります。

値を取り出すメソッドは (型名)Value メソッドです。また、静的関数には文字列から基本型の値を取り出す parse(型名) メソッドがあります。なお、文字列の表現はコンストラクタに入れればそのままラッパクラスのオブジェクトになります。

例4-11


Integer a = new Integer(3);
int b = a.intValue();
Integer c = new Integer("30");
int d = Integer.parseInt("40");

なお、文脈により基本型とラッパクラスとの型変換が必要な場合は、自動的にコンストラクタや (型名)Value メソッドが挿入されます(オートボクシング、オートアンボクシング)。

例4-12


class Rei {
    public static void main(String[] arg){
	Integer a = 3; // オートボクシング
	int b = a;  // オートアンボクシング
	Integer c = new Integer("30"); // 文字列は自動変換しません
	int d = Integer.parseInt("40");
    }
}

ファイルの取扱い

ファイルという OS が管理しているデータ単位と、プログラムが取り扱う際のファイルの中身に含まれているデータの列は区別しなければなりません。プログラムがファイルを読み書きする際、最小のデータのやりとりは 1 byte です。その byte を読み書きするごとに、対象となるデータの注目点は一つずつ先に進みます。このような byte あるいは文字が次々と連続しているようなデータ構造をストリームと呼びます。また、対象ファイルに対して読み書きは可能ですが、読み込みと書き込みは同時には行いません。

Java では java.io.File オブジェクトが存在します。一方、ストリームに関しては java.io.InputStream と java.io.OutputStrem があります。この、 java.io.InputSream などは抽象クラスで、例えば、 File から生成される InputStream である java.io.FileInputStream は java.io.InputStream のサブクラスです。

なお、 Java では byte のやりとりと char つまり文字のやりとりが区別されます。文字のやりとりのクラスは java.io.Reader(抽象クラス) です。標準入力である java.lang.System.in は byte を読む InputStream です。一方、java.io.InputStream から文字を読み出すクラスが java.io.InputStreamReader になります。

java.io.Reader は文字を扱うので、テキストファイルを扱えます。そしてそのサブクラスには java.io.BufferedReader クラスがあります。これには getLine メソッドがあります。

Java ではファイルに対して直接行を読むメソッドはありませんが、最終的に java.io.File クラスのオブジェクトを使って、　java.io.BufferedRader クラスのオブジェクトを作れば行の処理を行うことができます。オブジェクトの変換をするには、最終目標のオブジェクトのコンストラクタの引数をたどって、変換したいオブジェクトの型になるようにします。ここで、サブクラスのオブジェクトは親クラスから参照できることに注意します。例えば、 java.io.Reader を引数に持つコンストラクタに java.io.InputStreamReader を与えることができます。

なお、入出力処理には例外が付き物です。ここでは、あらゆる例外処理をせずに異常終了させるため、まず main の定義時にすべての Exception を throw させるため、 java.lang.Exception を throws で指定しています。なお、なんらかの例外が発生したとき(ファイルが見つからないなど)、プログラムを終了させたくないときは try catch 文で対応する必要があります。

例4-13


import java.io.*;
class Rei {
    public static void main(String[] arg) throws Exception {
	File f = new File(arg[0]);
	FileInputStream fis = new FileInputStream(f);
	InputStreamReader isr = new InputStreamReader(fis);
	BufferedReader br = new BufferedReader(isr);
	
	String line;
	while((line = br.readLine())!=null){
	    System.out.println(line);
	}
	br.close();
    }
}

出力に関しては java.io.OutputStream と java.io.Writer が対応しています。

文字コード変換

Java では Stream はバイト列、 Reader は文字列を扱います。そのため、 Stream オブジェクトを Reader のコンストラクタに与える際に、文字コードを与えることで、文字コード変換をさせることができます。

例えば、java.io.InputStream はバイトのストリームを扱います。そのため、 read メソッドはバイトを返します。一方、 java.io.InputStreamReader は文字のストリームを扱います。そのため、 read メソッドは文字を返します。 InputStreamReader に InputStream のオブジェクトと文字コードを与えることで、入力列の文字コード変換を実現します。

例4-14

このプログラムはメモ帳などで utf-8 形式で保存したテキストファイルを java Rei < ファイル名により画面に表示できます。


import java.io.*;
class Rei {
    public static void main(String[] arg) throws Exception {
	InputStreamReader isr = new InputStreamReader(System.in,"utf-8");
	int c;
	while((c=isr.read())!=-1){
	    System.out.print((char)c);
	}
    }
}

なお、ファイルに関しては、 OS で決められている文字コードを使用する場合は、 java.io.FileReader で一気に文字読み込みのできるオブジェクトが作れます。一方、文字コード変換する場合は、 java.io.FileInputStream を作ってから、 InputStreamReader で文字コードを変換します。

例4-15

以下のプログラムにより、utf-8 で書かれたファイルを java Rei ファイル名により画面に表示します。


import java.io.*;
class Rei {
    public static void main(String[] arg) throws Exception {
	File f = new File(arg[0]);
	FileInputStream fis = new FileInputStream(f);
	InputStreamReader isr = new InputStreamReader(fis,"utf-8");
	int c;
	while((c=isr.read())!=-1){
	    System.out.print((char)c);
	}
    }
}

java.util.Collection

java.util パッケージには様々な有用なデータ構造などが組み込まれています。この授業の後半ではこれらの仕組みなどを解説しますが、ここでは簡単な用法を示します。

java.util.Collection インターフェイスは大量のデータを格納するための抽象クラスです。これには格納するデータの型を Generics により指定します。この java.util.Collection のサブクラスには、入れた順序を保存する java.util.List インターフェイスと、複数回入れても一回として扱われる java.util.Set インターフェイスがあります。そして、それぞれ実装したクラスが java.util.ArrayList, java.util.LinkedList, java.util.HashSet, java.util.TreeSet などになります。 java.util.Collection で定義されているメソッドには isEmpty, size の他に、 add, contains, remove メソッドがあります。add は要素の追加、 contains は要素の検索、 remove は要素の削除ですが、これらは実装方法により計算量が下記のように異なります。

クラス	要素の追加	要素の検索	要素の削除	特記事項
ArrayList	$O (n)$	$O (n)$	$O (n)$	ランダムアクセス
LinkedList	$O (1)$	$O (n)$	$O (1)$
HashSet	$O (log n)$	$O (log n)$	$O (log n)$
TreeSet	$O (log n)$	$O (log n)$	$O (log n)$	整列

Collection インターフェイスを実装しているクラスのオブジェクトは for each 構文で値を取り出すことができます。

なお、これだけだと ArrayList が一番効率が悪そうに見えますが、ArrayList は前にも紹介した通り通常の配列と同じような働きをします。つまり index を指定して、任意の位置の要素を $O (1)$ で取得することができます。また、 TreeSet は HashSet と違い、要素を辞書順に取り出すことが可能です。

例4-16

「java Rei 数」で実行すると、 ArrayList, LinkedList, HashSet, TreeSet に対して、それぞれ指定した数のデータを入れ、検索し、削除するのにかかる時間をそれぞれ出力します。


import java.util.*;
class Test {
    private static Integer[] array;
    public static void initialize(int size){
	array = new Integer[size];
	for(int i=0; i<array.length; i++){
	    array[i]=array.length-i;
	}
    }
    private Collection<Integer> col;
    public Test(Collection<Integer> col){
	this.col = col;
    }
    private  void add(){
	for(Integer i : array){
	    col.add(i);
	}
    }
    private void contains(){
	for(Integer i : array){
	    col.contains(i);
	}
    }
    private void remove(){
	for(Integer i : array){
	    col.remove(i);
	}
    }
    public void examine(){
	StopWatch sw = new StopWatch();
	add();
	System.out.print(sw+" ");
	contains();
	System.out.print(sw+" ");
	remove();
	System.out.println(sw);
    }
}
class StopWatch {
    private Date time;
    public StopWatch(){
	time = new Date();
    }
    @Override
    public String toString(){
	Date newtime = new Date();
	String res = String.valueOf((newtime.getTime()-time.getTime())/1000.0);
	time = newtime;
	return res;
    }
}
class Rei {
    public static void main(String[] arg){
	Test.initialize(Integer.parseInt(arg[0]));
	Test[] tests = { new Test(new ArrayList<Integer>()),
			 new Test(new LinkedList<Integer>()),
			 new Test(new HashSet<Integer>()),
			 new Test(new TreeSet<Integer>())};
	System.out.println("add, contains, remove");
	for(Test test : tests){
	    test.examine();
	}
    }
}

java.util.Map

一方 java.util.Map インターフェイスは put メソッドで「キー」と「値」のペアの形の要素の格納ができます。また、値を取り出すときに get メソッドで「キー」を指定します。 Map の実装されたクラスには java.util.HashMap と java.util.TreeMap があります。 HashMap の方が検索は速く、 TreeMap は辞書順に要素を並べることができます。

キーが含まれているかどうかは containsKey メソッドで調べます。また、キーの一覧は keySet メソッドで取り出します。全ての要素を出力したいときなどは entrySet メソッドを使います。 entrySet での戻り値は Set<Map.Entry<K,V>> 型になります。 Map.Entry 型に対して、 getKey メソッドでキーを、 getValue メソッドで値を取り出すことができます。

例4-17


import java.util.*;
class Test {
    private static String[] id;
    private static int[] point;
    public static void intialize(int max){
	id = new String[max];
	point = new int[max];
	for(int i=0; i<id.length; i++){
	    id[i]=String.format("08ec%03d",999-i);
	    point[i]=100-i;
	}
    }
    private Map<String,Integer> map;
    public Test(Map<String,Integer> map){
	this.map = map;
    }
    private void put(){
	for(int i=0; i<id.length; i++){
	    map.put(id[i],point[i]);
	}
    }
    private void contains(){
	for(int i=0; i<id.length; i++){
	    map.containsKey(id[i]);
	}
    }
    private void showKey(){
	for(String key : map.keySet()){
	    System.out.println(key);
	}
    }
    private void showAll(){
	for(Map.Entry<String,Integer> m : map.entrySet()){
	    System.out.println(m.getKey()+": "+m.getValue());
	}
    }
    public void examine(){
	put();
	contains();
	showKey();
	showAll();
    }
}
class Rei {
    public static void main(String[] arg){
	Test.intialize(10);
	Test[] tests = { new Test(new HashMap<String,Integer>()),
			 new Test(new TreeMap<String,Integer>())};
	for(Test test : tests){
	    test.examine();
	}
    }
}

java.util.stream.Stream

Java8 より、データの集まりをマルチコアで処理するために Stream という新しいデーター構造が加わりました。配列や Collection は Stream に変換できます。また、Stream に対しては MapReduce という手法により、マルチコアで効率よく処理できます。

java.util.stream.Stream インタフェースはオブジェクトのデータの集まりに対して操作をするものです。他に、 double 型用の DoubleStream, int 型用の IntStream, long 型用の LongStream があります。

Java8 から、 Collection 型に stream メソッドが追加され、 Stream オブジェクトを生成できます。また、配列に対しては Arrays クラスに stream メソッドが追加されて、 Stream オブジェクトを生成できます。

多くのメソッドはラムダ式を引数に取って、データの操作をします。代表的なメソッドを紹介します。

戻り型	メソッド	機能
<R> Stream<R>	map(Function<? super T,? extends R> mapper)	各要素に与えた mapper を施し、新しい Stream を作り返す
Optional<T>	reduce(BinaryOperator<T> accumulator)	accumulator という2引数の演算により、すべての要素を集計する
void	forEach(Consumer<? super T> action)	各要素に対して action を行う
Stream<T>	filter(Predicate<? super T> predicate)	条件 predicate が true を返す要素のみを取り出し、新しい Stream を作る
Stream<T>	sorted(Comparator<? super T> comparator)	comparator を比較条件として要素を並べる

例4-18

int[] a = {7, 3, 5, 6, 4}; に対しての処理

map: int[] b = Arrays.stream(a).map(x->x+1).toArray();
reduce: int c = Arrays.stream(a).reduce((x,y)->x+y).getAsInt();
forEach: Arrays.stream(a).forEach(System.out::println);
filter: int[] d = Arrays.stream(a).filter(x->(x%2==0)).toArray();
sorted: int[] e = Arrays.stream(a).sorted().toArray();

なお、上記のようにラムダ式という新しい文法が使われています。ラムダ式については次で説明します。

4-4. ラムダ式

default

Java8 では interface に大幅な仕様変更がありました。

Java7 までの interface にはメソッドのシグネチャの宣言はできても、動作の定義はできませんでした。しかし、Java8 では default を指定することで、メソッドの定義ができます。

例4-19


interface Function<T> {
    default T apply(T x){
        return x;
    }
}

default で指定されたメソッドは abstract になり得ません。

FunctionalInterface

abstract メソッドが一つだけの interface を FunctionalInterface と呼びます。 FunctionalInterface に対してその一つだけのメソッドを実装したインスタンスを生成するのに、次節で説明するラムダ式を使うことができます。

なお、 java.lang.Object のメソッドは、インスタンス化するときに自動的にオーバライドされるので、abstract とはみなしません。従って、 compareTo と equals の二つが定義されていた java.util.Comparable は FunctionalInterface となります。

また、コンパイル時のチェックをするために @FunctionalInterface というアノテーションが定義されています。

例4-20


@FunctionalInterface
interface Function<T>{
    T apply(T x);
}

java.util.function パッケージのインターフェイス

java.util.function 内に定義されている FunctionalInterface の分類は下記の通りです。

引数オブジェクト

引数の数	戻り値 void	戻り値 boolean	戻り値オブジェクト	戻り値 double	戻り値 int	戻り値 long
引数なし		BooleanSupplier	Supplier
1引数	Consumer	Predicate	Function, UnaryOperator	ToDoubleFunction	ToIntFunction	ToLongFunction
2引数	BiConsumer	BiPredicate	BiFunction, BinaryOperator	ToDoubleBiFunction	ToIntBiFunction	ToLongBiFunction
1引数+double	ObjDoubleConsumer
1引数+int	ObjIntConsumer
1引数+long	ObjLongConsumer

引数 double

引数の数	戻り値 void	戻り値 boolean	戻り値 double	戻り値 int	戻り値 long	戻り値オブジェクト
引数なし			DoubleSupplier
1引数	DoubleConsumer	DoublePredicate	DoubleUnaryOperator	DoubleToIntFunction	DoubleToLongFunction	DoubleFunction
2引数			DoubleBinaryOperator

引数 int

引数の数	戻り値 void	戻り値 boolean	戻り値 int	戻り値 double	戻り値 long	戻り値オブジェクト
引数なし			IntSupplier
1引数	IntConsumer	IntPredicate	IntUnaryOperator	IntToDoubleFunction	IntToLongFunction	IntFunction
2引数			IntBinaryOperator

引数 long

引数の数	戻り値 void	戻り値 boolean	戻り値 long	戻り値 double	戻り値 int	戻り値オブジェクト
引数なし			LongSupplier
1引数	LongConsumer	LongPredicate	LongUnaryOperator	LongToDoubleFunction	LongToIntFunction	LongFunction
2引数			LongBinaryOperator

ラムダ式

本来のラムダ式は無名関数の定義を言います。ラムダ式の計算方法や、それに伴う性質などは「計算論」などの専門書を参照して下さい。

Java8 のラムダ式には本来のラムダ式の性質をすべて持ち合わせているわけではありません。しかし、本来のラムダ式に似た記法ができます。基本的な文法は次の通りです。


(型1 仮引数名1, 型2 仮引数名2, ..., 型n 仮引数名n)->{ 手続き }

但し、次のような省略記法があります。

仮引数の型は推論可能であれば省略できる
手続きが一つの文のみの場合、中括弧{} を省略できる
手続きであるただ一つの文が return である時、return も省略できる
引数が一つの場合は先頭の丸括弧を省略できる

例4-21

次の FunctionalInterface を考えます。


@FunctionalInterface
interface Function<T>{
    T apply(T x);
}

これに対するラムダ式として、例えば次を考えます。


Function<Integer> f = (Integer x)->{return x-1;};

これは次とほぼ等価です。


Function<Integer> f = new Function<>(){
    @Override
    public Integer apply(Integer x){
         return x-1;
    }
};

あるいはインナークラスを用いると次のように書けます。


class MyFunction implements Function<Integer>{
    @Override
    public Integer apply(Integer x){
         return x-1;
    }
}
Function<Integer> f = new MyFunction();

これに対して前述の省略構文は次のようになります。

型の省略


Function<Integer> f = (x)->{return x-1;};

中括弧の省略


Function<Integer> f = (x)->return x-1;

return の省略
```
Function<Integer> f = (x)->x-1;
```
丸括弧の省略
```
Function<Integer> f = x->x-1;
```

なお、実際に int 型から int 型へのラムダ式を定義するには、既存のインターフェイスを利用して、次のようにします。


java.util.function.IntUnaryOperator f = x ->x-1;

メソッド参照

様々なメソッドに対して、そのメソッドを FunctionalInterface のメソッドとして実装したオブジェクトとして見なす便利な表記として、メソッド参照があります。これは、メソッド呼び出し表現において、丸括弧と引数を省略する一方、最後のピリオド(.)を二個のコロン(::)に置き換える記法になります。

例4-22


System.out::println
String::valueOf
Arrays::sort

演習問題

演習4-1

java.lang.String クラスを調べ、次のプログラムを作りなさい。

「This is a pen.」など、任意の文字列に対して、文字列の長さと、全部大文字に変換した文字列と、全部小文字に変換した文字列を表示しなさい。


class Ex1 {
      public static void main(String[] arg){
	String str="This is a pen.";
...
    }
}

実行例

java Ex1

14
THIS IS A PEN.
this is a pen.

演習4-2

テキストファイルを読み込んで、各行の長さを出力するプログラムを書きなさい。

入力例

test2.txt

class Rei {
    public static void main(String[] arg){
	System.out.println("Hello World");
    }
}

実行例

java Ex2 test2.txt

演習4-3

テキストファイル中に含まれる数値を非負整数値として読み込み、合計を求めなさい。

入力例

test3.txt

abc123 def 456ghi-789
jkl10+1112 mno 13*14pqr+1516

実行例

java Ex3 test3.txt

演習4-4

テキストファイルを読み込み、行を逆順に出力しなさい。

ヒント

java.util.LinkedList の addFirst メソッドで全ての行を先頭に挿入していくと、ファイルを読み終えた時に、 List 中で逆順になっています。また、 LinkedList も for each 構文で内容を順に取り出すことができます。

入力例

test2.txt

class Rei {
    public static void main(String[] arg){
	System.out.println("Hello World");
    }
}

実行例

java Ex4 test2.txt

}
    }
	System.out.println("Hello World");
    public static void main(String[] arg){
class Rei {

演習4-5

テキストファイルを読み込み、英数字の部分を単語とみなし、単語ごとの出現頻度を計算しなさい。そして、辞書順に単語と頻度を出力しなさい。

ヒント

java.util.TreeMap<String,Integer> のオブジェクトに単語の頻度を集計します。 containsKey メソッドで登録状況を調べ、登録されてない場合は、単語を頻度 1 で登録します。 EntrySet メソッドで Set<Map.Entry<String,Integer>> 型の Set が得られます。これは for each 構文で単語の辞書順に Map.Entry<String,Integer> 型の要素を取り出せます。

入力例

test2.txt

class Rei {
    public static void main(String[] arg){
	System.out.println("Hello World");
    }
}

実行例

java Ex5 test2.txt

Hello: 1
Rei: 1
String: 1
System: 1
World: 1
arg: 1
class: 1
main: 1
out: 1
println: 1
public: 1
static: 1
void: 1

演習4-6

int 型の配列に値が入っているとき、次の動作をするプログラムを、拡張for 文、Stream のそれぞれを使って書きなさい。

全ての値を表示する
合計を求める

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 4 回 計算量、クラスライブラリの利用

本日の内容

4-1. 計算量

関数のオーダ

定義

例4-1

4-2. 例外

例4-2

例4-3

4-3. Java のクラスライブラリ

java.lang.String

文字配列的な処理

例4-4

文字列処理

例4-5

比較

例4-6

データ変換

例4-7

例4-8

構文解析

例4-9

例4-10

ラッパクラス

例4-11

例4-12

ファイルの取扱い

例4-13

文字コード変換

例4-14

例4-15

java.util.Collection

例4-16

java.util.Map

例4-17

java.util.stream.Stream

例4-18

4-4. ラムダ式

default

例4-19

FunctionalInterface

例4-20

java.util.function パッケージのインターフェイス

引数オブジェクト

引数 double

引数 int

引数 long

ラムダ式

例4-21

メソッド参照

例4-22

演習問題

演習4-1

実行例

演習4-2

入力例

test2.txt

実行例

演習4-3

入力例

test3.txt

実行例

演習4-4

ヒント

入力例

test2.txt

実行例

演習4-5

ヒント

入力例

test2.txt

実行例

演習4-6

第 4 回計算量、クラスライブラリの利用