処理速度を計測

前期中間前レポート課題(選択1)

例年であれば、プログラム作成中心のレポート課題をやってもらっているけど、前期中間試験は今回早めに行われるので、プログラム作成か、処理速度のオーダを実際に計測実験のいずれかとする。

現在時間を ミリ秒の精度で求める System.currentTimeMills() を使って、様々なプログラムの処理時間を計測してみよう。ただし、OS によって 100ミリ秒未満はあまり正確に測れない。このため、処理時間は繰り返し処理などを入れることで、10秒程度になるようにすること。また、動作例で示した Paiza.io では、長い処理時間のプログラムは、途中で強制終了させられるので、自分のパソコンにインストールしてある環境で動作させること。また、並列処理しているプログラムの影響を受ける可能性もあることから、他の処理の影響がでないように工夫すること。

様々なプログラムの実行時間を計測してみよう

import java.util.*;

public class Main {
    // 乱数を配列にセット
    public static void array_set_random( int[] array ) {
        Random rnd = new Random() ;
        for( int i = 0 ; i < array.length ; i++ )
            array[ i ] = rnd.nextInt( array.length ) ;
    }
    // 配列を選択法でソート
    public static void array_sort( int[] array ) {
        for( int i = 0 ; i < array.length - 1 ; i++ ) {
            int min = i , j ;
            for( j = i + 1 ; j < array.length ; j++ ) {
                if ( array[ min ] > array[ j ] )
                    min = j ;
            }
            int tmp = array[ i ] ;
            array[ i ] = array[ min ] ;
            array[ min ] = tmp ;
        }
    }
    public static void main(String[] args) throws Exception {
        // 変化させるデータ件数
        int[] data_n = {
            2500 ,
            5000 ,
            7500 ,
            10000
        } ;
        for( int i = 0 ; i < data_n.length ; i++ ) {
            int[] array = new int[ data_n[ i ] ] ;
            // 配列を乱数で埋める時間は測りたくない
            array_set_random( array ) ;
            long start = System.currentTimeMillis() ;
            array_sort( array ) ;
            // ソート結果の表示時間は測りたくない
            //for( int x = 0 ; x < array.length ; x++ )
            //    System.out.print( array[ x ] + " " ) ;
            //System.out.println() ;
            long end   = System.currentTimeMillis() ;
            System.out.println( "Time = " + (end - start) ) ;
        }
    }
}

• データ件数と処理時間の計測(Paiza.io)

プログラムによっては、処理時間が短すぎる場合があるので、下記のように 1000 回ループさせるなどで、一定時間以上の処理となるように工夫すること。

public static int fact( int x ) {
    if ( x == 1 )
        return 1 ;
    else
        return x * fact( x - 1 ) ;
}
public static void main(String[] args) throws Exception {
    int[] data_n = { 2 , 4 , 6 , 8 , 10 } ;
    for( int i = 0 ; i < data_n.length ; i++ ) {
        long start = System.currentTimeMillis() ;
        for( int j = 0 ; j < 1000 ; j++ ) {
            int ans = fact( data_n[ i ] ) ;
        }
        long end = System.currentTimeMillis() ;
        System.out.println( "Time = " + ( end - start ) ) ;
    }
}

レポート内容

データ件数や 引数に与える数によって、処理時間が変化するプログラムを記述し、そのプログラムを N を変化させながら上記のプログラムなどを参考に処理時間を計測する。時間計測には誤差が大きく含まれる可能性があることから、複数回実行して平均をとるなどの工夫もすること。

授業中に示したプログラムなどの計測を行う場合は、ループのプログラムの変化と、別プログラムの再帰の場合の変化の２つについて結果を示すこと。創造工学演習の再帰問題の課題の整数比の直角三角形探索、辺の組み合わせ問題、N Queen、ハノイの塔など、自分で興味のあるテーマを選んだ場合は1つでも良い。

この上で、(1) プログラムリスト, (2) 時間計測にあたり工夫したこと, (3) 実際の実行結果のグラフ, (4) その結果の考察した結果をレポートにまとめて提出せよ。