最終更新日
最終更新日 |
|
|
1 まえがき 2 ロゴライターのプログラム例 3 Javaのクィックソート例
4 Sentenceクラス(ArrayListの結合) 5 乱数発生、数値比較のソート 6 リスト処理のパッケージ化
7 オーバーライド 8 大量データのクィックソート 9 ファイル書き込みと処理時間
リスト処理を得意とする、Lispという言語があり、その上に作られたといわれるLogoの再帰用法(Recursion)を駆使したプログラム例があった。クィックソート である。この簡潔だが、難しい問題をJavaで書き換えた報告である。とりあげた題材は、とても基礎レベルのものではないだろうが、難航の連続の中でつかんだものは、結局、オブジェクトの指向の基本、Java言語の基礎を忠実にまもることにつきるので、あえて「Java基礎3」とした。特に難航して、ほとんどあきらめかけた頃にようやくできたのは、3章と6章、7章であった。いずれも、どこか、理解が中途半端だったことう痛感している。
Javaの基礎やフラクタル、数学基礎などのページを作成したのは、2003年8月。2003/8、「Javaの基礎」 の6、7章3節のように、ArrayListを少しやって、Javaでも再帰による繰り返しが使えること、ArrayListクラスはリスト処理そのものらしいことは分かった。が、その程度では、このクィックソートの書き換えはまるで歯がたたなかった。
2004/9、「Javaの基礎2」 を作成、「Javaの基礎」にも、7章1,2節を追加して、オブジェクト指向の考え方、概念をある程度把握できたし、ArrayListの扱い方にかなり慣れた段階で再挑戦した。難解なアルゴリズムではあるし、やはりそうとう苦労したが、曲がりなりにもこの難問をクリアできた。これが3章。
その中で、特に、苦労したのは、3章のコメントにも書いたが、たとえば、ArrayList alから最初の要素を除く al.remove(0)というメソッドの考え方だった。ロゴでいうと、BFというコマンドだが、戻り値はリストなのに対し、al.remove()の戻り値はboolean。一体、最初の要素を除いたArrayListはどこにあるのかということだった。al.remove(0)の処理を終えたa1そのもの なのだが、分かってみればなんでもない、こんなところも大きなネックになった。ArrayListの扱いに少し慣れていたとはとてもいえない状態であった。本の例題にもあるし、私自身の「Javaの基礎」「Javaの基礎2」のソースリストにも、類似事例は少なからずあったといのに!!
クィックソートの考え方を説明するのに、簡潔なロゴのプログラムから始め(2章)、その対比をコメントの形で追記しつつ、Javaによる書き換えを紹介(3章)、処理過程で、ArrayList同士やStringオブジェクトとの結合をArrayListで戻すようなメソッドが必要ということで作ったSentenceクラス(4章)と続く。4章では、型変換が必要だった。Object型をArrayListとかString型に変換する のである。その意味がほんとうに分かったとはいいにくいが、他に方法がありそうもなく、試しにやってみたらあっさり解決した。
5章では、コマンドライン引数という形で少数のデータについて、文字型比較でトライしてきたが、1000件とかかなりの量のデータを乱数で発生させ、数値比較でもやってみた。4章でできた型変換によるObject型からString型ヘの変換は失敗。toString()を使って解決した。Object型とはいえ、もとがString型なのか、5章のようにInteger型なのかで、違うらしい。
6章は、ここで作ったSentenceクラスや「Javaの基礎」でやったFput,Insertなどを独立のクラスらしく修正したうえで、Listパッケージ としてまとめてみた。Bfも追加して、Logoの持つリスト処理の関数をいくつか作ってみた。戻り値はすべてArrayList。6章1節の概要に、メソッド一覧 をtable形式で出した。
6章では、Listパッケージとは別フォルダに作ったテストプログラムからパッケージを使うようなトライをしたが、なかなか使える状態にならず難航したが、別フォルダにもpackage宣言必須ということで解決した。その必要性が腑に落ちず、難航した原因となったが、解決したいまも釈然としないところがある。
7章はオーバーライド。「Java基礎2」でもStackの例でもやっているが、パッケージ化したものの一つ、Sentenceに対するオーバーライドで、再度トライした。簡単にできるつもりだったが、Stackの例では引数なし、Sentenceは引数つきというだけ、かつ、もとがパッケージの中にあるということで、予想をはるかにこえて大いに難航した。最後は、もとのクラスに空のコンストラクタがあれば、引数の有無は関係ない ということで、すっきりした解決となった。
8章は、5章の1000件程度という制約をこえて、はるかに大量のデータが扱えるよう、pratitionの再帰をやめて、普通の繰り返しにした。ArrayListの代入も必要となり、戻り値をArrayListにしたリスト処理のパッケージが役立った。
9章はソート結果をファイルに書き出している。ついでに、処理時間も調べた。1万件は約1秒と即座にクリア、20万件も約6分と多少時間がかかったが、 30万件 では、23分弱となる。本にあったマージソート、再帰を使っていないものだろうが、桁違いに速かった(9章5節 おまけ参照)。
[参考] JavaTM 2 Platform, Standard Edition, 1.4.0 API 仕様 「Javaチュートリアル 第３版」 M.カンピオーネ他 安藤慶一訳(ピアソン・エデュケーション 2001年11月) 「独習Java」(ジョセフ・オニール、翔泳社 1999/5 初版)
まずは、簡潔なロゴ(Logo)のプログラムで、基本的なアルゴリズムを記しておく。クィックソートの考え方を説明するのにも使い、Javaへの書き換えでも、コメントの形で追記するので、ロゴのリスト処理関係のコマンドも簡単にふれておく。
TO QSORT :L
IF :L = [ ] [OP [ ]]
IF ( BF :L ) = [ ] [OP :L]
OP PARTITION [ ] FIRST :L [ ] BF :L
END
TO PARTITION :LEFT :X :RIGHT :L
IF :L = [ ]
[OP SE QSORT :LEFT FPUT :X QSORT :RIGHT]
IF :X < ( FIRST :L )
[OP PARTITION :LEFT :X FPUT FIRST :L :RIGHT BF :L]
OP PARTITION FPUT FIRST :L :LEFT :X :RIGHT BF :L
END
1 上記はロゴライターの例である。下記のような特徴とコマンド(一部)がある。
・変数、配列は、:Xのように、: をつける。
・型宣言はなし。上記の例では、プログラムからみて、
:L,:LEFT,:RIGHT は配列。:Xは変数。
・ここにでてきているコマンドは、ほとんどがリスト処理系のもの。
TO 関数
OP (OutPut) return相当。再帰では、ここまで、処理不能のところをすべて
でスタックにため込んでおき、OPがきたところで、スタックからとりだ
し、処理を始める。
FIRST リスト(配列の一種)の先頭の要素をとりだす。
BF (ButFirst) リストの先頭要素を除いた残りのリスト。
FPUT (FirstPut) リストの先頭に、要素をいれる。
SE (Sentence) リストの結合、空白リストは[]を除去。
REPEAT 繰り返し
PR (Print) 画面に表示
MAKE 代入 (= は、IF文の中の等号であって、代入文としては使えない)
[ ] 空のリスト(初期化の必要なく、いきなり使える)
2 この例では、QSORTのプログラムから、4つの引数をとるPARTITIONの関数を呼び出
し、その結果を受け取ることになり、普通なら、QSORTを呼び出して、再帰するとこ
ろが様相が異なる。PARTITIONは、自分自身を呼び出す普通の再帰ではあるが、なん
と、途中でQSORTを呼び出している。
QSORTとPARTITIONとていったりきたり、下手すると、簡単にループに陥る。
リストの先頭の値を基準に、それより小さいものを左に、大きいものを右に
集める。 PARTITIONで行なっている処理はこれである。
左、右とも、まだ小さい順になっているわけではないから、左や右のリストを最初
の :Lに変わる新しいリストとして、また、QSORTに戻す。
QSORTは、左や右のリストをそれぞれ、新しい:L、新しい:LEFT や :RIGHT は空白に
して、再び、PARTITIONにきて、新しい:Lの先頭要素をもとに、また、左右に分ける。
最初の :L、:LEFT や :RIGHT がなくなってしまいそうであるが、それは、とりあえ
ず、スタックへ格納し、最後に上からとりだして順次処理する仕組み。それが再帰に
よる繰り返し処理の面白いところである。
これを繰り返して、最初のリスト、左、右に分けて次々に作られるリストが完全に
空になるか、1項だけになると、その値(OP [] ないし、OP :L)を出発点として、スタ
ックからのとりだし処理を開始して、左 + FIRST + 右 と並べて、 ソートが完了
するという仕組み。この結合をFPUTとSEでやっている。
[実行]
コマンドプロンプト相当、ロゴライターでいうコマンドセンターから、
PR QSORT [5 2 8 3 9 6 4 1 7] とでもする。
[ ] 内が、このプログラムの場合の :Lになる。
下記のJavaのプログラム例、qsort2 や partition の右側に、コメントの形でロゴのコマンドを記述した。Javaの場合、多少、準備が必要なので、冗長にはなるが、基本的には変わらない結果になった。しかし、そこまでもっていくのは大変だった。
特に、partition の最大の難所であるqsort2への戻り。コメントのところで詳述する。リスト処理を本命とするLispやロゴではできても、Javaでこのような複雑な再帰用法が扱えるかどうかという懸念もあったが、それは幸いに杞憂に終わった。
Listとついていることから選択したArrayListだが、使い方になれるにつれ、やはりリスト処理的なことに最も向いているようにみえてきた。
「Javaチュートリアル 第３版」付録C のコレクションのところでもふれられている。ArrayListは、コレクションインスタンスの実装という。Vectorとどこか似ていて、どちらを使うのがいいかと迷うところもあったが、同書のP503に「Vectorとの比較」という節もあって、その欠点を改善しているところもあるという。
メソッド名を短くして、VectorのelementAt()やsetElementAt()が、ArrayListでは、 get(),set() と、簡潔になっているなど。
なお、Vectorについては「独習Java」の10章に説明がある。
//cd c:\HPTak\Program\JavaBasic3\Qsort
//set CLASSPATH=.
//javac Qsort.java
//java Qsort 3 9 4 7 5 1 8 6 2
//java Qsort c d f e g a k b f
//クィックソート(ArrayList使用)
import java.util.*;
public static void main(String[] args) {
ArrayList al = new ArrayList(10); //リストとその要素を作成する
for (int i=0; i < args.length; i++)
al.add(i,args[i]); //コマンドライン引数をargsで受け取りリストに。
System.out.println("クィックソート" );
System.out.println("Qsort Start" + al);
System.out.println("Qsort 結果" + qsort2(al));
}
static ArrayList qsort2(ArrayList al){
if (al.isEmpty() || al.size() ==1)
return al; // RETURN :L 相当
String first=al.get(0).toString(); // FIRST :L
ArrayList left=new ArrayList(10); //:LEFT=[]
ArrayList right=new ArrayList(10); //:RIGHT=[]
al.remove(0); // BF :L
return partition(left,first,right,al);
}
static ArrayList partition(ArrayList left,String first,ArrayList right,
ArrayList bf) {
if (bf.isEmpty()) { // :L = []
ArrayList alt = qsort2(left);
// System.out.println("partition return:qsort2(left)= " + alt);
ArrayList alt2 = qsort2(right);
// System.out.println("partition return:qsort2(right)= " + alt2);
Sentence st3 = new Sentence(alt,first,alt2);
return st3.ss3(alt,first,alt2);
// alt = qsort2(left) alt2 = qsort2(right)
//OP SE QSORT :LEFT FPUT :X QSORT :RIGHT 相当
}
String first2=(bf.get(0)).toString();
bf.remove(0); // BF :L
if (first.compareTo(first2) < 0) { //:X<( FIRST :L )
right.add(0,first2); //FPUT FIRST :L :RIGHT
return partition(left,first,right,bf);
} else {
left.add(0,first2); //FPUT FIRST :L :LEFT
return partition(left,first,right,bf);
}
}
}
java Qsort 3 9 4 7 5 1 8 6 2 Qsort 結果 [1, 2, 3, 4, 5, 6, 7, 8, 9] java Qsort c d f e g a k b f Qsort 結果 [a, b, c, d, e, f, f, g, k]
1 最も難航した点は発想の転換ができず、必要のない変数への代入 にこだわって
しまったことである。
たとえば、qsort2 の ArrayList al から先頭要素を取り去る al.remove(0) 。
先頭要素をとり出すのは、first=al.get(0).toString() と、代入が可能なので、
なんとか、bf= al.remove(0) のように代入するか、ロゴのように引数に直接使いた
かったが、だめだった。
2 理由は簡単、 al.get(0) の戻り値は Object だが、al.remove(0)の戻り値は
boolean で、取り除きに成功すれば、trueが戻るだけだからである。
JavaTM 2 Platform, Standard Edition, 1.4.0 API 仕様 にも明記されている。
3 al.remove(0); としておけば、先頭要素を取り除いたものは、al であることにやっ
と気づいた。ArrayListに、たとえばコマンドラインの引数ををいれていくときは、代
入など考えず、al.add(i,new Integer(n))とかal.add(i,args[i])と書きっぱなしだっ
たはず!! (「Javaの基礎」 6、7章)
「Javaの基礎」5章のVectorには、
vector.remove(0); //vector.removeElementAt(0);でも同じ
と、きちんとできていたことにも気づいた。今頃、見直しても遅いが、当時の試行錯
誤の状況は記録していなかった。
4 前述したように、partition の最大の難所はqsort2への戻りである。
ロゴでいうリストの結合、最初は
return (qsort2(left).add(first).add(qsort2(right)));
としていたが、このadd()もremove()同様、戻り値はbooleanで「間接参照できない」
とやられて難儀した。2と違って書きッぱなしというわけにもいかない。
5 結局、ArrayList同士やStringとの結合は別途作成して、Sentenceとした。(次の4章)
Sentence st3 = new Sentence(alt,first,alt2);
return st3.ss3(alt,first,alt2);
//alt = qsort2(left) alt2 = qsort2(right)
//OP SE QSORT :LEFT FPUT :X QSORT :RIGHT 相当
の2行が、Sentenceクラスと関連するが、次の章で詳述する。
[2010.9.24 追記]
このまま、実行すると、
Qsort.java:54: シンボルを見つけられません。
シンボル: クラス Sentence
場所 : Qsort の クラス
Sentence st3 = new Sentence(alt,first,alt2);
となる。 ^
4章にある、Sentenceクラスを結合し、
public class Sentence { から、public をはずして、コンパイル。
^
注:Qsort.java の操作は、未チェックまたは安全ではありません。
注:詳細については、-Xlint:unchecked オプションを指定して再コンパイルしてください。
となるが、
c:\Java\JavaTry2010>javac Qsort.java -Xlint:unchecked
とすると、
Qsort.java:31: 警告:[unchecked] raw 型 java.util.ArrayList のメンバとしての add(int,E) への無検査呼び出しです。
al.add(i,args[i]);
など、警告 8 個が出るが、コンパイルはできた。
c:\Java\JavaTry2010>java Qsort c d f e g a k b f
クィックソート
Qsort Start[c, d, f, e, g, a, k, b, f]
Qsort 結果[a, b, c, d, e, f, f, g, k]
Sentenceクラスの結合には、7章にもふれている package という手法があるが、忘れているので、今はこのままとする。
クィックソートのプログラムでどうしても必要なのは、se3、またはss3である。３つのオブジェクトの結合、se3では、最初のArrayList aa に、2番目、３番目をadd（）メソッド を適用していくだけ。ここで書きっぱなしを３つ並べればいいことは、３章のコメントに詳述したような学習効果のおかげである。結合した結果は、aa。
ただし、add（）メソッドが使えるのは、Objectという抽象的なものでなく、ArrayListでなければならない。Object型の引数alをどうして、ArrayListにできるかに苦労した。
試行錯誤の結果、 ArrayList aa = (ArrayList)a1; (a1はObjectとして受け取る引数)。
こういう型変換で簡単にできたことに驚いた。戻り値もaaとなるから、ArrayListにできる。
Sentenceクラスには、3通りのコンストラクターも作ってみた。
以下、詳細は[コメント]で後述することにして、概要のみ記す。
a se3をクィックソートに適用すると、データが3ケまでのものはデータ次第で成功し
たり、ループしたりだったが、4ケ以上になると、すべてループに陥り、理由がわか
らず大いに苦労した。
b できてしまえば、いたって簡単なse3では、クィックソートに適用すると、再帰に
よる繰り返し処理の過程で、空白の[]があったり、[]が何重にもついて不都合なの
で、ss3のようなやや複雑て処理を加えることにした。
import java.util.*;
public class Sentence {
Object a1;
Object a2;
Object a3;
public Sentence (Object a1) {
this(a1,null,null);
}
public Sentence (Object a1,Object b1) {
this(a1,b1,null);
}
public Sentence (Object a1,Object a2,Object a3) {
this.a1=a1;
this.a2=a2;
this.a3=a3;
}
public ArrayList se(Object a1,Object a2) {
ArrayList aa = (ArrayList)a1;
aa.add(a2);
return aa;
}
public ArrayList se3(Object a1,Object a2,Object a3) {
ArrayList aa = (ArrayList)a1;
aa.add(a2);
aa.add(a3);
return aa;
}
public ArrayList ss3(Object a1,Object a2,Object a3) {
ArrayList aa = (ArrayList)a1;
ArrayList aa3 = (ArrayList)a3;
String aa2=(String)a2;
if (aa2.length() > 0)
aa.add(aa2);
if (aa3.size() > 0) {
int n=aa.size();
for (int i=0; i < aa3.size(); i++) {
aa.add(n+i,aa3.get(i));
}
}
return aa;
}
}
1 何度も書いているが、クィックソートのプログラムで partition の最大の難所は
qsort2への戻り。そのポイントを再掲すると、
Sentence st3 = new Sentence(alt,first,alt2);
return st3.ss3(alt,first,alt2);
// alt = qsort2(left) alt2 = qsort2(right)
//OP SE QSORT :LEFT FPUT :X QSORT :RIGHT 相当
st3という前掲のSentenceクラスへの参照変数を実現するために、Sentenceに引数3
ケのコンストラクタを作った。
2 最初は、簡単な作りのse3メソッドで、まず、3ケまでのデータでトライ。
return st3.ss3(alt,first,alt2);
java Qsort 6 2 7 は OK
java Qsort 6 2 3 は ループしたあげく、StackOverflowError。
もちろん、4ケ以上のデータも同じエラーになる。
3 この理由がわからず、なんども同じエラーを出し、ほとんどあきらめかけていた。
最初に、partitionからqsort2に戻ってきたとき、left ないし rightに１ケしか入っ
ていない場合は、left ないしrightのそれぞれが、再帰によって新しいalになるから
qsort2の１行目がきいて終了する。
そうならず、2度目に、partitionに入ると、そこでループするということになる。
4 最初、qsort2で、left とrightを初期化するのはまずいからと、グローバル変数に
して、qsort2の外で宣言、面倒だからと、public、そしてstaticまでつけていた。
qsort2に戻るたびに、過去の処理はすべてスタックに預けて、新しい形でやらない
といけないことは承知していたはずなので、これは単純な錯覚。
戻ってきた left ないしrightを新しいal、新しいleftとrightは最初と同じく
空白にして、partition にいれなければならない。
5 そこで、left とrightの宣言、初期化の
ArrayList left=new ArrayList(10);
ArrayList right=new ArrayList(10);
をqsort2の中にいれて解決した。
6 java Qsort 6 2 3 結果 [2, 3, [], 6, []]
java Qsort 6 2 3 7 結果 [2, 3, [], 6, [7]]
7 これでは少し格好が悪いからと、パッケージ内、Sentence内で、2番目、3番目は空白
ならaddしないで無視。3番目のArrayListのaddはget()で、１項ずつとり出してaddす
るようにした。これが、se3を改良した ss3のメソッド である。
この結果は3章3節に掲載ずみ。
クィックソートのこの再帰は、ロゴの場合もあまり大量のデータを扱えず、前述したように、partitionは再帰によらない普通の繰り返しにしたこともある。Javaではどの程度、再帰でできるか、乱数を発生させてやってみた。
Mathクラスに、0から1までのdouble型の乱数を発生させるrandom()というクラスメソッドがあるが、それは以前やっているので、こんどは、「独習Java」10章に紹介のあったjava.utilityパッケージの中にある Randomクラス を使ってみる。ガウス型の乱数も発生させられ、現実をシミュレートするのにも役立つとある。double型などさまざまな型でできるようだが、本の例題にしたがっていたら、整数型だったのでそのまま使う。generator.nextInt() を使うので当然か？
なお、VectorやArrayListクラスも、java.utilityパッケージに属している。
Randomクラスは、double型、long型などさまざまな型で生成できるようだが、本の例題にしたがっていたら、整数型だったのでそのまま使う(generator.nextInt()を使うので当然か？)。ただ、非常に大きな数となり、いまの場合は、煩わしいので、1000000で割った整数とした。
1000ケのデータまではできた。1200ではStackOverflow(大量データは8章にて)。いままでのソースを使うと、文字型で比較するため、数値のソートにはあわないので、変更してみた。ArrayListには、オブジェクト型でいれるので、主たる変更点はString型からInteger型に変更したところである。主な変更点を下記に、細部はコメントに書く。
import java.util.*;
public class Qsort2 {
public static void main(String[] args) {
ArrayList al = new ArrayList(10);
int n=1000; //1200 ではStackOverflowError
Random generator = new Random(); //ここから6行変更
for (int i=0; i < n; i++) {
int rand = generator.nextInt()/1000000; //整数乱数発生
Integer rn = new Integer(rand); //Integer化
al.add(i,rn);
} //ここまで
System.out.println("クィックソート" );
System.out.println("Qsort Start" + al);
System.out.println("Qsort 結果" + qsort(al));
}
static ArrayList qsort(ArrayList al){
.................
String firsts=al.get(0).toString(); //第1項をとり出し、Objectから
Integer first=Integer.decode(firsts); //Stringへ、そしてIntegerへ。
.................
}
static ArrayList partition(ArrayList left,Integer first,ArrayList right,ArrayList bf) {
.................
String first2s=bf.get(0).toString(); //上に同じ
Integer first2=Integer.decode(first2s); //上に同じ、追加
Stringへ、そしてIntegerへ。
.................
}
}
import java.util.*;
public class Sentence2 {
.................
public ArrayList sn3(Object a1,Object a2,Object a3) {
.................
// String as2=(String)a2; もともとInteger型のa2では変換不可。
String as2=a2.toString(); //変更
Integer aa2=Integer.decode(as2); //追加
if (as2.length() > 0)
aa.add(aa2); //変更
if (aa3.size() > 0) {
int n=aa.size();
for (int i=0; i < aa3.size(); i++) {
aa.add(n+i,aa3.get(i));
}
}
return aa;
}
}
C:\HPTak\Program\JavaBasic3\Qsort>java Qsort2 (1000ケの場合、途中省略) Qsort 結果 [-2141, -2136, -2133, -2124, -2121, -2121, -2113, -2113, -2100, -2098, ............................................. 2082, 2095, 2098, 2098, 2107, 2108, 2108, 2117, 2119, 2120, 2124, 2130, 2131, 2146, 2147]
1 思ったより簡単にできたが、qsort,partition の中で第1項をal.get(0),bf.get(0)
と、ArrayListのget()メソッドでとり出すと、Object型になる。
下記のように型変換で一気に Integerにしようとして、失敗。
Integer first=(Integer)al.get(0); //ClassCastException
2 いままでどおり、String firsts=al.get(0).toString()で、Stringとして、Integer
クラスのdecodeメソッド で、Integerとする。
Integer first=Integer.decode(firsts);
3 partition中の引数のfirstとArrayListの中の第一項の比較
、 if (first.compareTo(first2)<0)
は、Integerクラスにも、compareToがあるので、そのまま使えた。
3 Sentenceクラスも変更しないといけないので、特化させて、Sentence2とする。
ここでは、第2引数のObject a2を String型への型変換
String as2=(String)a2
ですませていたが、文字列の数をみるlengh()には使えても、それを上記のdecode()
で、Integer型にしようとするとエラーとなる。理由は不明。
2､3と同じようにして、成功した。
リスト処理として、上記のSentenceだけでなく、、先頭の要素を除くBF相当(al.remove(0)の戻り値をalとするもの)、「Javaの基礎」でやったFPUTやINSERTも加えて、パッケージ化してみた。そして、簡単にテストするためのTest.javaも作った。
Sentenceの例でいうと、文字型(String)の4章2節のリストと、数値型(Integer)の5章2節をあわせたものとしている。INSERTも数値型を加えた。詳しくは、3節参照。
パッケージ化する過程でも苦労した。Test.javaやSentence.javaなどを 同一のフォルダ Listにいれて、package List; とすれば問題ないが、リスト処理はパッケージとして独立させたくて、Test.java を別フォダにいれると、まったくだめな状況だったが、ようやくできた。package宣言必須ということで、その別フォダをTestListとすると、TestList; がいるというのである。釈然としないところがあって、難航したのもそのため。
[2005/12 追記]
バスカルの三角形 の2-5で、再度、パッケージ化に挑戦し、上記、疑問はすべて解決した。
Sentence、FPut、Bf、Insert
Test (リスト処理パッケージと同一フォルダ)
TestList (リスト処理パッケージと別フォルダ)
| クラス名 | コンストラクタ | メソッド | 機能 |
|---|---|---|---|
| Fput | Fput(Object a1,Object a2) | fput(Object a1,Object a2) | a1をa2の先頭に挿入 |
| Bf | Bf(Object a1) | bf(Object a1) | a1から先頭要素を除く |
| Insert | Insert(Object a1,Object a2) | insert(Object a1,Object a2) | a2とa1を文字比較して、a1より大きいものの前にa1を挿入 |
| Insert | 同上 | insertn(Object a1,Object a2) | a2とa1を数値比較して、a1より大きいものの前にa1を挿入 |
| Sentence | Sentence(Object a1,Object a2) | se(Object a1,Object a2) | 2つの要素の結合 |
| Sentence | Sentence (Object a1,Object a2,Object a3) | se3(Object a1,Object a2,Object a3) | 3つの要素の結合 |
| Sentence | 同上 | ss3(Object a1,Object a2,Object a3) | 空でない3つの要素の結合(文字型) |
| Sentence | 同上 | sn3(Object a1,Object a2,Object a3) | 空でない3つの要素の結合(数値型) |
[注]
1 戻り値は、すべてArrayList。
2 すべてに、空のコンストラクタ がある。
Fput(),Bf(),Insert(),Sentence() である。
3 最初は空のコンストラクタがなく、7章のオーバライドで痛い目にあい、急遽追加。
おかげで、普通に使うインスタンス化にも、引数不要になり、少しはみやすくなっ
た。8章のクィックソートではそうしている。
Fput fr = new Fput(); (Fput fr = new Fput(first2,right);より簡潔)
Bf b = new Bf(); など。
4 7章 オーバライドの題材は、パッケージの中のSentenceクラスを継承、se3メソッド
をオーバライドして、ss3相当のものを作り出すことである。
C:\HPTak\Program\JavaBasic3\Package>java List.Test 3 5 2 7 9 Sentence Test [-1538, -485, -1346, -1554, 10, -800, -1506, -1337, 1342, -1026, 6, 3, 5, 2, 7,9] Fput Test [6, -1538, -485, -1346, -1554, 10, -800, -1506, -1337, 1342, -1026, 6, 3, 5, 2,7, 9] Bf Test [-1538, -485, -1346, -1554, 10, -800, -1506, -1337, 1342, -1026, 6, 3, 5, 2, 7,9] Insert Test [-1538, -485, -1346, -1554, 6, 10, -800, -1506, -1337, 1342, -1026, 6, 3, 5, 2,7, 9]
[リスト処理パッケージと同一フォルダの場合]
1 親フォルダをPackage、パッケージをおくサブフォルダをListとして、リスト処理関
連のもろもろのプログラムにも、テストプログラム Test.javaにも、package List;
宣言をする。
2 コンバイルと実行は、カーレントドライブをPackageとして、下記のように、Listか
らのパスで行う。
cd c:\HPTak\Program\JavaBasic3\Package
set CLASSPATH=. //必要なら行う(同一フォルダの場合は不要かも?)
javac List\*.java
java List.Test 3 5 2 7 9
問題なし。
3 Test.javaには、import List.*; をいれたが、これをとっても結果は問題なし。
4 package List; をコメントにすると、コンバイルで、Sentenceなどのシンボルを解
決できないとなる。set CLASSPATH=. としてからやってもおなじ。
5 package List; をコメントにして、import List.*;をいれると、コンバイルはでき
るが、下記のエラーとなる。
C:\HPTak\Program\JavaBasic3\Package>java List.Test 3 5 2 7 9
Exception in thread "main" java.lang.NoClassDefFoundError: List/Test (wrong name: Test)
at java.lang.ClassLoader.defineClass0(Native Method)
at java.lang.ClassLoader.defineClass(Unknown Source)
at java.security.SecureClassLoader.defineClass(Unknown Source)
at java.net.URLClassLoader.defineClass(Unknown Source)
at java.net.URLClassLoader.access$100(Unknown Source)
at java.net.URLClassLoader$1.run(Unknown Source)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClassInternal(Unknown Source)
6 Test.javaにも、package List;が必須ということである。import List.*; は、下記
では必須なので、同一フォルダにあるときに限り、不要なのだろう。
[リスト処理パッケージとテストプログラムが別一フォルダの場合]
1 親フォルダをPackage、パッケージをおくサブフォルダをListとして、リスト処理関
連のもろもろのプログラムをおくことは同じだが、テストプログラム Test.javaは、
Packageの下のTestListフォルダにおき、package TestList; 宣言をする。
2 コンバイルと実行は、カーレントドライブをPackageとして、下記のように TestList
からのパスで行う。
cd c:\HPTak\Program\JavaBasic3\Package (List内はコンパイル済み)
set CLASSPATH=. //必須のよう(別フォルダの場合)
javac TestList\Test.java
java TestList.Test 3 5 2 7 9
問題なし。
3 import List.*; をとると、コンパイルでSentenceなどのシンボルを解決できない
となるので、この場合は必須。また、クラスパス設定のset CLASSPATH=. も必要。
4 パッケージ名とフォルダ名とは一致させるということなので、package TestList;と
して、解決したが、それをとると、上記の5と同じエラーとなる。
package TestList必須には、釈然としないところがあるが。
5 最初、別フォルダにおいた場合、なかなかうまくいかず「独習Java」のP213から225
まで、練習問題の解答も読み、「Javaチュートリアル」のP199〜P203、 P243〜P251
も熟読し、練習問題のトライも問題ない。
「同じようにしているはずだが、どうして」というコメントまで用意していた。
Sentence中のss3は特殊なので、別途、se3をオーバーライドするトライをしたが、なぜか失敗の連続であった。「Javaの基礎2」 の5章では、Stackのオーバーライドに成功しているし、5章のコメントBの4 と同じ方法でいいはずと自信があったのだが!!
これまた、ほとんどあきらめかけるくらい難航した。Stackのオーバーライドと何が違うのか見直してみると、コンストラクタに引数 があるかないかの違いに気づき、変数宣言と引数つきのコンストラクタをオーバーライドするSentenceOverrideクラスに追加して、やっと解決した。
その後、Sentenceに、空のコンストラクタを追加することにより、Stackのオーバーライドと同じ手法でできてしまった。
オーバーライドのもとになるSentenceは、パッケージ化してあるので、そこからのオーバーライドもトライしたが、これも失敗の連続、ようやくできた。バッケージ化する場合のもろもろのお約束事遵守に欠ける点もあった。
package Override;
import java.util.*;
import List.*;
public class SentenceOverride extends Sentence {
public ArrayList se3(Object a1,Object a2,Object a3) {
ArrayList aa = (ArrayList)a1;
ArrayList aa3 = (ArrayList)a3;
String aa2=a2.toString();
if (aa2.length() > 0)
aa.add(aa2);
if (aa3.size() > 0) {
int n=aa.size();
for (int i=0; i < aa3.size(); i++) {
aa.add(n+i,aa3.get(i));
}
}
return aa;
}
}
TestOverrideのソース (TestOverride にあり)
//cd c:\HPTak\Program\JavaBasic3\Package
//set CLASSPATH=.
//javac Override\*.java
//java Override.TestOverride 3 5 2 7 9
package Override;
import java.util.*;
import List.*;
public class TestOverride {
public static void main(String[] args) {
ArrayList alt = new ArrayList(10);
ArrayList alt2 = new ArrayList(10);
for (int i=0; i < args.length; i++)
alt.add(i,args[i]); //String型
ArrayList alt3=(ArrayList)alt.clone(); //altのコピー
for (int i=0; i < args.length; i++)
alt2.add(i,Integer.decode(args[i])); //Integer型
Integer s = new Integer(6);
System.out.println("Sentence Test");
Sentence st3 = new Sentence(alt,s,alt2);
System.out.println(st3.ss3(alt,s,alt2));
SentenceOverride sto = new SentenceOverride();
// Sentence sto = new SentenceOverride(alt,s,alt2); これでもいい
System.out.println("SentenceOverride Test");
System.out.println(sto.se3(alt3,s,alt2));
}
}
C:\HPTak\Program\JavaBasic3\Package>javac Override\*.java
コンバイル OK
C:\HPTak\Program\JavaBasic3\Package>java Override.TestOverride 3 5 2 7 9
Sentence Test
[3, 5, 2, 7, 9, 6, 3, 5, 2, 7, 9]
SentenceOverride Test
[3, 5, 2, 7, 9, 6, 3, 5, 2, 7, 9]
1 SentenceOverrideでやっていることは、Sentenceの中の簡単なse3メソッドを複雑に
したもので、Sentenceの中のss3と同じである。
2 最初は、SentenceOverrideには、コンストラクタをいれていなかった。Stackのとき
のように引数なしのメソッドの場合はそれでよさそうだが、引数の必要な場合は、コ
ンバイルできず、下記 のエラーに悩まされた。
シンボル: コンストラクタ SentenceOverride を解決できない。
3 public class SentenceOverride extends Sentence {
のSentenceがコンストラクタであるかのようなエラーもあった。
4 SentenceOverride に、下記を追加したが、状況は変わらず。
Object a1; Object a2; Object a3;
5 SentenceOverride に、4の変数宣言と引数つきのコンストラクタを追加して、よう
やく解決した。本には、コンストラクタのいらない簡単な例しかないから、ほんとう
に苦労した。
public class SentenceOverride extends Sentence {
Object a1;
Object a2;
Object a3;
public SentenceOverride(Object a1,Object a2,Object a3) {
this.a1=a1;
this.a2=a2;
this.a3=a3;
}
........................
}
インスタンス化は、Sentence sto = new SentenceOverride(alt,s,alt2);
6 4でも、最初は、sto.se3(alt,s,alt) のようにしていたため、実行時に、
OutOfMemoryError というエラーが出て、オーバーライド絡みの深刻なエラーと錯覚
したが、se3の中のfor ループの上限がおかしくなったためだった。第3引数のaltは
第1引数のaltに第2引数のsが追加されているため、サイズが大きくなっていたため。
7 もともとのSentenceに、空のコンストラクタを追加するだけでもよい。
ただし、インスタンス化は、SentenceOverride sto = new SentenceOverride();
5の追加も不要でずっと簡単になるし、Stackのときと同じ形ですむ。
8 最初のトライは、System.out.println(sto.se3(alt,s,alt2)) と、Sentence Testの
ときと同じ引数であった。
java TestOverride 3 5 2 7 9
Sentence Test
[3, 5, 2, 7, 9, 6, 3, 5, 2, 7, 9]
SentenceOverride Test
[3, 5, 2, 7, 9, 6, 3, 5, 2, 7, 9, 6, 3, 5, 2, 7, 9]
Sentence Testの結果がスタートのaltになるため、その分が増えてしまった。
スタートの値をあわせるため、ArrayListのコピーをcloneメソッドで作って、alt3と
し、それを 第1引数としたので、両者が一致した。上記、3の実行結果。
5章では、1000件までのデータしか扱えなかったが、もっと大量データをソートさせるたい。リスト処理に強いロゴでも、大きなリストの処理はスタックオーバとなるので、コメントに記すPARTITION2 のように、REPEATを使った普通の繰り返しにして、partitionの再帰を避ける。その場合でも、繰り返し二よって、左右に分割してしまえば、qsortに戻ることは同じである。
繰り返しの方法では、代入も必要となる。それは6章のリスト処理関連をパッケージ化したことで使える状況になり、Javaでトライしてみた。少なくとも100000件はクリアした。
//cd c:\HPTak\Program\JavaBasic3\Package
//set CLASSPATH=.
//javac Qsort4\Qsort4.java
//java Qsort4.Qsort4
//クィックソート(乱数発生、数値比較、大量データ処理)
package Qsort4;
import java.util.*;
import List.*;
import java.util.*;
public class Qsort4 {
static int n=200000; //乱数の発生回数
public static void main(String[] args) {
ArrayList al = new ArrayList(10);
Random generator = new Random();
for (int i=0; i < n; i++) {
int rand = generator.nextInt();
Integer rn = new Integer(rand);
al.add(i,rn);
}
System.out.println("クィックソート " + n + " 件");
// System.out.println("Qsort Start" + al);
System.out.println("Qsort 結果" + qsort2(al));
}
static ArrayList qsort2(ArrayList al){
................
return partition2(left,first,right,al);
}
static ArrayList partition2(ArrayList left,Integer first,ArrayList right,ArrayList bf) {
for (int i=0; i < n; i++) { //追加
if (bf.isEmpty()) {
ArrayList alt = qsort2(left);
ArrayList alt2 = qsort2(right);
Sentence st3 = new Sentence();
return st3.sn3(alt,first,alt2);
}
String first2s=bf.get(0).toString();
Integer first2=Integer.decode(first2s);
if (first.compareTo(first2)<0) {
Fput fr = new Fput(); //バッケージ利用
right=fr.fput(first2,right); //代入
} else {
Fput fl = new Fput(); //バッケージ利用
left=fl.fput(first2,left); //代入
}
Bf b = new Bf(); //バッケージ利用
bf=b.bf(bf); //代入
}
System.out.println("partition2 error");
return null; //なぜかreturn文要求
}
}
クィックソート 100000件
[................
214692, 214692, 214696, 214697, 214697, 214705, 214711, 214715, 214717,
214724, 214729, 214733, 214735, 214745]
クィックソート 200000件(乱数の桁数を増やす)
[................
2147376316, 2147413897, 2147428993, 2147431036, 2147436042, 2147460882,
2147481653]
1 ロゴの例
TO PARTITION2 :LEFT :X :RIGHT :L
REPEAT 9999
[IF :L = [ ]
[OP SE QSORT :LEFT FPUT :X QSORT :RIGHT]
IFELSE :X < ( FIRST :L )
[MAKE "RIGHT FPUT FIRST :L :RIGHT]
[MAKE "LEFT FPUT FIRST :L :LEFT]
MAKE "L BF :L]
END
2 MAKEによる代入文をパッケージの中で作ったFputとBfでさせている。いずれも戻り値
をArrayListにしているから可能になる。
3 partition2の中にqsort2に戻るreturn文があるのに、なぜか、コンバイラがreturn
文を要求したため、末尾に意味のないreturn文を形式的にいれた。
10件のソートでも、1万件でも、10万件でもこれが使われることはなかった。
4 このソースは、Qsort4という、リスト処理パッケージとは別のフォルダにおき、
package Qsort4;
import List.*;
と、6章でクリアした形式にのっとって、無事動作した。
9章のように、10万件ものデータを扱うと、結果をコマンドプロンプト画面には完全には出せない。大半は上書きされて、おしまいの方しかでてこない。当然、ファイルへの書き込みが必要になる。書き出しデータは文字型、処理効率のいいバッファ付きでやってみた。教科書通りで問題なし。
処理時間もDateクラスを使えばいけそうだということでトライ、大した苦労なくできた。
1万件約1秒、10万件約1分、20万件で約6分強、30万件で約23分弱。
//cd c:\HPTak\Program\JavaBasic3\Package
//javac QsortFile\QsortFile.java
//java QsortFile.QsortFile 300000
package QsortFile;
import java.util.*;
import java.io.*;
import List.*;
public class QsortFile{
static int n;
public static void main(String[] args) throws IOException {
ArrayList al = new ArrayList(10);
n=Integer.valueOf(args[0]).intValue(); //乱数発生回数
Random generator = new Random();
for (int i=0; i < n; i++) {
int rand = generator.nextInt();
Integer rn = new Integer(rand);
al.add(i,rn);
}
System.out.println("クィックソート " + n + " 件");
FileWriter fw = new FileWriter("QsortFile/output300000.txt");
// FileWriterオブジェクト
BufferedWriter out = new BufferedWriter(fw);
// BufferedWriterオブジェクト
out.write("クィックソート " + n + " 件" + "\n");
Date t1= new Date();
long starttime=t1.getTime();
out.write("ソート結果 " + qsort2(al) + "\n");
Date t2= new Date();
long finishtime=t2.getTime();
long processtime=finishtime-starttime;
System.out.println("starttime = " + starttime + " finishtime = " + finishtime + " processtime = " + processtime);
out.close(); // BufferedWriterオブジェクトのクローズ
}
static ArrayList qsort2(ArrayList al){
...............同じ..........
}
static ArrayList partition2(ArrayList left,Integer first,ArrayList right,ArrayList bf) {
...............同じ..........
}
}
クィックソート 10000 件(ファイル容量 118KB)
starttime = 1095084599078 finishtime = 1095084600031 processtime = 953
クィックソート 10000 件
starttime = 1095084046609 finishtime = 1095084047640 processtime = 1031
クィックソート 100000 件
starttime = 1095084289937 finishtime = 1095084352000 processtime = 62063
クィックソート 200000 件
starttime = 1095084799093 finishtime = 1095085176765 processtime = 377672
クィックソート 200000 件
starttime = 1095117709703 finishtime = 1095118069140 processtime = 359437
クィックソート 300000 件(ファイル容量 3511KB)
starttime = 1095119610093 finishtime = 1095120987656 processtime = 1377563
ソート結果 300000 件
[-2147480473, -2147479126, -2147478670, -2147469398, -2147467802,
-2147459853, -2147457236, -2147429617, -2147423824, -2147396264,
.................................
2147360240, 2147367126, 2147376366, 2147393082, 2147421369, 2147428448,
2147441797, 2147451242, 2147456738, 2147459830, 2147470909]
1 8章のプログラムとの違いは、画面表示のprint文に変えて、
FileWriter fw = new FileWriter("QsortFile/output300000.txt");
BufferedWriter out = new BufferedWriter(fw);
out.write("クィックソート " + n + " 件" + "\n");
out.write("ソート結果 " + qsort2(al) + "\n");
と、ファイル書き出しのためのインスタンスoutを使って、直接、qsort2(al) を
ファイルに書き出していることである。
2 追加書き込みをしたが、特に引数不要ですんだ。
3 上記、書き出しのファイル名をコンストラクタFileWriterの引数にしたが、最初
"QsortFile\output.txt"として、エラー。
4 発生させる乱数をコマンドライン引数にした。
5 乱数の桁数は10桁、マイナスや区切りの記号もあって、11バイトとみなすと、
ファイル容量は、11バイトに件数をかけたもので、計算があう。
6 DateクラスのgetTime()メソッドで得る、starttime やfinishtimeの巨大な値は
1970/1/1からのミリ秒単位の経過時間という。
最初は、Date t= new Date() と、インスタンスを1ケしか作らなくて、startも
finishも同じ値だったという以外は問題なかった。
1 「Javaチュートリアル」P542 付録C「コレクション」の中にあったマージソートの
プログラムに、乱数発生とファイル出力を加えて所要時間を比較してみた。再帰を使
ったクィックソートより桁違いに速い。
import java.util.*;
import java.io.*;
public class MergeSort{
static int n;
public static void main(String[] args) throws IOException {
ArrayList al = new ArrayList(10);
n=Integer.valueOf(args[0]).intValue(); //乱数発生回数
Random generator = new Random();
for (int i=0; i < n; i++) {
int rand = generator.nextInt();
Integer rn = new Integer(rand);
al.add(i,rn);
}
System.out.println("マージソート " + n + " 件");
FileWriter fw = new FileWriter("output500000.txt");
BufferedWriter out = new BufferedWriter(fw);
out.write("マージソート " + n + " 件" + "\n");
Date t1= new Date();
long starttime=t1.getTime();
Collections.sort(al);
out.write("ソート結果 " + al + "\n");
Date t2= new Date();
long finishtime=t2.getTime();
long processtime=finishtime-starttime;
System.out.println("processtime = " + processtime);
out.close();
}
}
マージソート実行結果
10000件 156ミリ秒
100000件 1016
500000件 4500
1000000件 Exception in thread "main" java.lang.OutOfMemoryError
100万件のメモリエラーは、乱数発生の段階のエラー。容量的には12MBくらいだか
ら、メモリ不足とは思えない。原因不明。
再帰は考え方が面白いし、逐一、値を確定する必要がなく、楽な面もある。効率は
悪いと聞いていたが、かなりのものである。
再帰を使わないクィックソートもやってみる必要があるが、繰り返しの中で値を確
定していかないといけないので、かえって難しそう。次の課題とする。
 |
|
|