Tagebuch ONLINE

[] 今月のもくじへ [▲▲] Tagebuch ONLINE Top へ

[0223] 2002 年 09 月 07 日 曜日
スキーレンタル問題でのLFU、LRU

【午前】睡眠。【午後】さくら。利家とまつ。学校へ。レポート。日記ページ更新。自宅到着目前で雨に降られる。

手違いで消去してしまいました。記憶を頼りに復旧を試みます。

きょうは計算アルゴリズム論の今井先生のほうの課題をやっておりましたが、第 1 問のオンラインアルゴリズムに関する問題は、問題文の解釈のしようによっては「スキーレンタル問題」に対するオンラインアルゴリズムとして LFU と LRU があるというおおよそ先生が期待していないような問題になってしまいそうです。そこで、LFU や LRU をうまく適用できるような「スキーレンタル問題」について考えてみることにしましょう。

ある日木村さんは税務署勤務を辞して実家の富山でスキー板のレンタル屋をはじめることにしました。

ところがです。店舗を確保することはできたのですが、店頭には k 個のスキー板しか置くことができません。残りのスキー板は奥の倉庫においておくことにしました。もちろんお客さんには全商品のカタログを見せ、すべての商品の中からスキー板を選んでもらうようにしたいわけですが、もしお客さんが店頭においてないスキー板を借りたいとほざいたおっしゃったときには、面倒くさいですが倉庫からそのスキー板をもってきて店頭に並べます。しかし、このとき店頭にディスプレイされていたスキー板からどれかを選んで倉庫に戻さなければなりません。

商品を入れ替える際には、のちのち何度も倉庫まで足を運ぶ羽目に陥らないよう倉庫にしまうスキー板をセレクトしたいところです。過去のレンタルの記録だけをもとにした場合、どのようなアルゴリズムにしたがってスキー板の入れ替えをおこなうと効率がよくなるでしょうか?

……と、このような問題を考えてみました。問題の前提として、(1) 客のスキー板の嗜好には局所性が認められる。(2) スキー板は壊れない。 そして、(3) 板を借りたお客さんは、次のお客さんが店にやってくるまでには板を店に返却しないとならない。 があげられます。(3) なんかそうとう無理がありますね。

この問題に対する最適オフラインアルゴリズムは、「しばらく貸し出されることのないスキー板を倉庫にしまう」です。あんまり議論の余地はないと思います。

対して、LFU・LRU はオンラインアルゴリズムで、それぞれ「過去にもっとも貸し出された頻度の少ないスキー板を倉庫に」「もっとも長い期間貸し出されていないスキー板を倉庫に」という戦略でお蔵入りの板を決めていくことになります。LFU だと新品のスキー板をいくつか導入したときに、お客さんのリクエストがあるたびに新品のスキー板が店頭と倉庫を行き来してしまう、というシチュエーションが考えられますね。

もちろんこのハナシはフィクションです。実在の人物、企業、官公庁などとはなんら関係ありません。課題として出ているスキーレンタル問題はこんなんやないので間違ってもレポートに書いたりしないでくださいね>これからレポートを作成される方々。

前後の記事