4
  • 位置
    • 断片化されたヒープ (ノードごとに malloc) - いくつかの異なる方法で非効率的 (遅い割り当て、遅いアクセス、メモリの断片化)
    • ヒープ内、1 つの大きなチャンク内 - 再割り当てが必要な場合、データ構造によって得られるすべての柔軟性が失われます
    • スタック内 - スタックのサイズはかなり制限される傾向があるため、スタックに大きな構造体を割り当てることはまったく推奨されません

彼らの大きな利点である挿入 O(1) は、断片化されたメモリの環境や、さらに 10 バイトを取得するためにメモリ アロケータを何千回も呼び出す環境では、あまり役に立たないように見えます。

明確にするために編集：
この質問はインタビューで尋ねられました。これは職場での質問ではないため、少数の標準アルゴリズムのセットから正しい決定に盲目的につまずくことを期待する通常のヒューリスティックスは適用できません。

既存の回答とコメントでは、「malloc はそれほど遅くない」、「malloc は断片化と部分的に戦う」と述べています。別のデータ構造、たとえば C++ ベクトルの C ポート (つまり、十分なサイズのシーケンシャル メモリを割り当て、データが拡張する場合は 2 倍のチャンクに再割り当てする) を使用すると、すべての問題が解決されますが、高速性が失われます。挿入/削除。リンクされたリスト (どこに割り当てられていますか?) がベクトルよりもはるかに優れているシナリオはありますか?

4

5 に答える 5

4

標準のアロケーターが特殊な 10 バイトの割り当てを効率的に処理しないことが心配な場合は、標準の ( malloc()) アロケーターから大量のメモリを取得し、小さな項目を効率的に分配するカスタム アロケーターを作成します。最初の大きなチャンクでメモリが不足した場合は、再割り当てしないでください。新しい（余分な）大きなチャンクを割り当て、そこから割り当てる必要があります。解放されたメモリの処理方法を決定できます。リストでの処理の最後にすべての大きなチャンクを解放するまで、単に解放を無視することができます。または、大きなチャンクで解放されたメモリを追跡することで、人生を複雑にすることができます. これにより、全体としてメモリ使用量が削減されますが、最初の書き込みはより複雑になります。

一方で、時期尚早の最適化のリスクに注意する必要があります。パフォーマンス ヒットを測定しましたか? あなたの最近の質問について私が見たものを考えると、おそらく使用に固執しmalloc()、独自のアロケーターを作成しようとしないでください (まだ)。

于 2013-04-30T06:01:37.433 に答える
0

メモリ割り当て戦略は、メモリの断片化、何千ものシステムコールなどによって異なる可能性があります。これが、まさに O が使用される理由です! ;-)

于 2013-04-30T06:36:22.163 に答える