最適適合のための空き領域管理
出典: 平成31年度 春期 応用情報技術者試験 午前 問5 (IPA)
要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合 (best-fit) アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものはどれか。
- ア 空き領域のアドレスをキーとする 2 分探索木
- イ 空き領域の大きさが小さい順の片方向連結リスト
- ウ 空き領域の大きさをキーとする 2 分探索木
- エ アドレスに対応したビットマップ
正解と解説を見る
正解: ウ
- ア: アドレスをキーにしても大きさでは探索できず、全体を調べる必要があります。
- イ: 大きさ順に並んでいても、連結リストは先頭から順にたどるので平均 O(n) かかります。
- ウ: 大きさをキーにした 2 分探索木なら、要求量以上で最小の領域を O(log n) で見つけられるので正しい答えです。
- エ: ビットマップは空きの位置は分かりますが、大きさで探すには全体を走査する必要があります。
ポイント
- 最適適合では「要求量以上で最小の空き領域」を探します。つまり 大きさ で探索します。
- 大きさをキーとする 2 分探索木 なら、平均 O(log n) で目的の領域を見つけられます。
- 大きさ順の連結リストは先頭から順にたどるので、平均 O(n) かかります。