ホーム » スタッフ » 斉藤徹 » 配列の処理効率の問題点

2013年5月
« 4月   6月 »
 1234
567891011
12131415161718
19202122232425
262728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

配列の処理効率の問題点

前回のmalloc+freeの理解確認のための課題の2回目ということで、 課題時間とするが、この後の授業進行のために、配列の問題点を説明する。

配列の問題点

現在、mallocの課題で、動的メモリ上に確保した配列上にデータを保存しているが、 基本は以下のような処理だろう。

int data[ 100 ] ;
int size = 0 ;
while( 入力繰り返し判定 ) {
data[ size++ ] = 入力値 ;
}

このプログラムであれば、すでに入力済みの配列にデータ1件を追加する処理は、 配列末尾に入れて、size を増やすだけの一定処理。このため、 データ追加はO(1) となる。
一方、この配列の中から目的データを探すには、登録データがデータ順とデタラメで あれば、配列先頭からループで探すしかない。つまり、データ検索はO(N)となる。

これに比べ、高速な検索方法として紹介した、2分探索法は、比較の度毎に対象が 半分となることから、検索時間はO(log N)となる。
しかしながら、新たにデータを追加する場合は、 挿入すべき場所を探す処理O(log N)と、1件分の場所を確保するために、 以下のようなループでデータをずらす処理となり、その処理時間はO(N) となる。

int pos = データを入れる場所 ;
for( i = N ; i >= pos ; i-- ) {
data[ i + 1 ] = data[ i ] ; // 後ろからずらさなとダメ
}

このことからも、配列は途中にデータを入れる処理が苦手といえる。 また、配列を扱うプログラムでは、データの追加がめったに発生せず、 データを探す処理が中心であれば、2分探索法が効率が良い。 しかし、途中でデータが頻繁に追加され、検索中心でないのであれば、 最初の末尾追加の使い方で良い。