大きいセットから選択すると4組の変化の数を最小限にするアルゴリズム

Question

マシンに4つのスロットがあり、このマシンに特定のアイテムを置くよう指示する命令があります。そこには、私は4つのスロットを持っている、のは、100の項目を言わせて、次のようになり注文がありますされています

4 8 3 3 8 8 8 10 2 7.

私はこの順序を履行できるようにする必要があります最小量のスロットが変化する。例えば、上記の入力で私はマシン上にアイテム番号8を保持する必要がありますので、それを戻してその場所の別のものを拾う必要はありません。

問題は実際に私に届く前に次の注文を確認できないことです。だから、推測ゲームのようなものです。誰でも私はこのプロジェクトを参照して適用できるアルゴリズムを持っていますか？

Answer 1

page replacement algorithmsのようなものを探しているようですね。あなたがまだマシン上にない注文に達すると、それはページミスのようなものです。今必要なもののためのスペースを確保するために、4つのキャッシュされたページの1つを退去させる必要があります。

多くのオプションがあり、すべてがトレードオフです。一般的に、オーダー・ストリームについてもっと知っているか、または合理的に想定できるほど、オーバーヘッドが増えれば増えるほど、不要なページ・ミスを回避できる可能性が高くなります。

を選択する前に、いくつかの質問を考えてみましょう：

1. を注文の指定されたストリーム内では、注文の順番や頻度については想定して喜んで何ですか？均一な分布を仮定し、ランダムな順序は完全に有効です。
2. これらの前提条件は、遭遇したオーダーストリームのほとんどに当てはまる傾向がありますか、いくつかのパターンがありますか？
3. オーダーストリームはどのくらいの期間ですか？

それでも問題が解決しない場合は、LRUとClockのような組み合わせを実装し、実際の注文ストリームに対してテストしてみてください。その精度を評価するために、特定のストリームの理論的な最適なアクションシーケンスと比較することができます。このアルゴリズムはOPTとして知られており、フルストリームにアクセスできる場合にのみ機能します。