このドキュメントは 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 | 3 |
| 代々木 | ∞ | ∞ | ∞ | ∞ | 13 | ∞ | ∞ | - | 3 | ∞ |
| 原宿 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 3 | 3 | - | 2 |
| 渋谷 | ∞ | ∞ | ∞ | ∞ | ∞ | 25 | 3 | ∞ | 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[] 変数には、電機大から来る場合に直前に経由した駅を入れます。 そうすると、最短路が見つかった場合、目的地から順に電機大まで最短経路をた どることができます。
この講義の主な目的は、以下のようなことを学ぶことでした。
プログラムの処理の一部に名前をつけ、その名前でその処理を行うようにする
ことができます。
関数は処理を行うのに必要な情報と、処理の結果の情報を規定し
て定義します。
定義した処理を行うには 関数名(必要な情報) と書くことで、
この処理を動かし、そして処理の結果得られた値を受け取ることができます。
int plus(int x, int y){
return x+y;
}
先頭の int は関数の最後で return で返される戻り値の型を表しています。 次に関数名が来て、丸カッコの中は仮引数の列が入ります。 そして、中カッコの中では仮引数を用いた処理が記述されます。 このように定義された関数を呼ぶには関数名の後の丸カッコの中に、実際に処 理させたい値(実引数)を与えます。 すると、関数が呼び出され、実引数を仮引数に当てはめて処理が行われ、最終 的に戻り値の型の値が返されます。
関数は、同じことを複数回繰り返すことに使えますが、単純に処理に名前を付 ける効果もあります。 さらに、関数の中で宣言した変数(ローカル変数)は関数の外側か らアクセスできないので、プログラムを部品として分割して作成することがで きます。
Java では、 main などの static メソッドから呼び出す関数を作るには private static 宣言して関数を定義します。
Java 言語は C 言語をベースに作られたオブジェクト指向型言語なので、 C の文法を踏襲しています。 但しオブジェクト指向に関しては、同じ C 言語の拡張である C++ とは異なる。
| アクセス修飾子 | 効能 |
|---|---|
| private | 同一クラス内のみでアクセス可能 |
| protected | 同一クラス、派生クラスのみでアクセス可能 |
| なし | 同一パッケージ(同じフォルダ内)のみでアクセス可能 |
| public | どこからでもアクセス可能 |
オブジェクト指向ではひとつのクラスを拡張して別のクラスを作る場合、二つ の方法があります。 ひとつはコンポジションと呼ばれるものです。 これは、メンバ変数に利用したい他のクラスのインスタンスを生成して保持します。 そして、外部からのメソッドの呼び出しがあった場合は、内部で保持している インスタンスに対してメソッドを呼び出し、得られた値をそのまま返します。
もう一方は継承と呼ばれるものです。 利用したいクラスを指定してクラスを作成すると、コンストラクタを除く全て の機能がコピーされます。
同じ目的であるプログラムは無限に存在します。したがって、作成したプログ ラムが正しいかどうかを調べるのに、特定のプログラムと一致するかどうかを 調べても意味がありません (従って、プログラムを作成する演習で答を提示しませんでした) 。 そこで、作成したプログラムが正しいかどうかを調べるには別の方法が必要で す。 本講義では容易な手法としてテストによる検証をとりあげました。 テストを行うには、入力と出力の正しい組み合わせを用意して、プログラムに 入力を与えた時、用意した出力と同じものが出力されるかを検証する必要があ ります。 但し、多くのプログラムは入力可能なパターンとして莫大な数がありますので、 実用的で完璧なテストは不可能です。 従って、どのような入出力パターンを用いるかは考える必要があります。 なお、近年のプログラム開発手法として、テスト駆動型と呼ばれる、プログラ ム開発に先だって自動テストプログラムを作ってからプログラムを作る手法が あります。 これらの手法は経験的に開発効率が良いことがわかっており、効率的な プログラミング手法であるXP(エクストリームプログラミング)やアジャイルコ ンピューティングでも採用されています。
一方、テストで誤りを発見した場合などで、その誤りを効率良く正していくこ とも考えなければなりません。 そのための手法として、プログラムを小さな部品ごとに分けて、各々をテスト する方法が考えられます。 各テストを完璧に行うことは不可能なので、部品ごとのテストが終った後も、 部品を組み合わせるごとにテストは必要ですが、誤りを見つけた時、誤りを探 す範囲を小さくできる利点があります。
プログラム開発において、与えられた問題を分解し、元の問題と同じ構造を発 見できれば、再帰という手法を用いてプログラムを書くことができます。
例えば、与えられたデータを整列する場合、整列された列はどの部分列を見て も整列されています。よってデータ列を半分にすれば、大きい列と小さい列に 分割できます。 従って、データ列を大きいものと小さいものとに半分に分割するような関数を 設計し、半分になった列それぞれに対して、同様な処理を繰り返すようにする と最終的にデータを整列できます(Quick Sort)。
このように、データの列に何らかの規則がありデータを分割しても成り立つ場 合、関数の中でデータを分割しながら同じ関数を呼び出すようにすると、シン プルなプログラムで複雑なデータを取り扱うことができます。 再帰は、このほか線形リストや順序木の処理などにも活用できます。
一つの問題を解くプログラムは無限に存在します。 そのため、どのようなプログラムを作成するかについては価値観が必要になり ます。 「良いプログラム」にはいろいろな観点が存在しますが、その中には処理が高 速なプログラムというものがあるはずです。 但し、コンピュータのプログラムの速度を評価する時、プログラム自身が持つ数学的 な性質ゆえ、特別な測り方をしなければなりません。 例えば、ある計算機で特定のデータを入力した時にかかった実時間は、そのプ ログラムの評価にはならないことが証明されています。 また、いわゆるベンチマークテストと呼ばれる、定めた入力データによる計算 時間を自動的に測定するプログラムを動作させるものがありますが、これもそ れだけプログラムの動作を速くする不正がしばしば行われていて、信頼できる 評価にはなりません。
プログラムの評価をする場合、与える入力の長さを n とした時、計算時間を n の関数で求める必要があります。 但しその際、最も増え方の速い項を定数倍は無視して求めます。 これを関数のオーダを求めると言いますが、この方法であれば実際に高速なプ ログラムであることを示すことができます。
大量のデータを扱うのに、あらかじめ容量を決めなければいけない配列は使え ません。そこで使用したのが線形リストというデータ構造です。 これはメモリをあらかじめ確保するのではなく、必要に応じて必要な量だけメ モリを取得し、データを順に格納するものです。
C 言語で実現するには次のような、データとポインタを格納するような構造体 を作り、 malloc 関数でメモリ上に生成してはひとつひとつつなげて使いまし た。
struct node {
struct node *next;
int data;
};
線形リストは大量のデータを取り扱う仕組みのうち、もっとも簡単な構造をし てます。従って、検索などはデータ量に比例した時間かかります。 一方で、データの追加や削除は容易にできます。 これは配列とは異なる特徴を持っています。
なお、C++ では STL(Standard Template Library)に deque や list というテ ンプレートが存在し、また、 Java では java.util.ArrayList が存在します。 どちらも C 言語のようにポインタの操作やメモリの操作無しに、頂点を付け 加えたり削除したりできます。
数の決まっているものを順序に従って整列させるには、配列のソートを行いま す。 しかし、数の決まってないものを整列させるには、順序木を使います。 順序木は、二分木において、頂点のデータが左の子よりも大きく、右の子より 小さいものを言います。 このような木に対して、データを格納する場合、根の頂点から順にデータを比 較していくとデータを格納すべき場所を捜し出すことができます。 一方、木の左から順にデータを取り出すことで、いつでも整列した状態でデー タを取り出すことができます。 C 言語ではこの順序木を使うのに、自らの構造を指すことができるポインタを 二つ持つ構造体を使用しました。
struct node {
int data;
struct node *left,*right;
};
なお、値の整列は情報処理の基礎であり、多くのプログラミング言語で簡単に 利用できるようになっています(但し、内部では順序木を利用している)。 C++ では STL にある map や multimap で利用 できます。 また、Java 言語では java.util.TreeMap を使います。 しかし、大量のデータの入出力が発生する場合、効率良くデータをやりとりす るために、外部データベースの利用を考えた方が良い場合があります。