このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
public static なメンバーを利用する際には通常はクラス名で修飾します。
java.lang.System.out.println(java.lang.Math.sin(1)+java.lang.Math.cos(1));
java.lang は省略できますが、相変わらず煩瑣になります。
System.out.println(Math.sin(1)+Math.cos(1));
この繁雑さを避けるため、import static 宣言をすることで、
メンバ名のみで参照することができます。
import static java.lang.System.out; // java.lang は省略不可
import static java.lang.Math.*;
class Rei {
public static void main(String[] arg){
out.println(sin(1)+cos(1));
}
}
なお、これは public static final メンバ、つまり定数の導入にも使えます。 定数の集まりを作るのに interface 宣言でもできますが、これは Constant Interface Antipattern と呼ばれ、避けるべきプログラミングテクニックにな ります。 public static final メンバを集めたい場合はインスタンス化できない実クラス を作成します。 実際に java.lang.Math や java.util.Arrays や java.util.Collections の ようなstatic メンバのみからなるクラスが存在しますが、そのようなクラス ををサービスクラスと言います。
class Constant {
private Constant(){} // インスタンス化を避ける
public static final String TEACHER = "坂本";
}
鉄道や道路の所要時間がわかっている時、ある都市から別の都市への最短の経 路を求める問題を考えましょう。 これはカーナビゲーションシステム、鉄道の乗り換え案内、インターネットの 制御などに応用できる問題です。 例えば次のような状況を考えましょう。 東京電機大学から渋谷に行くのに複数の経路が考えられます。 ここでは次の経路を考えてみましょう。
これらの関係を行列で表すことを考えます。 行と列をそれぞれの地点に対応させ、各成分にはおおよその所要時間を入れま す。また直接行けない地点間は∞で表します。 簡単のために直接行けても∞で表しているところもあります。 一方、乗換え時間は重要ですが、簡単のためにここでは無視します。
| 電機大 | 新お茶の水 | 大手町 | 神保町 | お茶の水 | 神田 | 表参道 | 代々木 | 原宿 | 渋谷 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 電機大 | - | 5 | 13 | 15 | 10 | 10 | ∞ | ∞ | ∞ | ∞ |
| 新お茶の水 | 5 | - | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 大手町 | 13 | 3 | - | 3 | ∞ | ∞ | 12 | ∞ | ∞ | ∞ |
| 神保町 | 15 | ∞ | 3 | - | ∞ | ∞ | 11 | ∞ | ∞ | ∞ |
| お茶の水 | 10 | ∞ | ∞ | ∞ | - | 3 | ∞ | 13 | ∞ | ∞ |
| 神田 | 10 | ∞ | ∞ | ∞ | 3 | - | ∞ | ∞ | ∞ | 25 |
| 表参道 | ∞ | ∞ | 12 | 11 | ∞ | ∞ | - | ∞ | 3 | ∞ |
| 代々木 | ∞ | ∞ | ∞ | ∞ | 13 | ∞ | ∞ | - | 3 | ∞ |
| 原宿 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 3 | 3 | - | 2 |
| 渋谷 | ∞ | ∞ | ∞ | ∞ | ∞ | 25 | ∞ | ∞ | 2 | - |
このような状況でどの経路が最短かを計算させるプログラムを作りましょう。 ここで紹介する方法はダイクストラ法と呼ばれるものです。 この方法では電機大からすべての駅への所要時間が求まります。
import java.util.*;
import static java.lang.Double.MAX_VALUE;
class Dijkstra {
public int[] path;
public double[] dist;
private Dijkstra(){}
public static Dijkstra analize(double[][] mat){
Dijkstra result = new Dijkstra(){};
result.dist = new double[mat.length];
Arrays.fill(result.dist,MAX_VALUE);
result.path = new int[mat.length];
boolean[] flag = new boolean[mat.length];
Arrays.fill(flag,true);
int index=0;
result.dist[0]=0;
result.path[0]=0;
for(int i=0;i<mat.length;i++){
double min = MAX_VALUE;
for(int j=0;j<mat.length;j++){
if(flag[j] && result.dist[j]<min){
index=j;
min=result.dist[j];
}
}
flag[index]=false;
if(min==MAX_VALUE){
throw new IllegalArgumentException("The graph is disconnected");
}
for(int j=0;j<mat.length;j++){
if((result.dist[index]+mat[index][j])<result.dist[j]){
result.dist[j]=result.dist[index]+mat[index][j];
result.path[j]=index;
}
}
}
return result;
}
}
class Rei {
public static void main(String[] arg){
String[] eki={"電機大","新お茶の水","大手町","神保町","お茶の水",
"神田","表参道","代々木","原宿","渋谷"};
double[][] distance = {{0,5,13,15,10,10,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE},
{5,0,3,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE},
{13,3,0,3,MAX_VALUE,MAX_VALUE,12,MAX_VALUE,MAX_VALUE,MAX_VALUE},
{15,MAX_VALUE,3,0,MAX_VALUE,MAX_VALUE,11,MAX_VALUE,MAX_VALUE,MAX_VALUE},
{10,MAX_VALUE,MAX_VALUE,MAX_VALUE,0,3,MAX_VALUE,13,MAX_VALUE,MAX_VALUE},
{10,MAX_VALUE,MAX_VALUE,MAX_VALUE,3,0,MAX_VALUE,MAX_VALUE,MAX_VALUE,25},
{MAX_VALUE,MAX_VALUE,12,11,MAX_VALUE,MAX_VALUE,0,MAX_VALUE,3,3},
{MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,13,MAX_VALUE,MAX_VALUE,0,3,MAX_VALUE},
{MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,3,3,0,2},
{MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,MAX_VALUE,25,3,MAX_VALUE,2,0}};
Dijkstra res = Dijkstra.analize(distance);
for(int j=0;j<distance.length;j++){
System.out.print(eki[j]+" "+res.dist[j]+": ");
int index=j;
do{
System.out.print(" - "+distance[index][res.path[index]]);
System.out.print(eki[res.path[index]]);
index=res.path[index];
}while(index!=0);
System.out.println();
}
}
}
ここで、 path[] 変数には、電機大から来る場合に直前に経由した駅を入れます。 そうすると、最短路が見つかった場合、目的地から順に電機大まで最短経路をた どることができます。
import java.io.*;
import java.util.*;
class Station implements Comparable<Station>{
public Station(String name){
this.name = name;
}
private String name;
@Override
public int compareTo(Station x){
return name.compareTo(x.name);
}
@Override
public boolean equals(Object obj){
if (this == obj) return true;
if (!(obj instanceof Station)) return false;
final Station other = (Station) obj;
if (name == null) return other.name==null;
if(! name.equals(other.name)) return false;
return distance == other.distance;
}
@Override
public int hashCode(){
return name.hashCode();
}
private HashMap<Station,Integer> distances
= new HashMap<Station,Integer>();
public void setDistance( Station sta,Integer dist){
distances.put(sta,dist);
}
public int getDistance(Station s){
return distances.containsKey(s)
? distances.get(s)
: Integer.MAX_VALUE/2;
}
@Override
public String toString(){
return name;
}
private int distance;
public void init(){
distance = Integer.MAX_VALUE/2;
previous = null;
}
public int getDistance(){
return distance;
}
public void modifyDistance(int x){
distance = x;
}
private Station previous;
public void setPrevious(Station s){
previous = s;
}
private String getPreviousList(){
if(previous==null) return "";
return previous.getPreviousList()+"-"+previous;
}
public String getResult(){
return name+":"+getPreviousList()+" "+distance;
}
}
class DistanceComparator implements Comparator<Station>{
public int compare(Station s1, Station s2){
final int res = s1.getDistance()-s2.getDistance();
if(res==0)
return s1.toString().compareTo(s2.toString());
else
return res;
}
}
class StationCollection {
public StationCollection(String[] array){
for(String name : array){
stations.put(name, new Station(name));
}
}
private HashMap<String,Station> stations
= new HashMap<String,Station>();
public void setDistance(String name1, String name2, int dist){
final Station station1 = stations.get(name1);
final Station station2 = stations.get(name2);
station1.setDistance(station2,dist);
station2.setDistance(station1,dist);
}
@Override
public String toString(){
final StringWriter sw = new StringWriter();
final PrintWriter pw = new PrintWriter(sw);
for(Station st : stations.values()){
pw.print(st);
pw.println(st.getDistance());
}
pw.close();
return sw.toString();
}
private TreeSet<Station> stationList;
private void modifyDistance(Station st,int dist){
stationList.remove(st);
st.modifyDistance(dist);
stationList.add(st);
}
private void recalculate(Station s, Station t){
final Integer dist = s.getDistance(t);
if(dist==null) return;
final int newDistance = dist + t.getDistance();
if(newDistance < s.getDistance()){
modifyDistance(s,newDistance);
s.setPrevious(t);
}
}
public String[] solveFrom(String start){
for(Station st : stations.values()){
st.init();
}
stationList = new TreeSet<Station>(new DistanceComparator());
stationList.addAll(stations.values());
modifyDistance(stations.get(start),0);
while(!stationList.isEmpty()){
final Station station = stationList.pollFirst();
if(!stationList.isEmpty()){
final Station[] stationArray
= stationList.toArray(new Station[0]);
for(int i=0;i<stationArray.length;i++){ // Iterator使用不可
recalculate(stationArray[i],station);
}
}
}
return getResult();
}
private String[] getResult(){
final String[] result = new String[stations.size()];
int index=0;
for(Station s: stations.values()){
result[index++]=s.getResult();
}
return result;
}
}
class Rei {
public static void main(String[] arg){
final String[] stations ={"電機大","新御茶ノ水","大手町",
"神保町","お茶の水","神田",
"代々木","表参道","原宿","渋谷"};
final StationCollection collection
= new StationCollection(stations);
collection.setDistance("電機大","新御茶ノ水",5);
collection.setDistance("電機大","大手町",13);
collection.setDistance("電機大","神保町",15);
collection.setDistance("電機大","お茶の水",10);
collection.setDistance("電機大","神田",10);
collection.setDistance("新御茶ノ水","大手町",3);
collection.setDistance("大手町","表参道",12);
collection.setDistance("神保町","表参道",11);
collection.setDistance("お茶の水","神田",3);
collection.setDistance("お茶の水","代々木",13);
collection.setDistance("神田","渋谷",25);
collection.setDistance("表参道","原宿",3);
collection.setDistance("原宿","渋谷",2);
/*
System.out.println(collection);
/**/
System.out.println(Arrays.toString(collection.solveFrom("電機大")));
/**/
}
}
ここで、作成しているクラスは拠点を示す Station と、 Station に対する distance メンバーの大小による Comparator である DistanceComparator と Station を集めて最短距離を計算する StationCollection の 3 クラスを定義 しています。
Station は駅名を保存する他に、他の駅との距離を保存する setDistance と 取り出す getDistance(Station) があります。 getDistance で Station で距離を検索するために、HashMap を使用します。 そのために、 Station は Comparable を実装する必要があります。 基本的には駅名で比較できるように compareTo, equals, hashCode を実装し ておきます。
また最短経路を計算するために出発点からの距離を記憶する distance フィー ルドと最短距離で直前の拠点を覚えておく previous フィールドを定義してお きます。 distance に対しては、 init で大きな値(但し多少の距離を足しても符号が反転 しない程度)に初期化して、 getDistance() で値を返し、 modifyDistance(int x) で値を変更します。 previous に関しては init で null に初期化し、 setPrivious で Station を記憶します。 そして、 getPriviousList で再帰的に出発点から直前の拠点までを文字列と して取得します。 getResult で本拠点と経由点と距離を合わせた形式の文字列を生成します。
DistanceComparator は Station の distance フィールドによる大小関係を与 える Comparator です。 但し、同一距離の複数の拠点を扱えるように、 compare メソッドは同一距離 の場合は拠点名の比較結果を返しています。 さらに、 java.util.Comparator にあるように、 equals メソッドと一貫性を 持たせるために、 Station の equals では拠点名と distance が等しいとき だけ true になるようになっています。
拠点を登録し、最短距離を計算させるクラスです。 拠点名の配列をコンストラクタに与えると、それぞれ Station オブジェクト を生成し、拠点名で検索できるように HashMap で登録しておきます。 次に、 setDistance で二拠点間の距離を入力します。これは作成した HashMap を利用した Station の setDistance のラッパーになっています。 そして、 solveFrom(String) メソッドで入力した拠点名からの最短距離を求 めて行きます。
solveFrom メソッドでは、まず、各拠点を初期化します。 そして、距離で順序づけする stationList という TreeSet を定義し、全拠点 を登録します。 次に出発点の出発点からの距離を 0 に設定します。 そして、 stationList が空になるまで次を繰り替えします。 まず、出発点から最短の距離にある拠点を stationList から取り出します。 そして、stationList が空で無いとき、各拠点までの距離と、今取り出した最 短地点間経由の距離を比較して距離の再計算を行います。
これを行うために、再計算のメソッドと、距離の書き換えのメソッドを用意し ます。 再計算のメソッドでは、新しい距離を計算した後、元々の距離よりも短くなっ ていたら距離を書き換え、直前の経由地を設定します。 距離の書き換えメソッドでは、stationList のキーが距離なので単純に距離を 書き換えできません。 そのため、一旦 stationList から取り出した後、距離を書き換え、 stationList に登録します。 各拠点で距離を再計算する際に、このように stationList の要素を変更して しまうため、「各拠点」を Itarator で扱うことができません。 そのため、solveFrom メソッドでは一旦配列に変換して、添字によって各拠点 の処理を行っています。
この講義の主な目的は、以下のようなことを学ぶことでした。
プログラムの処理の一部に名前をつけ、その名前でその処理を行うようにする
ことができます。
関数は処理を行うのに必要な情報と、処理の結果の情報を規定し
て定義します。
定義した処理を行うには 関数名(必要な情報) と書くことで、
この処理を動かし、そして処理の結果得られた値を受け取ることができます。
int plus(int x, int y){
return x+y;
}
先頭の int は関数の最後で return で返される戻り値の型を表しています。 次に関数名が来て、丸カッコの中は仮引数の列が入ります。 そして、中カッコの中では仮引数を用いた処理が記述されます。 このように定義された関数を呼ぶには関数名の後の丸カッコの中に、実際に処 理させたい値(実引数)を与えます。 すると、関数が呼び出され、実引数を仮引数に当てはめて処理が行われ、最終 的に戻り値の型の値が返されます。
関数は、同じことを複数回繰り返すことに使えますが、単純に処理に名前を付 ける効果もあります。 さらに、関数の中で宣言した変数(ローカル変数)は関数の外側か らアクセスできないので、プログラムを部品として分割して作成することがで きます。
Java では、 main などの static メソッドから呼び出す関数を作るには private static 宣言して関数を定義します。
同じ目的であるプログラムは無限に存在します。したがって、作成したプログ ラムが正しいかどうかを調べるのに、特定のプログラムと一致するかどうかを 調べても意味がありません。 そこで、作成したプログラムが正しいかどうかを調べるには別の方法が必要で す。 本講義では容易な手法としてテストによる検証をとりあげました。 テストを行うには、入力と出力の正しい組み合わせを用意して、プログラムに 入力を与えた時、用意した出力と同じものが出力されるかを検証する必要があ ります。 但し、多くのプログラムは入力可能なパターンとして莫大な数がありますので、 実用的で完璧なテストは不可能です。 従って、どのような入出力パターンを用いるかは考える必要があります。 なお、近年のプログラム開発手法として、テスト駆動型と呼ばれる、プログラ ム開発に先だって自動テストプログラムを作ってからプログラムを作る手法が あります。 これらの手法は経験的に開発効率が良いことがわかっており、効率的な プログラミング手法であるXP(エクストリームプログラミング)やアジャイルコ ンピューティングでも採用されています。
一方、テストで誤りを発見した場合などで、その誤りを効率良く正していくこ とも考えなければなりません。 そのための手法として、プログラムを小さな部品ごとに分けて、各々をテスト する方法が考えられます。 各テストを完璧に行うことは不可能なので、部品ごとのテストが終った後も、 部品を組み合わせるごとにテストは必要ですが、誤りを見つけた時、誤りを探 す範囲を小さくできる利点があります。
Java 言語は C 言語をベースに作られたオブジェクト指向型言語なので、 C の文法を踏襲しています。 但しオブジェクト指向に関しては、同じ C 言語の拡張である C++ とは異なる。
| アクセス修飾子 | 効能 |
|---|---|
| private | 同一クラス内のみでアクセス可能 |
| なし | 同一パッケージ(同じフォルダ内)のみでアクセス可能 |
| protected | 同一パッケージ、派生クラスのみでアクセス可能 |
| public | どこからでもアクセス可能 |
オブジェクト指向ではひとつのクラスを拡張して別のクラスを作る場合、二つ の方法があります。 ひとつはコンポジションと呼ばれるものです。 これは、メンバ変数に利用したい他のクラスのインスタンスを生成して保持します。 そして、外部からのメソッドの呼び出しがあった場合は、内部で保持している インスタンスに対してメソッドを呼び出し、得られた値をそのまま返します。
もう一方は継承と呼ばれるものです。 利用したいクラスを指定してクラスを作成すると、コンストラクタを除く全て の機能がコピーされます。
以下はクラス A の f() というメソッドをクラス B がコンポジションをし、 クラス C が継承を行う例です。
class A {
public A(){}
public void f(){
System.out.println("実行されました");
}
}
class B {
final private A a;
public B(){
a = new A();
}
public void f(){
a.f();
}
}
class C extends A {
public C(){}
}
class Rei {
public static void main(String[] arg){
final A a = new A();
final B b = new B();
final C c = new C();
a.f();
b.f();
c.f();
}
}
ここで、継承されるクラス(A)を親クラスやスーパークラス、継承されたクラ ス(C)を子クラスやサブクラスと言います。
オブジェクト指向言語では、子クラスのオブジェクトを親クラスの変 数で参照できます。 そして、親クラスで定義されているメソッドを子クラスがオーバーライドして いれば、メソッド呼び出しでは、そのオーバーライドされているメソッドが呼 び出されます。 これをポリモーフィズムと呼びます。
class A {
public A(){}
public void f(){
System.out.println("A のメソッド");
}
}
class B extends A{
public B(){}
@Override
public void f(){
System.out.println("B のメソッド");
}
}
class Rei {
public static void main(String[] arg){
final A a = new B();
a.f(); // B のメソッドが呼ばれる
}
}
ポリモーフィズムを前提としたクラス設計では、親クラスは変数宣言のみ必要 で、オブジェクトを生成する必要が無い場合があります。 この場合、親クラスのオーバーライドされるメソッドは一度も呼び出されるこ とはありません。 そのため、実装せずにメソッドのシグネチャのみを定義するため、 abstract 宣言をすることができます。 但し、クラス内のメソッドを一つでも abstract 宣言した場合は、クラスを abstract 宣言し、オブジェクトを作成することは禁止されます。
abstract class A {
abstract public void f();
}
class B extends A{
public B(){}
@Override
public void f(){
System.out.println("B のメソッド");
}
}
class Rei {
public static void main(String[] arg){
final A a = new B();
a.f(); // B のメソッドが呼ばれる
}
}
なお、子クラスで全ての abstract メソッドを実装しないとコンパイルエラー になります。
Java は二つ以上のクラスを継承できません。 その代わり、インタフェイスと呼ばれる特別な抽象クラスはいくつでも継承で きます。 インタフェイスとはフィールドを持たず、全てのメソッドが public abstract である public クラスです。 上記のクラス A は次のように書き換えられます。
interface A {
void f();
}
class B implements A{
public B(){}
@Override
public void f(){
System.out.println("B のメソッド");
}
}
class Rei {
public static void main(String[] arg){
final A a = new B();
a.f(); // B のメソッドが呼ばれる
}
}
このように、クラス宣言が interface で始まり、 public abstract を省略で きることと、継承するには implements で指定するところは違いますが、他は 同じ構文です。
Java 言語の特性はオブジェクト指向というプログラミング手法を用いるため に作られています。 ここではオブジェクト指向プログラミングの手法をまとめます。
巨大なプログラムは長大なプログラムの記述によって作られているわけではあ りません。 プログラムは小さな単位の部品になっていて、その部品が複雑に組み合わさっ ています。
プログラムは初めから最適な設計に基づいて作られているわけではありません。 作成しながら、良い形に整えていくものです。 作成されたプログラムを整形するのをリファクタリングと言います。 リファクタリングではプログラムが動作可能な状態のまま形を変える必要があ ります。 このため、カプセル化が可能なオブジェクト指向言語は便利です。
リファクタリングの手法を一言で言うことはできませんが、基本はなるべく小 さなメソッドにプログラムを分割することです。 その他、変数の除去や、共通引数の抽出によるクラスの作成、メソッドの所有 権の移譲などがあります。
オブジェクト指向プログラミングが使われる理由は、人間が使う自然言語と対 応がつけやすいからです。 CRC カード分析では、名詞をオブジェクト、動詞をメソッドとしてクラス設計 をして、オブジェクトの操作を記述していきます。 このようにすると、自然言語で作成した仕様書とプログラムの対応が良くつき ます。
オブジェクト指向の研究は 1960 年代から始まっていますが、様々な定石が作 られてきました。 特に、講義で触れたものには、イテレータ、シングルトン、ストラテジ、テン プレートなどがありました。
デザインパターンは Wikipedia の解説がわかりやすいです。
オブジェクトの集まりのオブジェクトに対して、その内部のオブジェクトを順 番に指し示すものを独立してオブジェクトとして作成するもの。 Java ではさらに、イテレータを生成できるクラスを Iterable というインタ フェイスを実装すると、拡張 for 文を使用することができる。
イテレータは要素がまだあるか判定する hasNext() メソッドと要素を一個ず つ取り出す next() メソッドを実装しています。
Iterator i = collection.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
オブジェクトを一つだけ生成するファクトリを作るもの。 通常はコンストラクタの使用を禁じて、 static な getInstance() メソッド を実装します。
class A {
private A(){}
private static A instance = new A();
public static A getInstance(){
return instance;
}
}
あるメソッドを持つオブジェクトに対して、 setter で様々なオブジェクトを 与えることで、異なる動作をさせるものです。 setter の引数はインタフェイスであり、与えるオブジェクトはそのインタフェ イスを実装しています。
interface A {
void f();
}
class B {
public B(){}
private A a;
public void setA(A a){
this.a = a;
}
public void execute(){
a.f();
}
}
class Rei {
public static void main(String[] arg){
B b = new B();
b.setA(new A(){public void f(){System.out.println("1");}});
b.execute();
b.setA(new A(){public void f(){System.out.println("2");}});
b.execute();
}
}
文字列を生成する際に、親クラスで文字列の部品を抽象関数として定義し、抽 象関数を使った文字列生成メソッドを作成する。 子クラスで抽象関数を実装して、親クラスの文字列生成メソッドを呼び出すこ とで完成した文字列を生成する。
abstract class A {
abstract protected String getName();
@Override public String toString(){
return "I am "+getName();
}
}
class B extends A {
public B(){}
@Override
protected String getName(){
return "B";
}
}
class C extends A {
public C(){}
@Override
protected String getName(){
return "C";
}
}
class Rei {
public static void main(String[] arg){
System.out.println(new B());
System.out.println(new C());
}
}
プログラム開発において、与えられた問題を分解し、元の問題と同じ構造を発 見できれば、再帰という手法を用いてプログラムを書くことができます。
例えば、与えられたデータを整列する場合、整列された列はどの部分列を見て も整列されています。よってデータ列を半分にすれば、大きい列と小さい列に 分割できます。 従って、データ列を大きいものと小さいものとに半分に分割するような関数を 設計し、半分になった列それぞれに対して、同様な処理を繰り返すようにする と最終的にデータを整列できます(Quick Sort)。
このように、データの列に何らかの規則がありデータを分割しても成り立つ場 合、関数の中でデータを分割しながら同じ関数を呼び出すようにすると、シン プルなプログラムで複雑なデータを取り扱うことができます。 再帰は、このほか線形リストや順序木の処理などにも活用できます。
一つの問題を解くプログラムは無限に存在します。 そのため、どのようなプログラムを作成するかについては価値観が必要になり ます。 「良いプログラム」にはいろいろな観点が存在しますが、その中には処理が高 速なプログラムというものがあるはずです。 但し、コンピュータのプログラムの速度を評価する時、プログラム自身が持つ数学的 な性質ゆえ、特別な測り方をしなければなりません。 例えば、ある計算機で特定のデータを入力した時にかかった実時間は、そのプ ログラムの評価にはならないことが証明されています。 また、いわゆるベンチマークテストと呼ばれる、定めた入力データによる計算 時間を自動的に測定するプログラムを動作させるものがありますが、これもそ れだけプログラムの動作を速くする不正がしばしば行われていて、信頼できる 評価にはなりません。
プログラムの評価をする場合、与える入力の長さを n とした時、計算時間を n の関数で求める必要があります。 但しその際、最も増え方の速い項を定数倍は無視して求めます。 これを関数のオーダを求めると言いますが、この方法であれば実際に高速なプ ログラムであることを示すことができます。
データ構造を表す際に良く使われるのがグラフと呼ばれる、頂点と辺で作られ た構造です。 特に重要な構造は木構造です。 木構造は連結したループの無いグラフです。 そのため、部分グラフも木構造となるため、再帰処理が容易です。
Java では配列の他に java.util.ArrayList という配列と同じような性質を持 つクラスライブラリがあります。 さらに、データ数を上限を越えて書き込みできます。 添字を使用したデータの取り出しは一定時間で可能です。 但し、拡張する際は容量に比例した時間がかかります。
大量のデータを扱うのに、あらかじめ容量を決めなければいけない配列は使え ません。そこで使用したのが線形リストというデータ構造です。 これはメモリをあらかじめ確保するのではなく、必要に応じて必要な量だけメ モリを取得し、データを順に格納するものです。
Java では java.util.LinkedList は線形リストです。 これは大量のデータを取り扱う仕組みのうち、もっとも簡単な構造をし てます。従って、検索などはデータ量に比例した時間かかります。 一方で、データの追加や削除は容易にできます。 これは配列とは異なる特徴を持っています。
数の決まっているものを順序に従って整列させるには、配列のソートを行いま す。 しかし、数の決まってないものを整列させるには、順序木を使います。 順序木は、二分木において、頂点のデータが左の子よりも大きく、右の子より 小さいものを言います。 このような木に対して、データを格納する場合、根の頂点から順にデータを比 較していくとデータを格納すべき場所を捜し出すことができます。 一方、木の左から順にデータを取り出すことで、いつでも整列した状態でデー タを取り出すことができます。 Java 言語では java.util.TreeMap を使います。 しかし、大量のデータの入出力が発生する場合、効率良くデータをやりとりす るために、外部データベースの利用を考えた方が良い場合があります。
この講義の続編として「データ構造とアルゴリズムII」があります。 この講義で学んだ「グラフ」や「木構造」のアルゴリズムを活かして、 「作りたいプログラムを作る」にはどうすればよいかということに関して一般 的なテクニックを学びます。
前半はオートマトン理論、形式言語理論、コンパイラ論などに触れ、テキスト ファイルからデータを取り出し、定めたルールによって計算を行うようなプロ グラムを作成する術を学びます。 また、 GUI のデザインパターンも学び、電卓を作成することを目標としてい ます。
後半は XML に関して学びます。 XML は形式言語理論の成果を元に、プログラムで扱いやすいテキストベースの データ構造として設計されました。 そのため、 XML を扱うプログラムのインタフェースが定義されていますが、 通常は Java と Javascript 言語だけで規程されています。 そのため、 Java でどのように XML を扱うかを中心に、 XML 技術を紹介しま す。 DTD, XML Schema, SAX, DOM, XPath, XSLT を学びます。 特に、 XPath は、データベース問い合わせ言語と関連性があります。
本講義をより深く学ぶには、様々なアルゴリズム関係の本があります。 但し、通常アルゴリズムはプログラミング言語と無関係という立場をとります ので、 ALGOL や Pascal などの構造型言語で記述性より可読性を重視したプ ログラミング言語で書かれています。 本講義で取り上げたアルゴリズムは本当に少しだけです。 上級者が必ず知らなければならないテクニックとしては、動的計画法や分割統 治法などがあります。 これらをキーワードに教科書を選んで下さい。
なお、アルゴリズムに関する本の中には NP 完全問題に関して詳しい本もあり ます。 これは組み合わせ最適化問題に関するアルゴリズムの研究が書かれています。 しかし、NP 完全問題には効率の良いアルゴリズムは見つかっていませんので、 直接プログラミング技術の習得にはつながりません。 但し、効率の見極めや、アルゴリズムの抽象的な考え方や限界など、アルゴリ ズムに対するより深い理解ができるようになります。 大学院科目の「アルゴリズム論」ではこれらのことについて論じます。
Java 言語をより深く学ぶには「Effective Java」が良いでしょう。 これは少々難しいですが Java の中級者には必読です。 Java のリファレンスマニュアルからも参照される、重要な書籍です。
オブジェクト指向に関しては、分析法、プログラミングの定石としてのデザイ ンパターンやアンチパターン、ソフトウェア管理法としてリファクタリングの 手法など 様々な切り口があります。 リファクタリングに関しては マーチン ファウラー著、児玉公信、友野晶夫、平澤章、梅澤真史訳 「リファクタリング プログラミングの体質改善テクニック」ピアソン・エ デュケーション(2000) は Java でどのようにプログラムを管理していくかのテクニックがよくわかり ます。