第 2 章 Java 言語の基本的な文法 I 5
2.99 SortingExample.java#main ( 追加：ヒープソートによるソート )
// main メソッド内、クィックソートの後ろに以下を追加 System.arraycopy( data, 0, array, 0, data.length );
// ヒープソート
startTime = System.nanoTime();
ArraySorting.heapSort( array );
endTime = System.nanoTime();
MyTools.printIntArray( "heap の結果", array, 5 );
printTime( endTime - startTime );
ソースコード2.100 ArraySorting.java#heapSort (ヒープソート) // クイックソート (quickSortメソッド) の後ろに以下を追加
/**
* ヒープソート (Heap sorting method)
* @param array ソートする整数配列
*/
public static void heapSort( int[] array ) { buildHeap( array );
for(int i=array.length-1; i>0; i--) { MyTools.swap( array, 0, i );
heapUpdate( array, 0, i );
} }
private static void buildHeap( int[] array ) { for(int i=array.length/2-1; i>=0; i--) {
heapUpdate( array, i, array.length );
} }
private static void heapUpdate( int[] array, int parent, int last ) { int left_child = 2 * parent + 1;
int right_child = left_child + 1;
int largest = parent;
if( left_child < last && array[left_child] > array[largest] ) largest = left_child;
if( right_child < last && array[right_child] > array[largest] ) largest = right_child;
if( largest != parent ) {
MyTools.swap( array, parent, largest );
heapUpdate( array, largest, last );
} }
配列の長さnに対し、最初のヒープ木を作成する際にO(nlogn)、後半のヒープ木の修復反復もO(nlogn)の時間 計算量が掛かることが予想されます(詳しくは２年生以降ですね)。
2.20.6 マージソート (Merge sort)
既にソートされた配列２本を１本のソート列に合体させる操作をマージと言います。最も小さなソート列「１要素だ けの列」から初めて、２要素の列のマージ、４要素の列のマージ、とマージする列の長さを倍にしながらマージを繰り 返すことで、１本のソートされた配列を作るアルゴリズムがマージソートです。マージソートは、マージ操作を単純に するために、元配列と同じ大きさの配列をもう１本用意しなければなりません。従って、メモリの少ない環境には向い
ていないソート法です。
ところで、クィックソート以降に説明しているソート法は最初に紹介した単純なアルゴリズム３種類とは異なり、複 雑なアルゴリズムで、アルゴリズムの効率化による効果も大きいため、参考書やネットに紹介されている方法が微妙に 異なっていたりします。このマージソートも、大きさ k のマージが全て終わってから大きさ2k のマージに取り掛か るのではなく、kの列が２本でき次第、大きさ2kのマージを行ってしまう、という方法も考えられます(他にもいろ いろ)。
5 3 7 1 4 2 3 6
3 5 1 7 2 4 3 6
1 3 5 7 2 4 3 6
1 2 3 3 4 5 6 7
array
array2
array
array2
1 2 3 3 4 5 6 7
array
図2.33 マージソートによるソート
ソースコード2.101 SortingExample.java#main (追加：マージソートによるソート)
// main メソッド内、ヒープソートの後ろに以下を追加
System.arraycopy( data, 0, array, 0, data.length );
// マージソート
startTime = System.nanoTime();
ArraySorting.mergeSort( array );
endTime = System.nanoTime();
MyTools.printIntArray( "mergeの結果", array, 5 );
printTime( endTime - startTime );
ソースコード2.102 ArraySorting.java#mergeSort (マージソート) // ヒープソート (heapSortメソッド) の後ろに以下を追加
/**
* マージソート (Merge sorting method)
* @param array ソートする整数配列
*/
public static void mergeSort( int[] array ) { int[] array2 = new int[array.length];
int size = 1;
while( size < array.length ) {
merge( array, array2, size );
merge( array2, array, 2 * size );
size *= 4;
} }
private static void merge( int[] from, int[] to, int size ) { int start = 0;
while( start < from.length ) { int k = start;
int i = start;
int j = start + size;
int iend = Math.min( start + size, from.length );
int jend = Math.min( start + 2 * size, from.length );
while( i < iend && j < jend ) {
if( from[i] < from[j] ) to[k++] = from[i++];
else to[k++] = from[j++];
}
while( i < iend ) to[k++] = from[i++];
while( j < jend ) to[k++] = from[j++];
start += 2 * size;
} }
2.20.7 シェルソート (Shell’s sort)
挿入法がほとんど整列された配列に対しては高速である一方で、あまり整列が進んでいない配列においては隣り合う 要素同士の交換しか行わないので低速であることを逆手に取って、D.L.Shellが1959年に発表したソート法である。ま ず、遠い要素同士を挿入法のアルゴリズムでソートし、徐々に間を狭くしていく。飛び飛びの要素の間隔の取り方で計算 量は変わってしまうが、要素の間隔hをデータ数nに対し、点列{hi}:hi+1= 3hi+ 1, h1= 1, hi< nの最大値から順 に減らしながら取ると、O(n1.25)であることがKnuthによって示されています。({hi}={1,4,13,40,121,364, . . .})
5 3 7 1 4 2 3 6
4 2 3 1 5 3 7 6
h = 4 離れた(同じ色)同士で挿入法ソートを実行
h = 1 : デフォルトの挿入法を実行
1 2 3 3 4 5 6 7
図2.34 シェルソートによるソート
ソースコード2.103 SortingExample.java#main (追加：シェルソートによるソート)
// main メソッド内、マージソートの後ろに以下を追加
System.arraycopy( data, 0, array, 0, data.length );
// シェルソート
ここまで、いろいろなソーティングアルゴリズムを紹介し、それらを同じデータに対する経過時間で比較してみまし たが、果たしてこの実験結果はどれほどの信頼性があるのでしょうか。また、果たして、この経過時間は正確なので しょうか。
まず、Javaにおいて測定できる時間には、次の２種類があります。
• System.currentTimeMillis()：ミリ秒単位での測定(1 msec = 10−3 sec)
• System.nanoTime()：ナノ秒単位での測定(1 nsec = 10−9 sec)
currentTimeMillis()が現在の時刻に関連したミリ秒単位の値を返すのに対し、nanoTime()は時刻とは無関係な 時間測定のためのナノ秒単位の値を返します。但し、APIドキュメントを読んでみると、必ずしも解像度がナノ秒で あるという保証は無いとあります。とりあえず、プログラムの計測を行うのにミリ秒単位は利用価値が無いでしょうか ら、ナノ秒での測定について見ていきましょう。なお、こうしたプログラムの性能評価のことを、「ベンチマークテス ト」と言います。
ソースコード2.105 TimePrecisionExample.java (時間測定)
package section0220;
public class TimePrecisionExample {
public static void main(String[] args) { final int N = 1000000;
int count = 50;
int x = 0;
for(int k=0; k<count; k++) {
long startTime = System.nanoTime();
for(int i=0; i<N; i++) { x++;
}
long endTime = System.nanoTime();
System.out.printf( "%d nsec%n", (endTime - startTime) );
}
System.out.println( "x = " + x );
} }
上記のプログラムを以下の２種類のマシーンで実行した結果が表2.20.1 です。なお、こうした測定を行う場合は、他 の要因が少しでも少なくなるように、他のアプリを停止したり、ネットから切断して実行しましょう。
• Windows 10 Pro / Intel Core i5-3337U 1.80GHz
• MacOS X 10.11.6/ Intel Core i7 2.20GHzz
結果から読み取れることは何でしょうか？まず、実験自体は毎回同じ処理(変数xに1 をN 回加える繰り返し)を しているはずです。従って、理論上は毎回同じ測定時間になるはずですね。しかし、いずれの場合も、最初の数回は 極端に時間がかかっています。これは、Java がプログラムを開始するに際し、何らかの追加的な仕事を処理とは別に 行っているということですね。Javaは中間言語に翻訳されたclassファイルをインタプリタがJVM内で実行します。
そのとき、クラスの設定、フィールド(変数)の確保等々、最初にいろいろな仕事をしなければいけません。それをや りながらプログラムは実行をしているので、初期の処理は本来の実行速度が測れないのです。
その後、いずれのパソコンでも安定して同じような処理時間(Windowsが0、Macが38)が続きます。処理をやっ ているのですから、0 nsecということはありえませんから、パソコンのタイマーが進む以前に終わってしまったという ことですね。では、WindowsがMacOSより圧倒的に早いのでしょうか？いえ、Windowsの値を見ると、時々 570 くらいの数値が顔を出します。つまり、タイマーは 0 nsecの次(?) に大きな値として570 nsecを測定できるけれど、
その間の値は測定できないのでは(?) と考えられます。同様にMacOSの場合も、似通った値が飛び飛びに現れてい ます。
k 0 1 2 3 4 5 6 7 8 9 10 11
Windows 7842292 6009725 2638235 570 0 6676269 2779070 0 0 0 0 0
MacOS X 2251628 4580460 125 38 38 38 39 38 38 39 38 38
k 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Windows 0 0 0 0 571 0 0 0 570 0 0 0 0 0 0 0 0
MacOS X 38 38 38 38 39 38 38 38 38 26 72 38 39 38 38 38 38
表2.20.1 Javaによる時間測定
表2.20.2では、繰り返し回数N を変えて測定してみました。何と、N を増やすと測定時間0 が現れます。このこ
とは、繰り返し回数を増やすと、何らかの最適化が行われて、実際は繰り返しを行わないという結果になっていると考 えられます。Javaのコンパイラは、単純作業に対して最適化を行うので、それが時間測定の難しさにもなっています。
Java のベンチマークテストについての詳細な説明が、以下のページで解説されていますので、参考にしてみて下さ い。＞「確実なJavaベンチマーク」(https://www.ibm.com/developerworks/jp/java/library/j-benchmark1.html)
n 0 1 2 3 4 5 6 7 8
10 1710 570 0 570 570 570 570 570 0
100 1710 1711 1141 1140 2281 1141 1140 1141 1141
1000 15395 14825 11973 11404 11974 11403 11404 11404 11404
10000 119169 116887 115747 116317 135703 116888 124870 115747 115177
100000 1732785 330135 283951 278249 608385 440181 441322 392286 466980
1000000 7842292 6009725 2638235 570 0 6676269 2779070 0 0
10000000 4146368 6632934 0 7951767 0 0 0 0 0
n 9 10 11 12 13 14 15 16 17 18
10 571 570 570 570 570 570 570 570 570 570
100 1140 5131 1140 2281 1711 1710 2281 1710 1140 1711
1000 11404 11404 10834 11404 13114 19957 19956 20526 19387 19956
10000 115176 115177 132283 49036 43334 46755 852993 46755 48465 41053
100000 433909 741237 80395 0 1579976 684790 436760 477243 476103 367197
1000000 0 0 0 0 0 0 0 571 0 0
10000000 0 570 0 0 570 0 0 0 0 0
表2.20.2 配列の長さを変えて時間測定(Windows)
for(int i=0; i<A.length; i++) { for(int j=0; j<A[i].length; j++) {
System.out.printf( "%3d", A[i][j]);
}
System.out.println();
} } }
できましたか？ここまで良く理解できていれば楽勝かと思うのですが。さて実は、このプログラム、もっと簡単な書き 方ができます。
この部分、追記予定！
問題 2.21.4. 次の各説明文に対し、◯や△に当てはまる単語(カタカナ)や記号を下線部に書きなさい。
1. 改行のような特殊文字を表すために使われるもので、\記号との組み合わせで特殊な文字を表す。それらの文字 列を◯◯◯◯◯シーケンスと呼ぶ。
2. プログラムソースを読みやすくするために、命令文を右に数文字分、字下げする行為を◯◯◯◯◯させると言う。
3. プログラム中にプログラムの説明を書くためのコメント文には3種類あるが、一般に複数行に渡るコメントは、
最初の行を ◯◯ で始め、最後の行を △△ で終わらす。
◯◯= , △△=
4. 例えば、浮動小数点数を整数型変数に代入することは、一般にエラーとなって実行できないが、情報の損失を覚 悟の上で強制的に代入させることができる。その操作を浮動小数点数を整数に◯◯◯◯させると言う。
5. Java言語では、複数の単語を連結して1 つの変数名を作るとき、2 つ目以降の単語の先頭文字だけを大文字に
してつなげる◯◯◯◯形式がよく用いられる。
6. 整数変数aの値を1 増やす単項演算子の++のことを ◯◯◯◯◯◯◯ と言い、前置と後置の2種類がある。
問題 2.21.5. 以下の繰り返しを行うfor文の宣言部 (for(項目1; 項目2; 項目3))をそれぞれ書きなさい。
1. 整数カウンタiを0から100までの偶数のみ昇順で：つまり、i= 0,2,4,· · ·,100 2. 整数カウンタiを5から1000まで5 の倍数で：つまり、i= 5,10,15,20,· · ·,1000
3. 整数カウンタiを1から10000まで、毎回、前回の5 倍で：つまり、i= 1,5,25,125,625,3125
4. 浮動小数点数カウンタxを 0.0 から1.0 まで0.01刻みで：つまり、x= 0.0,0.01,0.02,· · ·,1.0（この場合、
計算誤差でxは1.0に等しくなるとは言えないが）
問題 2.21.6. 以下のようにキーボードから入力された整数値nに対して、次のような一連の操作をするプログラムを 作りなさい。途中で利用する変数名は自由に付けてよい。
1. キーボードからベクトルの要素数nを読み込む。
2. Math.random()を用いてn次元の[0,1)の乱数値による実ベクトルx= (x1, x2,· · ·, xn)を作る。
3. ベクトルの長さ∥x∥を求める。 ∥x∥= Ã
∑n i=1
x2i
4. xと方向が等しく長さ1の実数ベクトルyを作る。 y= x
∥x∥ 5. yの値をコンソールに出力する。
ソースコード2.108 VectorNormalize.java (ベクトルの正規化) package section0221;
import java.util.Scanner;
public class VectorNormalize {
public static void main(String[] args) { // (1)
Scanner scan = new Scanner(System.in);
System.out.println("ベクトルの要素数を入力して：");
int n = scan.nextInt();
// この後に、指示の処理 (2)(3)(4) の内容を書く // (5)
System.out.println( "作成した長さ１のベクトル：");
for(int i=0; i<n; i++) {
System.out.println( "y[" + i + "]=" + y[i] );
} } }
問題 2.21.7. nCm：n個の要素からm個を取り出す組み合わせの数を求めるプログラムを作る。
以下のように n を与えた時、コンソールに nC0, nC1, nC2, . . . , nCn−1, nCn を計算して出力するプログラム
Combination.javaを完成させなさい。なお、出力は(n, m)でnCm を意味するとする。なお、組み合わせ数は大きな
数になりがちなので、long 型整数変数を用いた。
ところで、このプログラムでコケずに動く最大のnは幾つだろう。
ソースコード2.109 Combination.java (組み合わせ数) package section0221;
import java.util.Scanner;
public class Combination {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("n を入力して：");
int n = scan.nextInt();
for(int m=0; m<=n; m++) {
// ここに、nCm を計算して変数 comb に代入する処理を書く long comb =
// 計算された組み合わせ数 comb を出力する
System.out.println( "(" + n + "," + m +")=" + comb );
} } }
問題 2.21.8. 以下の公式は、指数関数exのマクローリン展開です。この公式を用いて、e=e1 を求めて下さい。
ex=
∑∞ n=0
xn n!
n= 0からnを１ずつ増やして 1 0!+1
1!+1
2!+· · ·+1
n!と和を求めていって、ある項を加えてもその前の和と変わらなく なったら（どんどん小さくなる値を加えていくので、最後は数を加えても和の値が変化しなくなります。これを丸め誤差 と言います）、そうしたら新たな項を加えることをやめて、結果を出力します。この繰り返しは何回になるか事前にはわ かりません、つまりfor文での繰り返しには向かないということですね。ちなみに、e= 2.7182818284590452354· · · です。
ソースコード2.110 Maclaurin.java (マクローリン展開によるネイピア数eの計算) package section0221;
public class Maclaurin {
public static void main(String[] args) { double x = 1.0;
// ヒント全くなしで、出来ますかね？
// マクローリン展開を用いて 2.71828... の近似値が // 求められれば、多少の計算のムダなどは目をつぶりましょう }
}
2 年生になるとこうした数値計算をしっかりやりますよ。
問題 2.21.9. 次の関数のx∈[1,3]での定積分の値を求めたいのですが、関数の積分ができない。(^^;)
f(x) = sin(
ecosx−xlogx)
−→
∫ 3 1
f(x)dx そこで、数値積分（もどき）を以下のように行って、定積分の値を求めなさい。