情報構造論・ガイダンス

最初の授業ということで、シラバスなどのガイダンスに交えて、 「プログラムを作る時、何を考慮して書くべきか」という質問をしてみた。 こちらとしては、プログラムでのアルゴリズム評価の観点ということで、 「処理速度」、「使用メモリ量」、「アルゴリズムの複雑さ」という答えを 期待していたんだけれど、プログラムの見易さについての返答ばかり。 「処理速度」という答えがでるまでに随分と時間がかかってしまった。

速度・メモリ・複雑さの3つは、それぞれ速度優先のアルゴリズムは、メモリを大量消費したり、 プログラムが複雑になるなど、一方を優先すれば他方に悪影響のでる トレードオフの関係にあることを解説。 単純検索・2分探索法・全データメモリーマップなどの方法を例に挙げて説明を行う。 プログラム開発では、トレードオフの関係にあるからこそ、 その状況に応じたアルゴリズムを選択(デザイン)できるためにも、 速度・メモリ・複雑さを客観的に評価できる必要性がある。

速度の評価

まず手始めに、N件のデータを配列の中から探す処理で説明。

int  data[ N ] ;
int  key = ??? ;
for( int i = 0 ; i < N ; i++ ) {
    if ( data[ i ] == key )
        break ;
}

このプログラムの実行時間を考えると、最悪のケースでは、式の実行回数は、 i=0 | 1回、i < N | N+1回、i++,if(==) | N回となる。 よって、処理時間は、以下の式で示される。

このプログラムで、1000件で1msecの時間を要した場合、 10000件であれば、何秒かかるか?という問題があった場合、2変数1式であり 通常では処理時間を求めることができない。しかし、 処理速度の見積もりでは、大抵データ件数Nは巨大な場合がほとんどであり、 も、1回の初期化の時間であり、きわめて小さい値が一般的であり、無視できる。 よって、 から、10000件では、10msecという予想時間を求めることができる。

次に、もう少し複雑な例ということで、データの並び替えで最大選択法の プログラムを示し、処理時間を議論する。

int  data[ N ] ;
int  i , j , m , t ;
for( i = 0 ; i < N-1 ; i++ ) {
    m = i ;
    for( j = i+1 ; j < N ; j++ )
        if ( data[ m ] < data[ j ] )
            m = j ;
    t = data[ m ] ;
    data[ m ] = data[ i ] ;
    data[ i ] = t ;
}

内部のjのループの実行回数は、(N-1-i) 回であり、 これを外側iのループで回すため、以下のような式で示される。




 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2011年4月13日 14:44に書いたブログ記事です。

ひとつ前のブログ記事は「プログラミング応用・ガイダンス」です。

次のブログ記事は「参照渡し、コンストラクタ・デストラクタ」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。