「平成31年春季午前問5」メモリ管理方式

問5

出典:応用情報技術者平成31年春季午前問5

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。
「要求量以上の大きさを持つ空き領域のうちで、最小のものを割り当てる最適適合(best-fit)アルゴリズム」
を用いる場合、
空き領域を管理するためのデータ構造として、
メモリ割当て時の平均処理時間が最も短いものはどれか。

ア:空き領域のアドレスをキーとする2分探索木

イ:空き領域の大きさが小さい順の片方向連結リスト

ウ:空き領域の大きさをキーとする2分探索木

エ:アドレスに対応したビットマップ


解説

問題の内容を簡単に言い換えると以下になる。
1.六畳以上の部屋を探している
2.見つかった部屋の中で一番小さい部屋を教えて!
3.それを見つけるために一番速い方法はこの選択肢の中でどれ?

至極簡単な話である。今回の目的はある一定以上の部屋の広さを求めていて、その中で一番速いのはどれ?
という話なのである。

そんな具合で選択肢を精査していく。

ア:空き領域のアドレスをキーとする2分探索木

「アドレスをキーとする」とある。
アドレスは、所謂、住所みたいなものであり、その住所の広さを指し示している訳ではない。
だから、広さが分からないから、間違っている。

イ:空き領域の大きさが小さい順の片方向連結リスト

片方向連結リストとは、一方通行でしか読み進めることのできないリストのことである。
一本道であり、分かれ道はないリストのことである。

片方向連結リストで目的の部屋に辿り着くことは可能だが、この選択肢には「小さい順」とある。
目的の部屋が物凄く大きい場合は、この選択肢だと非常に時間が掛かってしまうことになる。
何故ならば、目的の部屋が100個ある内の98個目だったら、97個分の時間を浪費してしまうからである。

よって、この回答は保留。もっと速い方法があるかもしれないから。

ウ:空き領域の大きさをキーとする2分探索木

「空き領域の大きさを条件として、2分探索木を利用するよ!」と言っている。

「空き領域の大きさを条件として」とあるので、少なくとも目的の部屋には辿り着けるだろう。

では2分探索木とは何なのか?

簡潔に言うと「目的とする値より大きいか?それとも小さいか?の2択を繰り返していき、答えに辿り着く方法」である。
これだと、一方通行よりも速く辿り着く場合が多い。
無論、選択肢イのケースで、目的の値が3番目とかにあれば、その時は選択肢イの方が速いが、この問題で求められているのは、「平均処理時間が最も短いもの」である。

よって現時点ではウの方が速い。

エ:アドレスに対応したビットマップ

「アドレスに対応した」とあり、選択肢アと同様の理由で却下。

回答

答え:ウ