ITパスポート 2016年 春期 問82

ファイル置き換え（最長未参照方式）【ITパスポート 解説】

正解の理由

解法ステップ

1. 机には最大4冊を置ける。初めは空とする。
2. 参照（置く／アクセス）された順に机の状態と「最後に参照された時刻」を更新する。
3. 机が満杯（4冊）で5冊目を置く必要があるとき、4冊のうち最も「最後に参照されてから時間が経っている」＝最も古い時刻のファイルを引き出す。

1. A を置く → 机: A(1)
2. B を置く → 机: A(1), B(2)
3. C を置く → 机: A(1), B(2), C(3)
4. D を置く → 机: A(1), B(2), C(3), D(4)（ここで満杯）
5. E を置く → 引き出すのは最も古い A(1) → 机: B(2), C(3), D(4), E(5)
6. C を参照 → C の時刻更新 → 机: B(2), C(6), D(4), E(5)
7. B を参照 → B の時刻更新 → 机: B(7), C(6), D(4), E(5)
8. D を参照 → D の時刻更新 → 机: B(7), C(6), D(8), E(5)
9. F を置く → 引き出すのは最も古い E(5) → 机: B(7), C(6), D(8), F(9) ← ここで最後に引き出されたのは E
10. B を参照 → B の時刻更新 → 最終: B(10), C(6), D(8), F(9)

選択肢別の誤答解説

• ア: A
  • A は最初に引き出されています（ステップ5で最初に外された）。しかし問題は「最後に引き出しにしまうファイル」を問うており、最後に引き出されたのは E なので誤りです。
• イ: B
  • B は複数回参照され、最後まで机上に残ります。最終的にも机上にあるため、引き出しの対象にはなっていません。
• ウ: D
  • D も参照が更新されており、最後に引き出されたのは E のため誤りです。
• エ: E
  • ステップ9で F を置く際に、E が最も長く参照されていなかった（時刻が最も古かった）ため、最後に引き出しにしまわれました。これが正しい理由です。

よくある誤解

1. 「最初に引き出されたものが最後に出る」と勘違いする
   • 人によっては「最初に入れたものが最後に出る＝FIFO（先入れ先出し）」と混同しますが、本問のルールは「最後に参照されてからの時間」で決める LRU 方式です。
2. 「参照＝必ず置く」と解釈する
   • 既に机上にあるファイルを参照しても、置き換え（引き出し）は発生しません。新しいファイルを置くときだけ置換の判断をします。

補足コラム

• LRU（Least Recently Used：最も最近使われていない）
  • キャッシュ（よく使うデータを一時的に置く場所）やページ置換（メモリ管理）でよく使われる戦略です。直感的には「長く使われていないものは今後も使われない可能性が高い」と仮定して置き換えます。
• 似た用語の整理
  • FIFO（First In, First Out：先に入れたものを先に出す）— 入れた順で置換。
  • MRU（Most Recently Used：最も最近使われたものを置換）— 最近使ったものを優先して外す（用途は限定的）。

sequence = ['A','B','C','D','E','C','B','D','F','B']
desk = []
times = {}
t = 0
for x in sequence:
    t += 1
    if x in desk:
        times[x] = t
    else:
        if len(desk) < 4:
            desk.append(x)
            times[x] = t
        else:
            # 引き出すのは最も古い times が小さいもの
            lru = min(desk, key=lambda y: times[y])
            desk.remove(lru)
            print(f"{t}: 引き出した -> {lru}")
            desk.append(x)
            times[x] = t
print("最終desk:", desk)

FAQ