49

new、mallocなどを使用した動的メモリ割り当ての時間計算量は? 私はメモリ アロケータがどのように実装されているかについてほとんど知りませんが、その答えは実装に依存するということだと思います。したがって、より一般的なケース/実装のいくつかについて回答してください。

編集:最悪の場合、ヒープ割り当てが無制限であると聞いたのを漠然と覚えていますが、平均/典型的なケースに本当に興味があります。

4

5 に答える 5

34

O 記法を扱うときに認識しなければならないことの 1 つは、nが何であるかを理解することがしばしば非常に重要であるということです。nが制御できるものに関連するものである場合(例: 並べ替えたいリスト内の要素の数)、それを詳しく調べるのは理にかなっています。

ほとんどのヒープ実装では、nはマネージャーが処理しているメモリの連続したチャンクの数です。これは明らかに、通常、クライアントの制御下にあるものではありません。クライアントが実際に制御できるのは、必要なメモリのチャンクのサイズだけです。多くの場合、これはアロケータにかかる時間とは関係ありません。大きなnは、小さなnと同じくらい迅速に割り当てられる可能性があります。または、はるかに時間がかかるか、サービス不能になることさえあります。これはすべて、他のクライアントからの以前の割り当てと割り当て解除がどのように行われたかによって、同じn に対して変更される可能性があります。したがって、実際には、ヒープを実装していない限り、適切な答えはそれが非決定論的であるということです.

これが、ハード リアルタイム プログラマーが (起動後に) 動的割り当てを回避しようとする理由です。

于 2008-12-29T18:39:31.333 に答える
26

ヒープ アロケーターの時間の複雑さは、最適化の目的に応じて、システムごとに異なる場合があります。

デスクトップ システムでは、ヒープ アロケーターはおそらく、最近の割り当てのキャッシュ、一般的な割り当てサイズのルックアサイド リスト、特定のサイズ特性を持つメモリ チャンクのビンなど、さまざまな戦略を組み合わせて使用​​し、割り当て時間を短縮するだけでなく、断片化を管理しやすくします。使用されているさまざまな手法の概要については、Doug Lea の malloc 実装に関するメモを参照してください: http://g.oswego.edu/dl/html/malloc.html

より単純なシステムでは、リンクされたリストに保存された空きブロックを使用して、最初に適合または最適に適合する戦略が使用される場合があります (N が空きブロックの数である場合、O(N) 時間になります)。しかし、AVL ツリーなどのより洗練されたストレージ システムを使用すると、O(log N) 時間 ( http://www.oocities.org/wkaras/heapmm/heapmm.html )で空きブロックを見つけることができます。

リアルタイム システムは、O(1) の割り当てコストを持つ TLSF (Two-Level Segregate Fit) のようなヒープ アロケーターを使用する場合があります: http://www.gii.upv.es/tlsf/

于 2008-11-12T06:22:20.073 に答える
4

2 つのコメント:

  • TLSFは、単一のループがないという意味で O(1) です。最大 2Gb まで管理できます。信じがたいことですが、コードを確認してください。

  • 「ベスト フィット」ポリシー (タイトなブロックを見つける) が小さな断片化を達成するのに最も適しているというのは真実ではありません。この主張を証明することは簡単なことではありません。実際、正式には証明されていませんが、その方向に進む多くの証拠があります。（素晴らしい研究テーマ）。

于 2010-12-10T15:08:47.613 に答える
2

典型的なアロケータがどのように機能するかを確認してください。

バンプポインタアロケータはO（1）で機能し、それは小さな「1」です。

分離ストレージアロケータの場合、kバイトの割り当ては、「List（n）から最初のブロックを返す」ことを意味します。ここで、List（n ）は、 n>=kであるnバイトのブロックのリストです。List（n ）が空であることが判明する可能性があるため、次のリスト（List（2n））のブロックを分割して、nバイトの結果の両方のブロックをList（n）に配置する必要があり、この効果が波及する可能性があります利用可能なすべてのサイズを介して、O（ns）の複雑さを実現します。ここで、nsは利用可能なさまざまなサイズの数であり、ns = log（N）ここでNは利用可能な最大のブロックサイズのサイズであるため、それでも小さくなります。ほとんどの場合、特に多数のブロックが割り当てられ、割り当てが解除された後は、複雑さはO（1）です。

于 2008-12-29T17:56:17.130 に答える
2

一般的には O(n) になると思います。ここで、n は使用可能なメモリ ブロックの数です (適切なメモリ ブロックを見つけるには、使用可能なメモリ ブロックをスキャンする必要があるため)。

そうは言っても、サイズの範囲に応じて使用可能なブロックの複数のリストを維持するなど、より高速化できる最適化を見てきました (したがって、1k 未満のブロックは 1 つのリストにあり、1k から 10k のブロックは別のリストにあるなど)。 ）。

ただし、これはまだ O(n) ですが、n が小さいだけです。

無制限のヒープ割り当てがあるというソースを確認したいと思います（それによって、永遠にかかる可能性があることを意味している場合）。

于 2008-11-12T03:31:27.470 に答える