探索アルゴリズム
多数のデータの集合から，与えられた条件に該当するデータを発見する手順を探索アルゴリズムと呼ぶ．
この探索アルゴリズムをプログラムとして実現する際，実現がどの程度容易であるか，或いは，
実行速度は速いかといった特性は，データ保持の仕方で大きく左右される．
ここでは，やや大規模なデータセットを対象として，幾つかの探索アルゴリズムを実現するプログラムを作成し，
その性能特性の評価を行う．
/NF/class0/oomoto/applied/postal 以下に郵便番号表のデータが用意してある．
postal_10.dat 10件分
postal_1000.dat 1000件分
postal_full.dat 121470件分
このデータの形式は，
郵便番号 (tab文字) ヨミガナ (tab文字) 住所漢字文字列 （改行文字）
という形式となっている．
これらのデータは予め郵便番号順に並んでいるとは限らない．また，同じ郵便番号で異なる住所が
複数存在する（例えば 6040805, 6040092など）．
尚，かなりデータサイズが大きいので，自分のホームディレクトリ以下にコピーしない方が良い．
作成するプログラムでは，これらのデータを読み込んだ後，キーボードから検索したい郵便番号を
検索キーとして入力すると，検索された住所を画面表示，或いは，データの追加・削除が出来るものとする．
実行例：
データ読み込みを開始します........完了
読み込み処理時間(秒): 38.230034
********************************
処理を選択してください． 1) 追加 2) 削除 3) 検索 >> 1
追加する郵便番号：0010100
追加する住所：Hokkai-Dokoka
削除を開始します........完了
追加処理所要時間(秒): 0.000001
********************************
処理を選択してください． 1) 追加 2) 削除 3) 検索 >> 3
検索したい郵便番号: 6028454
検索を開始します........完了
見つかった住所: 京都府京都市上京区今出川町
検索所要時間(秒): 14.529800
********************************
処理を選択してください． 1) 追加 2) 削除 3) 検索 >> ^C
このようなプログラムを以下に示す幾つかのアルゴリズムを用いて実現し，
実際に実行した処理所要時間について，データ件数との関連を分析評価せよ．
ヘルプその１： プログラム中の処理時間を測定する例は /NF/class0/oomoto/applied/algorithm/StopWatch.java を参照のこと．
ヘルプその２： テキストファイルからデータを読み取る例は /NF/class0/oomoto/applied/algorithm/FileRead.java を参照のこと．
尚，作成するプログラムは以下の条件を満たすように作成せよ．
一つの郵便番号と対応する住所（複数の住所が存在する場合が有り得る）の組み合わせは，クラスPostalEntryで表現される．
PostalEntryクラスの仕様：
privateインスタンス整数変数zipを持つ．
privateインスタンス変数addrsを持つ．変数型はString配列とする．
privateインスタンス変数nextを持つ．変数型はPostalEntry型とする．
インスタンス変数zipの値を返すpublicメソッドgetZip()を持つ．
addrsのString要素を一つ追加するpublicメソッドaddAddr(String)を持つ．
インスタンス変数addrsの値を返すpublicメソッドgetAddrs()を持つ．
インスタンス変数nextの値をセットするpublicメソッドsetNext(PostalEntry)を持つ．
インスタンス変数nextの値を返すpublicメソッドgetNext()を持つ．
コンストラクタは引数を２つとる．最初は郵便番号の整数，二つ目は住所のStringとする．
ここで作成する郵便番号表を実現する様々なクラスは，全てインターフェイスPostalTblを実装(implement)するように作成する．
PostalTblは次のようなpublicメソッドを有すると定義されている．
・新しい郵便番号と住所の組を追加するメソッドadd(int, String)を持つ．
・与えた郵便番号に該当するのエントリを削除するremove(int)を持つ．
・与えた郵便番号に該当する住所の文字列（配列）を返すString[] search(int)を持つ．尚，該当が無い場合は要素数０の空配列が返るものとする．
・全てのエントリを削除するvoid reset()を持つ．
尚，PostalEntryクラスの雛型とコンパイル済みインターフェイスPostalTbl.classを
/NF/class0/oomoto/applied/algorithm/PostalEntry.java
/NF/class0/oomoto/applied/algorithm/PostalTbl.class
として置いているので，ソースコードは参考として利用して良い．
インターフェイスPostalTbl.classは各自の作業ディレクトリにコピーして用いよ．
探索アルゴリズムその１．線形探索
線形探索(Linear Search)とは，探すべきデータを一列に並べておき，端から順に探すアルゴリズムである．
但し，データの並びは整列されてない．
課題algo-1：
以下のようなクラスArrayTbl.javaと動作テスト用クラスPostalTest.javaを作成せよ．
ArrayTblクラスの仕様：
・PostalTblインターフェイスを実装すること．
・郵便番号表のデータは，PostalEntryの配列として保持する．
・データ探索アルゴリズムは線形探索とする．
・インスタンス変数は全てprivateとする．
・インターフェイスに宣言されたadd, remove, search, reset以外のインスタンスメソッドは全てprivateとする．
・main()メソッドには，このクラスが正常に動作することを確認するテスト用クラスPostalTestが持つテスト用クラスメソッド呼び出しを書く．
引数には読み込む郵便番号表データのファイル名を与えるものとする．例えば，次のようになるだろう．
public static void main(String[] args) {
if (args.length == 0)
return 0;
PostalTbl tbl = new ArrayTbl(); // 準備
String filename = args[0]
PostalTest.doTest(tbl, filename);
return 0;
}
また，PostalTestクラスはクラスメソッドdoTestのみを持ち，概略は次のようになる．
public class PostalTest {
public static void doTest(PostalTbl tbl, String fName) {
// ファイルの読み込み
System.out.print("データ読み込みを開始します.....")
try {
// 読み込み処理
System.out.println("完了")
BufferedReader bin = new BufferedReader(
new InputStreamReader(System.in));
while (true) {
System.out.println("*******************************");
System.out.print("処理を選択してください: ");
String inputString = bin.readLine();
// 検索処理．．．．．．
// 結果の表示
} // End of while loop
}
catch (IOException ioe) {
System.out.println("IO Error!");
return 1
}
return 0; // Never reached.
} // End of doTest
}
作成したプログラムを各データファイルを読み込ませて実行し，各処理の所要時間を計測せよ．
・データの読み込み開始から読み込み完了まで（初期化所要時間）
・先頭行の郵便番号（例えば，postal_10.datであれば 6030000 ）の検索
・先頭から25%位置の行（例えば，postal_10.datであれば，３行目 6038002 ）
・データファイルの中央行の郵便番号の検索
postal_10の場合：5行目
postal_1000.datの場合：500行目
postal_full.datの場合：60735行目
・先頭から75%位置の行（例えば，postal_10.datであれば，８行目 6038007 ）
・最終行の郵便番号（例えば，postal_10.datであれば 6038011 ）の検索
尚，計測された時間について，読み込むデータ総数の変化や検索キーの位置（先頭，中央，末尾）が
変化すると，どのように変わるか考察せよ．
このアルゴリズムは多数のデータから目的の条件を満たすものを探し出す処理に向いていると言えるか？
（注）： データファイル中の例えば500行目を知りたい場合は，headコマンドとtailコマンドを用いて，
cat postal_1000.dat | head -500 | tail -1
というコマンド・パイプラインを用いれば，その該当行を抽出出来る．
また，ファイルの行数をカウントするには，
cat postal_full.dat | wc -l
などとすれば分かる．
課題jalgo-2:
ArrayTblとは違い，郵便番号表をPostalEntryのリスト構造を用いて表現し，各データを線形探索できるクラスListTbl.javaを作成せよ．
リスト構造については，教科書「やさしいJavaプログラミング」Lesson 8を参考にすること．
ListTblクラスの仕様：
・PostalTblインターフェイスを実装すること．
・郵便番号表のデータは，PostalEntryをノードとするリスト構造として保持する．
・データ探索アルゴリズムは線形探索アルゴリズムとする．
・インスタンス変数は全てprivateとする．
・インターフェイスに宣言されたadd, remove, search, reset以外のインスタンスメソッドは全てprivateとする．
・main()メソッドには，このクラスが正常に動作することを確認するためのテスト用クラスPostalTestに定義されたテスト用クラスメソッドの呼び出しを書く．
mainメソッド引数には読み込む郵便番号表データのファイル名を与えるものとする．PostalTestクラスは課題algo1と全く同じものを用いる．
処理時間について java-algo-1と同様に計測して考察せよ．
特に，リスト構造を用いて表現した場合において，配列を用いたと比較して，処理速度（性能）において不利な点・有利な点について考えてみよ．
特にデータの追加や削除の処理コストに注目せよ．
探索アルゴリズムその２．二分探索
二分探索(Binary Search)とは，探索対象データをキー値に関して整列した状態となるように配列上に配置しておき，
範囲を絞り込みながら検索するアルゴリズムである．
その概略は次の通り．
１．検索対象のデータは，配列array[]に整列しており，検索キーは変数keyに入っている．
２．変数loで配列の先頭を示し，変数hiで配列の末尾を示す．
３．lo <= hiならば繰り返し続行、そうでないならば，８へ
４．loとhiの中間点 mid を計算する．
５．key <= array[mid] なら hi = mid-1; とする。
６．key >= array[mid] なら lo = mid+1; とする。
７．３へ戻って繰り返し続行
８．lo == hi+2ならばデータ発見でありデータの位置はlo-1，さもなくば，keyに一致するデータは存在しない．
尚，データの追加や削除に対しては，配列要素を移動させることで，常に，
・配列中でデータはキー値の大きさ順番に並んでいる．
・配列中にデータが入っていない抜けは無い．
状態を維持しなければならないことに注意すること．
課題algo-3:
郵便番号表検索を二分探索アルゴリズムで実現するクラスBinaryTbl配列を用いて作成せよ．
処理時間について先の課題と同様に計測して，線形探索を用いている場合と比較しながら考察せよ．
考察事項：
・次のようなデータを追加・検索・削除する所要時間をそれぞれ計測してみよ．
追加： 0010100 Hokkai-Dokoka
検索： 0010100
追加： 9998500 Yamagata-Chimei
検索： 0010100
削除： 0010100
削除： 9998500
・二分探索法を線形探索法と比較すると，データの検索・削除・追加の各場合において，どの程度に不利，或いは，有利と考えることが出来るか？
探索アルゴリズムその３．ハッシュ法
ハッシュ法（ハッシュ表, Hash Table）とは，検索対象のキー値を予め配列に入れておいて，高速にデータ探索を
行うアルゴリズムである．
ここで，配列の添え字（ハッシュ値）を i，データのキー値を vとすると，ハッシュ関数 fは次の性質を満たすとする．
i = f (v)
キー値が整数値の場合，ハッシュ関数として用いられるのは，vを適当な整数mで割った剰余をハッシュ値とするものである．
このmのことをハッシュ表サイズと呼ぶ．
また，配列へのデータ格納方法として最も単純な方法は，配列要素をデータへのポインタ（参照）とするもの（チェイン法）である．
配列要素に複数のデータを格納するには，各データをリスト構造で保持する．
以下に m = 10 とした場合の例を示す．
課題algo-4:
チェイン法によるハッシュ表を用いて郵便番号表を実現するHashTblクラスを作成せよ．
そのクラスが満たすべき条件は，上記の課題と同様とし，テスト用クラスも全く同じものを用いる．
考察事項その１：
ハッシュ表サイズ（配列要素数）m を変化させて，それぞれの場合に以下に示すデータ検索を行ってみて，処理時間の変化を考察せよ．
ハッシュ表サイズ：
100
1000
10000
100000
1000000
検索するデータ：
先頭行の郵便番号
先頭から25%位置の郵便番号
データファイルの中央行の郵便番号の検索
先頭から75%位置の郵便番号
最終行の郵便番号
考察事項その２：
・ハッシュ表サイズは，大き過ぎる，或いは，少な過ぎる場合は，望ましくない何故か？ また，どの程度に設定するのがするのが望ましいか？
・多数のデータ追加が起きた場合にハッシュ表サイズ適当でなくなった場合，その状況を解消するにはどうすればよいか？
課題提出その１：
各課題毎にプログラムの実行に必要な全てのソースコード全て，及び，実行結果をレポートシステムを用いて提出せよ．但し，添付書類形式では
受け取っても採点しないから注意のこと．
ソースコードの先頭部分には，「コメント」として氏名と学生番号を明記し，実行結果はソースコードの
末尾に「Javaプログラムのコメント行」として付けておくこと．
尚，提出するレポートは，念のため，正しくJava言語ソースコードとしてコンパイル・実行出来ることを
確認してから提出すること．
受け取ったソースコードは，Linuxシステム上で採点作業用シェルスクリプトを用いて半自動的にコンパイル・実行して
内容を確認するので，正しくコンパイル出来ないものが送られて来た場合は，「未完成」として採点される危険性がある．
レポート名の一覧：
課題algo-1 oomoto/applied/algorithm/algo1
課題algo-2 oomoto/applied/algorithm/algo2
課題algo-3 oomoto/applied/algorithm/algo3
課題algo-4 oomoto/applied/algorithm/algo4
締め切り： 5/9（土）
提出レポートの例：
/* 課題algo-1
ファイル名: ArrayTbl.java */
123456 産大太郎 */
import java.io.*;
.......
（中略）
.......
} /* ソースコードの終わり */
/* 実行結果ここから
データ読み込みを開始します．
読み込み処理時間(秒): 38.230034
......
（中略）
......
実行結果 終わり */
課題提出その２：
以下について，「紙のレポートとして」提出せよ．
・各課題を実現するクラスは，全てインターフェイスPostalTblをimplementするクラスとして作成した．このやり方による利点は何か？
PostalTblインターフェイスを使わないとした場合に発生するテスト用クラスPostalTestが受ける影響を考慮して考察せよ．
・algo-1からalgo-4までについて，各種の実行結果について考察せよ．
レポートはA4用紙とし，（本学指定のレポート表紙ではない）しかるべき体裁の表紙を付けておくこと．
特に実行時間の比較はグラフ化して分かり易く示すこと．
尚，当然ながら，機種が異なると実行時間は違ってくるから，「10号館PC」と「図書館のPC」の比較とか，
「10号館PC」と「自宅PC」の比較を行っても無意味である．同じ性能のPC上で実行した結果同士を比較せよ．
締め切り： 5/11（月）講義開始時に大本に提出のこと．〆切厳守！