分野 ：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

ベストフィット方式は、メモリ割当てを制御するアルゴリズムの一つで、空きブロックの大きさ順リストを先頭から探索し、最初に見つかった空きブロックを割り当てる方式です。要求に最も適したサイズのブロック（要求されたサイズ以上の中で最も小さい空き領域）を割り当てるため、無駄なメモリの消費を抑えることができます。

ただし、ベストフィットでの割当てを続けた場合、小さな空きブロックがたくさん残ることになり、最終的にはフラグメンテーション（断片化）の問題が発生することがあるため注意を要します。

他の空き領域を割り当てるアルゴリズムの特徴もあわせて説明します。

ファーストフィット方式

メモリの先頭から順に空きブロックを探し、要求されたサイズ以上のブロックを見つけた時点で、そのブロックを割り当てる。探索時間が短くて済む。

ワーストフィット方式

空きブロック全体を検索し、最も大きな空ブロックを割り当てる。断片化を避けられる

• ファーストフィット方式の特徴です。ベストフィット方式ではメモリ全体から最も合致するブロックを割り当てるため、アドレス上下のいずれかに空きブロックが偏ることはありません。
• 正しい。ベストフィット方式は要求サイズを満たす候補の中から最も小さい空きブロックを割り当てます。無駄が少なくて済む一方で、割り当てた残りが小さな空きブロックとして多数残る性質があります。
• ベストフィットは、サイズ順のリストや木構造などで実装されます。目盛り全体から「最小の適合」を見つける必要があるため、一意検索であるハッシュは使用されません。
• ベストフィット方式では、サイズの昇順に並べたリスト構造で空きブロックを管理します。アドレス順リストで領域管理を行うのはファーストフィット方式の特徴です。