pool - データ構造のリソース プール

Question

stack、などの基本的なデータ構造を実装するqueues場合linked list。メモリを一括して動的に割り当てることによって (ノードの) リソース プールを作成する必要がありますか、それともノードが必要になるたびにメモリを個別に割り当てる必要がありますか?

Answer 1

これは完全にあなたの目標に依存します。デフォルトでは (つまり、本当に別のことをする必要がない限り)、次のノードごとに通常の割り当てを行うだけです。

ノードを割り当てるだけと比較したメモリプール:

• 割り当てを高速化します。基になる割り当てメカニズムによっては、大幅に高速になる場合があります。

• アロケータによっては問題にならない場合もありますが、通常はメモリの断片化が少なくなります。

• 主な欠点: 予約されているが使用されていないノードでメモリが浪費されます。これは、インスタンスを 2 つだけ持つのではなく、データ構造を無差別に (たとえば、数千のインスタンス) 使用する場合に非常に重要です。

欠点があるため、メモリ プールは一般的な状況には適していません。

C++ では、すべての標準コンテナーにallocatorテンプレート パラメーターがあります。

Answer 2

これは基本的な時間対スペースのトレードオフです。あなたにとってより重要なものに基づいて選択してください：

事前にプールを割り当てると、ランタイム要素の挿入は、平均して速度が最適化されます。つまり、一定時間、つまり O(1) になります。「平均」とは、線形時間 O(n) である最大値に達してプールを拡張する必要があるものを除いて、ほとんどの挿入が一定時間になることを意味します。また、プール全体を使用しないことになると、メモリを浪費するリスクもあります。

すべての新しいノードのリアルタイム割り当てを行う場合、常に一定時間の挿入がありますが、この場合、一定時間は上記の一定時間より少し長くなります。メモリ ロケーションを割り当てますが、最初にメモリ ロケーションを割り当てる必要もあります。また、この方法では、事前にメモリ ロケーションを予約することにより、メモリを無駄にしません。

ほとんどの状況では、アプリケーションが極端な平均速度を必要とするか、膨大な数の挿入を行う場合を除いて、プールされたアプローチを使用する理由がわかりません。