断片化されたヒープにxバイトのメモリを割り当てるには、malloc（）を使用することを検討してください。ヒープには、xバイトより大きなサイズの複数の連続した場所があるとします。mallocの最高ヒューリスティック
次の中から場所を選択するのは、ヒープリストで最も効果的です。
私の直感は、xバイトよりも小さい最小の場所です。私は実際にどちらが最善であるかわからない。
いいえ、これは割り当て問題ではありません。私はこれをHow do malloc() and free() work?と読んでいたが、これは良い質問のように思える。
異なるサイズの割り当てが混在する一般的なヒープでは、2つのうちの2つは、割り当て可能な最小のブロックに配置します（割り当てることができる最大のブロックのサイズを減らさないために必要がある）。
ヒープを実装する他の方法もありますが、この問題の関連性は低くなります（Doug Leaの一般的なdlmalloc - スピードを改善し、全体的な断片化を減らすために同様のサイズのブロックをプールします）。
常に、アプリケーションがメモリ割り当てを実行する方法に最も適したソリューションがあります。アプリケーションパターンを事前に知っているなら、サイズとスピードの両方でジェネリックヒープを打つことができるはずです。
最小の場所を選択することをお勧めします。将来のmallocリクエストについて考えてみてください。あなたは彼らが何であるかを知らず、できるだけ多くの要求を満足させたいと思っています。したがって、あなたのニーズに正確に合った場所を見つける方が良いでしょう。そのため、将来的にはより大きな要求が満足されるようになります。つまり、最小の場所を選択すると、断片化が軽減されます。
それも私の直感です。しかし、最善の適合は実際にうまくいくのですか？リクエストパターンにも左右されます。私はこれらの発見的方法を評価する方法を知らない。 –
リストされている経験則は、それぞれベストフィットアルゴリズムとワーストフィットアルゴリズムで使用されます。また、First Fitアルゴリズムもあります。これは、見つかった最初のスペースを単に取るだけのアルゴリズムです。これは、ベストフィットとほぼ同じくらい速く、はるかに速いです。
それは面白いです。 First fitはBest fitと同じくらい良いと主張しているリソースを教えてください。 –
このペーパーは、First Fitの時間*メモリが通常Best Fitよりも優れていることを示しています。 http://portal.acm.org/citation.cfm?id=360949 –
どちらかと言えば、他の人よりも優れていれば、どちらも「発見的」であるとは限りません。 「ヒューリスティック」と呼ばれるものを使用することの全ポイントは、あなたが何が最良であるかを簡単に判断できないことです。あなたは、限られた情報やあなたの心を素早く補う必要から**推測**しています。 –
良い点。説明でそれを修正します。 –
@Karlしかし、ヒューリスティックは良くなりヒューリスティックは悪くなります。チェスのゲームでは、一般に、次の動きで女王を攻撃することは、おそらくポーンを攻撃するよりも優れたヒューリスティックです。しかし、非常に特殊なケースでは、ポーンを攻撃することは、あなたにチェックをもたらすものです。 –