ejdic2k.txtの内容は次のようなものです。2002件あります。
ejdic2k.txtのリンクを右クリックして出てくるメニューから「名前をつけてリンク先を保存」を選ぶことで、javaプログラムを入れるフォルダにダウンロードしておきましょう。
英単語と意味の間はタブで区切ってあります。
a 一つの,ある ability 能力 able できる,有能な about について,およそ,around above の上方へ,の上に,前に abroad 海外へ(で),外国に(で),広く,広まって absence るす,欠席,ないこと absent 欠席した,放心した absolute まったくの,絶対的な力を持った accept 受け取る,認める,引き受ける accident 偶然,事故 .....................省略.........
まず逐次探索にします。Jiten02.java に対して変わるところをこの色で示しましたが、削除される部分は書いてありません。
String[] word = { "blue", "green",....という部分をファイルからデータを読むように変更しているのが大きなところです。この部分はその気になればたくさん学ぶことがありますが、「String[] word = { "blue", "green",」と同様に word[] と imi[] を用意しているのだと大まかに理解することが最低限必要です。
import javax.swing.*;
import java.io.*;
public class Jiten04 {
public static void main( String[] args ) {
String fname = "ejdic2k.txt";
String[] word = new String[2010];
String[] imi = new String[2010];
int ct = 0;
try {
FileReader in = new FileReader(fname);
BufferedReader inb = new BufferedReader(in);
String line;
while ((line = inb.readLine()) != null) {
System.out.println(line);
String[] ndata = line.split("\t");
word[ct]=ndata[0];
imi[ct]=ndata[1];
ct++;
}
System.out.println("以上 0〜" + (ct-1) + " の " + ct + " 行");
inb.close();
in.close();
}
catch (IOException e) {
System.err.println( fname + " がないのでは？" );
System.err.println( e);
}
String s;
s = JOptionPane.showInputDialog("検索する英単語を入れてください？");
boolean atta=false;
for ( int i=0 ; ct>i ; i++ ){
System.out.println( i+" : "+word[i] );
if ( word[i].equals(s) ){
System.out.println( word[i]+" : "+imi[i] );
atta=true;
break;
}
}//forの終わり
if ( atta==false ) System.out.println( "見つかりません" );
}//mainの終わり
}//classの終わり
読み込みの途中にある System.out.println(line); は、正しく読み込んでいることを確かめるために、読み込んだ内容を報告している部分です。
探索部分に加えた System.out.println( i+" : "+word[i] ); は探している途中でいま何を調べているかを報告させるようにしたものです。
ファイルの中の単語数が少し増えてもいいように、配列を多めにしているので、読み込みの時に単語数を数えて ct に記憶しておきます。繰り返しの数は word.length() ではなく、この ct を使っています。
コンパイルと実行は次のようにします。
$ javac Jiten04.java $ java Jiten04 ....(読んだデータを表示しますが長いので最初の部分は省略)......... yes はい yesterday きのう,きのうは yet まだ,もう,それにもかかわらず yield 産出する,明け渡す,作物がてきてる,屈する you あなた[がた]は(を) young 若い,年下のほうの youth 若さ,青年時代,青年 zero 0,零,零度 以上 0〜2002 の 2003 行 (ここでダイアログがでます。yetと入力したとすると) 0 : a 1 : ability 2 : able ....(と頭から順番に探していきますが、長いので省略)......... 1990 : wrong 1991 : yard 1992 : year 1993 : yellow 1994 : yes 1995 : yesterday 1996 : yet yet : まだ,もう,それにもかかわらず $
yet という単語は1996番目に登録されているので、逐次探索では1996回比較して見つけることになります。a という単語ならば 1番目に登録されているので、1回の比較で見つかります。
二分探索を使うように書き換えます。前半(ファイルからの読み込み部分)は Jiten04.java とほとんど同じです。
正しく読み込めることはJiten04.javaでわかったので、ファイルからの読み込みの時に内容を報告しないようにします。
後半(探索部分)は Jiten03.java とほとんど同じです。
import javax.swing.*;
import java.io.*;
public class Jiten05 {
public static void main( String[] args ) {
String fname = "ejdic2k.txt";
String[] word = new String[2010];
String[] imi = new String[2010];
int ct = 0;
try {
FileReader in = new FileReader(fname);
BufferedReader inb = new BufferedReader(in);
String line;
while ((line = inb.readLine()) != null) {
//System.out.println(line);
String[] ndata = line.split("\t");
word[ct]=ndata[0];
imi[ct]=ndata[1];
ct++;
}
System.out.println("以上 0〜" + (ct-1) + " の " + ct + " 行");
inb.close();
in.close();
}
catch (IOException e) {
System.err.println( fname + " がないのでは？" );
System.err.println( e);
}
String s;
s = JOptionPane.showInputDialog("検索する英単語を入れてください？");
boolean atta=false;
int i,j,m;
i = 0;
j = ct-1;
while ( j >= i ){
m = (i+j)/2;
String format = "i=%4d | j=%4d | m=%4d | word[m]=%-10s\n";
System.out.printf(format,i,j,m,word[m]);
if ( word[m].equals(s) ){
System.out.println( "発見 word["+m+"] です。");
System.out.println( word[m]+" の意味は「"+imi[m]+"」です。" );
atta=true;
break;
}
else if (word[m].compareTo(s)>0) {
j=m-1;
}
else {
i=m+1;
}
}//whileの終わり
if ( atta==false ) System.out.println( "見つかりません" );
}//mainの終わり
}//classの終わり
コンパイルと実行は次のようにします。
$ javac Jiten05.java $ java Jiten05 以上 0〜2001 の 2002 行 (ここでダイアログがでます。yetと入力したとすると) i= 0 | j=2001 | m=1000 | word[m]=lodge i=1001 | j=2001 | m=1501 | word[m]=scatter i=1502 | j=2001 | m=1751 | word[m]=tap i=1752 | j=2001 | m=1876 | word[m]=use i=1877 | j=2001 | m=1939 | word[m]=whenever i=1940 | j=2001 | m=1970 | word[m]=within i=1971 | j=2001 | m=1986 | word[m]=wrap i=1987 | j=2001 | m=1994 | word[m]=yes i=1995 | j=2001 | m=1998 | word[m]=you i=1995 | j=1997 | m=1996 | word[m]=yet 発見 word[1996] です。 yet の意味は「まだ,もう,それにもかかわらず」です。 $
whileで繰り返されるたびに1行出力されますから11回の比較で見つかったことになります。
比較回数は最大で全体数を2で割りつづけて、1になる程度と言えます。ちょうど1/2のところにあったという幸運がであればもっと少なくなります。2000ならば大体 1000,500,250,125,64,32,16,8,4,2,1 ですから11回程度で見つかります。
二分探索をするには単語が文字コード順に並んでいる必要があります。
約2000件のデータから探索する場合、逐次探索は平均で1000回程度、二分探索では11回程度の比較で見つけられることがわかりました。
ただし、逐次探索の比較は等しいかどうかだけですが、二分探索の比較はどちらが大きいか(ABC順で先か後か)も調べているので単純に回数だけで比べるわけには行きません。
| データ数 | 逐次探索 | 二分探索 |
|---|---|---|
| 2000 | 1000 | 11 |
| 20000 | 10000 | 14 |
| 200000 | 100000 | 18 |
| n | O(n) | O(log2 n) |
1000と11と横に比べるだけでなく、データの数が多くなったときにどのように比較回数が増えるかが重要です。データ数(ここでは単語数)が2000⇨20000⇨200000と10倍になっていくとき、逐次探索は比較回数も同様に10倍ずつ増えていきます。二分探索は2倍にもなりません。データ数が多くなるほど逐次と二分の手間の差はますます広がります。
これだけから考えると、二分探索が優れているようですが、ちょっと待ってください。二分探索はデータが大きさの順に並んでいる必要があります。並んでいない場合は並べかえる手間も考慮に入れる必要があります。
また、複数のデータが合致する場合には二分探索では対処が難しくなります。