ホーム » スタッフ » 斉藤徹 » まともな過去問を使えよ…

2011年6月
« 5月   7月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

まともな過去問を使えよ…

4EIのテスト問題の採点中。 プログラムと効率の理解を確認するために、途中へのデータ挿入の 効率理解ということで、リストであればO(1)であるところを、 配列の途中へのデータ挿入がO(N)かかることの実践ということで、 配列へのデータ挿入を出題している。

しかし、過去の試験問題で似た出題があって、どうも過去問をみて勉強しているようで、 過去の回答者の効率の悪いコードを真似ている人が多い。 さらに、模範解答で説明したネタと一緒になって記憶しているだけの人がいて、 2つのコードを混ぜた回答していて、ハチャメチャ。
# 頭の中で自分のコードをシミュレートしろよ…

途中挿入だから、移動領域の重なったmoveだし、後ろ側からコピーする典型。 データ検索部を抜いて、後ろにシフトする部分のコードは、

// 普通の後方シフト
int idx ; // 挿入場所
int data ;
for( int i = size - 1 ; i >= idx ; i-- )
array[ i + 1 ] = array[ i ] ;
array[ idx ] = data ;
// 効率の悪い後方シフト
for( int i = idx ; i < size ; i++ ) {
int temp = array[ i ] ;
array[ i ] = data ;
data = array[ i ] ;
}
array[ i ] = data ;

確認として、配列サイズ10000件で同一処理を10000回ループで時間を計測。 通常後方シフト=0.281秒、効率の悪いシフト=0.534秒で、1.9倍遅い。 まあ、速度比較の結果としてはそんなもんだろう…