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

本日の内容

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

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

4-1. 計算量

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

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

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

関数のオーダ

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

定義

関数 $T_1\left(n\right)$ 、 $T_2\left(n\right)$ が $T_1\left(n\right)=O\left(T_2\right(n\left)\right)$ であるとは次を満たすことを言う。 ある定数 $N_0$ が存在し、すべての $N>N_0$ に対して $T_1\left(N\right)<c{T}_2\left(N\right)$ が成り立つような定数 c を見つけられることである。

直感的には $T_1\left(n\right)=O\left(T_2\right(n\left)\right)$ は $T_1\left(n\right)\le T_2\left(n\right)$ を意味します。つまり、 $T_1\left(n\right)$ n が大きくなるにつれ、増大するスピードがせいぜい $T_2\left(n\right)$ 程度であるという関係です。 但し、直接の大小関係ではなく、増加の速度の比較になっています。

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

1. $c{T}_1\left(n\right)=O\left(T_1\left(n\right)\right)$
2. $T_1\left(n\right)=O\left(T_2\left(n\right)\right)$ なら、 $T_1\left(n\right)+T_2\left(n\right)=O\left(T_2\left(n\right)\right)$

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

このオーダがプログラムの実行速度を表すのに都合が良いのは以下の点です。 まず、定数倍を無視 できることで、コンピュータの 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;
	    System.out.println(array[m]);
	    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));
    }
}

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

4-2. 例外

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

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

例4-2

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

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

Java では プログラムの本来の流れと、それ以外に必要な異常事態への対処のためのプロ グラムを分けるために、例外処理という概念があります。 Java では例外は java.lang.Exception クラスのサブクラスのオブジェクトです。 これを throw すると、プログラムは例外処理をします。 プログラムの例外処理には次の二つの方法があります。

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

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

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

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

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

文字列の操作

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

String

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

文字配列的な処理

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

例4-3

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

文字列処理

substring は文字列の特定の位置を指定して部分列を取り出すメソッド、 replace は文字の入れ替え、 toUpperCase, toLowerCase はそれぞれ大文字、小文字へ変換した文字列を返 します。

例4-4

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-5

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-6

String line = br.getline();
byte[] code = line.getBytes("iso-8859-1");
String str = new String(code,"shift_jis");

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

例4-7

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

構文解析

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

例4-8

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

例4-9

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-10

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

ファイルの取扱い

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

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.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 することを、メソッド宣言の時に throws の後に throw する Exception を列挙して宣言します。 なお、なんらかの例外が発生したとき(ファイルが見つからないなど)、プログ ラムを終了させたくないときは try catch 文で対応する必要があります。

例4-11

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.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 は要素の削除ですが、これらは実装方法により計算量 が下記のように異なります。

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

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

例4-12

「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-13

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("07ec%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();
	}
    }
}

演習問題

演習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

11
42
35
5
1

演習4-3

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

入力例

test3.txt

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

実行例

java Ex3 test3.txt

4033

演習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