int[ ] x = { 1, 2, 3, 4, 5 }

配
列
Java における配列
− その２ −
和田＠数理情報科学
このスライドでは
このスライドでは、配列操作を以下の例題で順に説明します
•
•
•
•
•
•
要素の合計・平均
２配列の和
配列のコピー
要素の移動
要素の交換
配列の交換
• 要素の並び替え
• 時間測定
• ファイルへの入出力
• ベクトルと行列の演算
配
列
繰り返しを用いて合計
１次元 int 型配列 array に入っている値を合計する処理は int[ ] array = { 3, 0, -2, 5, 4, 9, -1, 6, 4 } ; int sum = 0 ; for( int i = 0 ; i < array.length ; i++ ) { sum += array[i] ; } System.out.println( “sum = ” + sum ) ;
要素の平均値を求めるには、上記の結果を要素数で割れば良い
ので System.out.println( “average = ” + (double) sum / array.length );
配
列
スマートに
１次元 int 型配列 array に入っている値を合計する処理は int[ ] array = { 3, 0, -2, 5, 4, 9, -1, 6, 4 } ; int sum = 0 ; for( int element : array ) { sum += element ; } System.out.println( “sum = ” + sum ) ;
このような for を拡張 for 文という。配列内の要素を１度ず
つ配列番号の順に全て走査する場合のみ利用できる（i+=2）
のような飛び飛びでの走査はできない
配
列
２配列の和
要素数の等しい２つの配列の要素番号の等しい要素同士を加え
て新たな配列を作るには int[ ] x = { 1, 2, 3, 4, 5 } ; int[ ] y = { 1, 0, -1, 0, 1 } ; int[ ] z = new int[x.length] ; for( int i=0 ; i<x.length ; i++ ) { z[i] = x[i] + y[i] ; }
２つの配列 x と y の長さが異なる場合は、計算できないので、
これらを if( x.length == y.length ) { ・ } のブロックで囲む
のも必要か
配
列
配列のコピー
配列 x の中身を丸ごと別の配列 y にコピーしたい時 int[ ] x = { 1, 2, 3, 4 } ; int[ ] y = x ; ではコピーにならない。次のように１要素ずつコピーする： int[ ] x = { 1, 2, 3, 4 } ; int[ ] y = new int[x.length] ; for( int i = 0 ; i<y.length ; i++ ) { y[i] = x[i] ; } でも、もっとスマートな方法もある
配
列
要素の移動
配列内の要素を１つ後へ移動させるには int[ ] x = { 0, 1, 2, 3, 4, 5 } ; for( int i=x.length-1 ; i>0 ; i- - ) { x[i] = x[i-1] ; }
配列内の要素を１つ前へ移動させるには int[ ] x = { 0, 1, 2, 3, 4, 5 }; for( int i=0 ; i<x.length-1 ; i++ ) { x[i] = x[i+1] ; }
配
列
スマートに
Java には API (Application Programming Interface) と 言う様々な道具の入ったパッケージ群があるので、それを利用
するとスマートにプログラムを作ることができる
配列のコピーは、 System.arraycopy (Object src, int srcPos, Object dst, int dstPos, int count) によって実行できる： src[srcPos] から始まる配列の内容をdst[dstPos] へ count
個分だけコピーする。src と dst は同じ配列でも良く、部分
的に重なっていても実行できる（要素を移動にも使える）
配
列
arraycopy を使って
配列のコピー： int[ ] x = { 0, 1, 2, 3, 4, 5 } ; int[ ] y = new int[x.length] ; System.arraycopy( x, 0, y, 0, y.length ) ;
要素の移動： int[ ] x = { 0, 1, 2, 3, 4, 5 } ; System.arraycopy( x, 1, x, 0, x.length-1 ) ;
配
列
要素の交換
i 番目の要素と j 番目の要素を交換するには int[ ] x = { 1, 2, 3, 4, 5 } ; int i = 1 ; int j = 3 ; int y = x[i] ; x[i] = x[j] ; x[j] = y ; System.out.println( “x[” + i + “] = ” + x[i] + “ x[” + j + “] = ” + x[j] ) ;
配
列
配列の交換
２つの配列の中身を全て交換する方法は、以前のスライドで行っ
た int[ ] x = { 1, 2, 3, 4} ; int[ ] y = { 5, 6, 7, 8} ; int[ ] w = x ; x = y ; y=w;
配
列
要素の並び替え
配列内の要素を昇順（小さい順）や降順（大きい順）に並び替
える（ソートする）には、様々なソート法がある
要素数が少ない配列に対しては、アルゴリズムの簡単な方法を、
要素数が多い配列に対しては、多少複雑でもスピードの速い方
法を選ぶことになる
ソート法の比較アプレット： http://www.sorting-algorithms.com/random-initial-order
配
列
挿入法による並び替え
以下の方法が挿入法 (Insertion sort) と呼ばれる方法： int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; for( int i = 1 ; i < x.length ; i++ ) { int val = x[i] ; int j = i ; while( j > 0 && x[j - 1] > val ) { x[j] = x[j - 1] ; j- - ; } x[j] = val ; } 6, 5, 2, 7, 4, 1, 3
5, 6, 2, 7, 4, 1, 3
2, 5, 6, 7, 4, 1, 3
2, 5, 6, 7, 4, 1, 3
2, 4, 5, 6, 7, 1, 3
1, 2, 4, 5, 6, 7, 3
1, 2, 3, 4, 5, 6, 7
配
列
選択法による並び替え
以下の方法が選択法 (Selection sort) と呼ばれる方法： int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; for( int i = 0 ; i < x.length - 1 ; i++ ) { int min = i ; for( int j = i+1 ; j < x.length ; j++ ) { if( x[j] < x[min] ) { min = j ; } } int y = x[min] ; x[min] = x[i] ; x[i] = y ; }
6, 5, 2, 7, 4, 1, 3
1, 5, 2, 7, 4, 6, 3
1, 2, 5, 7, 4, 6, 3
1, 2, 3, 7, 4, 6, 5
1, 2, 3, 4, 7, 6, 5
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7
配
列
泡立ち法による並び替え
以下の方法が泡立ち法 (Bubble sort) と呼ばれる方法： int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; for( int i = x.length - 1 ; i > 0 ; i- - ) { for( int j = 0 ; j < i ; j++ ) { if( x[j] > x[j+1] ) { int y = x[j] ; x[j] = x[j+1] ; x[j+1] = y ; } } } 6, 5, 2, 7, 4, 1, 3
5, 2, 6, 4, 1, 3, 7
2, 5, 4, 1, 3, 6, 7
2, 4, 1, 3, 5, 6, 7
2, 1, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7
配
列
実行時間の測定
Java では、２種類の時間測定ができます。
ミリ秒(10-3秒)で測るメソッド： long System.currentTimeMillis()
ナノ秒(10-9秒)で測るメソッド： long System.nanoTime()
ミリ秒で表される現在の時間を返すが、値の粒度は基本となるオペレー
ティングシステムによって異なり、単位がより大きくなる場合がある。
多くのオペレーティングシステムでは、時間を 10 ミリ秒の単位で計
測している。
配
列
Shell 法による並び替え
以下の方法が Shell 法 (Shell s sort) と呼ばれる方法： int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; int h = 1 ; for(int i = 1 ; i <= x.length/9 ; i = 3*i + 1) { h = i ; } while( h > 0 ) { for(int i = h ; i < x.length ; i++) { int val = x[i] ; int j = i ; while( j >= h && x[j-h] > val ) { x[j] = x[j - h] ; j -= h ; } x[j] = val ; } h /= 3 ; このデータの場合、h=1 なのだが、
}
h=4 で始めている →
6, 5, 2, 7, 4, 1, 3
4, 5, 2, 7, 6, 1, 3
4, 1, 2, 7, 6, 5, 3
4, 1, 2, 7, 6, 5, 3
1, 4, 2, 7, 6, 5, 3
1, 2, 4, 7, 6, 5, 3
1, 2, 4, 7, 6, 5, 3
1, 2, 4, 6, 7, 5, 3
1, 2, 4, 5, 6, 7, 3
1, 2, 3, 4, 5, 6, 7
配
列
マージソートによる並び換え
配
列
以下の方法がマージソート (Merge sort) と呼ばれる方法： int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; int[ ] temp = new int[x.length] ; for(int intvl = 1; intvl <= x.length; intvl *= 2) { for(int s1 = 0; s1 < x.length; s1 += intvl * 2) { int e1 = Math.min(s1 + intvl, x.length) ; int s2 = e1 ; int e2 = Math.min(s2 + intvl, x.length) ; int i = s1 ; int j = s2 ; int k = s1 ; while( i < e1 && j < e2 ) { if( x[i] < x[j] ) { temp[k++] = x[i++] ; } else { temp[k++] = x[j++] ; } } while( i < e1 ) { temp[k++] = x[i++]; } while( j < e2 ) { temp[k++] = x[j++]; } System.arraycopy( temp, s1, x, s1, k - s1 ); } }
6, 5, 2, 7, 4, 1, 3
5, 6, 2, 7, 4, 1, 3
5, 6, 2, 7, 4, 1, 3
5, 6, 2, 7, 1, 4, 3
5, 6, 2, 7, 1, 4, 3
2, 5, 6, 7, 1, 4, 3
2, 5, 6, 7, 1, 3, 4
1, 2, 3, 4, 5, 6, 7
クイックソートによる並び換え
以下の方法がクイックソート (Quick sort) と呼ばれる方法：
int[ ] x = { 6, 5, 2, 7, 4, 1, 3 } ; int[ ][ ] stack = new int[20][2];
if( l <= r ) {
int y = x[l];
x[l] = x[r];
x[r] = y;
l++; r--;
}
} while(l <= r);
if(left < r ) {
stack[sp][0] = left;
stack[sp][1] = r;
sp++;
}
if( l < right ) {
stack[sp][0] = l;
stack[sp][1] = right;
sp++;
}
int sp = 1;
stack[0][0] = 0;
stack[0][1] = x.length-1;
while( sp > 0 ) {
sp--;
int left = stack[sp][0];
int right = stack[sp][1];
int l = left;
int r = right;
int pivot = x[(left+right)/2];
do {
while( x[l] < pivot ) { l++; }
while( x[r] > pivot ) { r--; } }
6, 5, 2, 7, 4, 1, 3
6, 5, 2, 3, 4, 1, 7
1, 5 2, 3, 4, 6, 7
1, 2, 5, 3, 4, 6, 7
1, 2, 3, 5, 4, 6, 7
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 5, 6, 7
配
列
行列の計算
２つの行列 a と b の和を求める int[ ][ ] a = { {1, 2, 3}, {4, 5, 6} } ; int[ ][ ] b = { {0, 1,-1}, {1,-1, 0} } ; int[ ][ ] c = new int[a.length][a[0].length] ; for(int i = 0; i < c.length; i++) { for(int j = 0; j < c[i].length; j++ ) { c[i][j] = a[i][j] + b[i][j] ; } }
配
列
行列の計算
行列 a を転置する int[ ][ ] a = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} } ; for(int i = 0; i < a.length - 1; i++) { for(int j = i + 1; j < a[i].length; j++) { int b = a[i][j] ; a[i][j] = a[j][i] ; a[j][i] = b ; } }
配
列
行列の計算
２つの行列 a と b の積を求める int[ ][ ] a = { {1, 2, 3}, {4, 5, 6} } ; int[ ][ ] b = { {0, 1}, {-1,1}, {-1, 0} } ; int[ ][ ] c = new int[a.length][b[0].length] ; for(int i = 0; i < c.length; i++) { for(int j = 0; j < c[i].length; j++ ) { c[i][j] = 0; for(int k = 0; k < b.length; k++) { c[i][j] += a[i][k] * b[k][j] ; } } }
配
列
ファイルへの読み書き
ファイルへの書き込み
File file = new File("src/sorting/SortData.txt");
int n = 10000;
// 要素の個数
int max = 100000; // 要素の最大値、最小値は１
// 乱数データのファイル書き込み
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file)));
pw.println(n);
pw.println(max);
for(int i = 0; i < n; i++) {
pw.println( (int)(1 + max*Math.random()) );
}
Eclipse では、パッケージエクスプローラ内のパッケージを右クリックし
pw.close();
「リフレッシュ」を選択すると作られたファイルが表示される
配
列
ファイルへの読み書き
ファイルからの読み込み
File file = new File("src/sorting/SortData.txt");
Scanner scan = new Scanner(file);
int n = scan.nextInt();
int max = scan.nextInt();
int[] x = new int[n];
for(int i = 0; i<x.length; i++) {
x[i] = scan.nextInt();
}
scan.close();
配
列

Download Report