動的に割り当てられたアレイの理想的な増加率はどれくらいですか?

StackOverflow https://stackoverflow.com/questions/1100311

質問

C++ には std::vector があり、Java には ArrayList があり、他の多くの言語には動的に割り当てられる独自の形式の配列があります。動的配列のスペースがなくなると、より大きな領域に再割り当てされ、古い値が新しい配列にコピーされます。このようなアレイのパフォーマンスの中心となる問題は、アレイのサイズがどれくらいの速さで増大するかということです。常に現在のプッシュに合わせて大きくするだけだと、毎回再割り当てを行うことになります。したがって、配列サイズを 2 倍にするか、たとえば 1.5 倍にするのが合理的です。

理想的な成長因子はあるのでしょうか?2倍？1.5倍？理想とは、数学的に正当化され、パフォーマンスと無駄なメモリのバランスが最も優れていることを意味します。理論的には、アプリケーションにプッシュの潜在的な分散が存在する可能性があることを考えると、これはアプリケーションに多少依存することがわかります。しかし、「通常」最適な値があるのか​​、それとも何らかの厳しい制約内で最適と考えられる値があるのか​​知りたいと思っています。

これに関する論文がどこかにあると聞いたのですが、見つかりませんでした。

役に立ちましたか？

解決

これは完全にユースケースに依存します。あなたの周りのデータをコピー（と配列を再割り当て）無駄な時間や余分なメモリの詳細気にしていますか？どのくらいの配列が続くために起こっていますか？それは長い間の周りにあることを行っていない場合、より大きなバッファを使用しても良いでしょう - ペナルティは短命です。 （古いと古い世代に入る、例えばJavaで）周りにハングアップするために起こっているのならば、それは明らかにペナルティの多くはでています。

のようなものはありません「理想的な成長因子。」それはちょうど依存の理論的の適用をいない、それが依存の間違いのアプリケーションです。

2はかなり一般的な成長因子である - 私はそれが.NETでArrayListとList<T>が使用するものだと確信しています。 JavaでArrayList<T>は1.5を使用します。

編集：エーリッヒが指摘するように、.NETのDictionary<,>は、ハッシュ値がバケット間で合理的に分配することができるように、「ダブルサイズは、次の素数を増やす」を使用します。 （私は最近、素数が実際にハッシュバケットを配布するためのその偉大ではないことを示唆しているドキュメントを見てきた確信しているが、それは別の答えのための引数です。）

他のヒント

少なくとも C++ に適用される場合、なぜ 2 よりも 1.5​​ が好ましいのかを何年も前に読んだことを覚えています (これは、ランタイム システムがオブジェクトを自由に再配置できるマネージ言語にはおそらく当てはまりません)。

その理由は次のとおりです。

  1. 16 バイトの割り当てから始めるとします。
  2. さらに必要な場合は、32 バイトを割り当て、その後 16 バイトを解放します。これにより、メモリに 16 バイトのホールが残ります。
  3. さらに必要な場合は、64 バイトを割り当て、32 バイトを解放します。これにより、48 バイトのホールが残ります (16 と 32 が隣接していた場合)。
  4. さらに必要な場合は、128 バイトを割り当て、64 バイトを解放します。これにより、112 バイトのホールが残ります (以前のすべての割り当てが隣接していると仮定します)。
  5. などなど。

考え方としては、2 倍の拡張では、結果として生じる穴が次の割り当てに再利用できるほど大きくなる時点は存在しないということです。1.5 倍の割り当てを使用すると、代わりに次のようになります。

  1. 16バイトから始めてください。
  2. さらに必要な場合は、24 バイトを割り当て、16 バイトを解放して 16 バイトの穴を残します。
  3. さらに必要な場合は、36 バイトを割り当て、24 バイトを解放して、40 バイトの穴を残します。
  4. さらに必要な場合は、54 バイトを割り当て、36 バイトを解放して、76 バイトの穴を残します。
  5. さらに必要な場合は、81 バイトを割り当て、54 バイトを解放して、130 バイトの穴を残します。
  6. さらに必要な場合は、130 バイトの穴から 122 バイト (切り上げ) を使用します。

理想的には（制限でとしてN →∞）、それはの黄金比ののの：φ= 1.618 ...

実際には、あなたが1.5のように、近くに何かをしたい。

その理由は、あなたがあなたより多くのメモリページを与えるキャッシングを利用してOSを作り、絶えず避けるために、古いメモリブロックを再利用できるようにしたいということです。あなたは、これはののX のに減らし確保するために解決したい式のn の - 1 - 1 = のX の N + 1 - X N 、その溶液近づく X =φ大きいための N

このような質問に答えるときの 1 つのアプローチは、広く使用されているライブラリが少なくともひどいことをしているわけではないという前提の下で、単に「カンニング」して、人気のあるライブラリが何をしているかを調べることです。

簡単に確認してみると、Ruby (1.9.1-p129) は配列に追加するときに 1.5x を使用しているようで、Python (2.6.2) は 1.125x に定数を加えたものを使用しているようです ( Objects/listobject.c):

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

newsize 上記は配列内の要素の数です。よく注意してください newsize に追加されます new_allocated, したがって、ビットシフトと三項演算子を使用した式は、実際には過剰割り当てを計算しているだけです。

あなたはxによって配列のサイズに成長しましょう。ですから、サイズTで始まると仮定します。あなたはそのサイズがT*xされる配列を育てる次回。そして、それはそうでT*x^2とされます。

あなたの目標は、以前に作成されているメモリを再利用できるようにする場合には、

、そして、あなたが割り当て新しいメモリを使用すると、割り当て解除前のメモリの合計よりも小さいことを確認します。したがって、我々はこの不等式を持っています：

T*x^n <= T + T*x + T*x^2 + ... + T*x^(n-2)

私たちは、両側からTを削除することができます。だから我々はこれを取得ます：

x^n <= 1 + x + x^2 + ... + x^(n-2)

非公式に、私たちが言うことnthの割り当てで、我々は我々が以前に割り当て解除メモリを再利用できるように、私たちのすべての以前に割り当てが解除メモリはn番目の割り当てのメモリが必要以上になりたいということです。

たとえば、私たちは第三段階でこれを実行できるようにしたい場合（すなわち、n=3）、その後、私たちは持っている。

x^3 <= 1 + x

この式は全てのxについても同様であるように0 < x <= 1.3（約）

私たちは異なるために得るX N以下で何を参照してください。

n  maximum-x (roughly)

3  1.3

4  1.4

5  1.53

6  1.57

7  1.59

22 1.61

成長因子は2のでx^n > x^(n-2) + ... + x^2 + x + 1 for all x>=2未満でなければならないことに注意してください。

これは実際に依存します。一部の人々は、最適な数を見つけるために、一般的な使用例を分析します。

私は1.5倍の2.0倍ファイxを見てきた、と2のパワーが以前に使用します。

あなたは、配列の長さ以上の分布を持っている、とあなたは時間を無駄に対スペースを無駄にするのが好きどのくらい言うユーティリティ機能を持っている場合、あなたは間違いなく、最適なサイズ変更（初期サイズ）戦略を選択することができます。

各追記が一定時間を償却しているように、

単純な定数倍が使用される理由は、明らかです。しかし、それはあなたが、小さなサイズの異なる（大きい方）の比率を使用することはできませんという意味ではありません。

スカラ座では、現在のサイズを調べる機能を備えた標準ライブラリハッシュテーブルのためloadFactorを上書きすることができます。奇妙なことに、サイズ変更可能な配列はちょうどほとんどの人が実際に何をすべきかである、倍増します。

私は、任意の倍増を知っている（または1.5 * INGの）実際にメモリ不足エラーがキャッチし、その場合には以下を育てる配列ません。あなたが巨大な単一の配列を持っていた場合、あなたがそれをやりたいだろうと思われます。

私はさらにあなたが十分な長さの周りにサイズ変更可能な配列を維持している、とあなたが時間をかけてスペースを好むならば、それは最初にして、ピッタリのサイズ際に（ほとんどの場合）劇的overallocate再割り当てするのは意味がありますことを追加したいですあなたが行われています。

私も私のtheorycrafterの友人が2倍にする要因を設定するときに、これはO（1）であることが証明できることを主張し、ジョンスキートに同意します。

のCPU時間とメモリとの間の比は、各マシン上で異なっており、従って係数はちょうど同じくらい変化するであろう。あなたはラムのギガバイトとマシン、および低速のCPUを持っている場合は、新しい配列に要素をコピーする順番に少ないメモリを持っているかもしれない速いマシン上でより多くの、より高価です。これは、実際のシナリオであなたのすべての助けをdoesntの均一コンピュータ、のために、理論的に答えることができる質問です。

私はそれが古い質問ですけど、誰もが欠けているように見えることを、いくつかのものがあります。

まず、これは2の乗算である：これはのものによって乗算である大き<< 1 を1〜2：int型（float型（サイズ）* x）は、xは数であり、 *浮動小数点演算、およびプロセッサは、floatとint型の間のキャストのための追加の命令を実行する必要があります。言い換えれば、マシンレベルで、倍増が新しいサイズを見つけるために、単一の、非常に高速な命令を取ります。 1と2の間に何かに掛けるとフロート乗算であるので、それはおそらく、少なくとも2倍の周期をとる（乗算、そうでない場合は4ために、フロートに一つの命令をサイズをキャストするために、の少なくともの一つの命令が必要ですあるいは8倍の）、およびint型にキャストバックする一つの命令、およびそれがあなたのプラットフォームではなく、特殊レジスタの使用を必要とする、汎用レジスタ上でフロート演算を実行できることを前提としています。要するに、あなたは、各割り当てのための数学は簡単な左シフトする限り、少なくとも10倍を取ることを期待すべきです。あなたがが再割り当ての際に大量のデータをコピーする場合、これは大きな違いを作るいない可能性があります。

第二に、おそらく大きなキッカー：誰もが解放されているメモリが新たに割り当てられたメモリと自身と隣接し、だけでなく、連続した両方であることを前提としているようです。あなたがしている場合を除き、プールとしてそれを使用して、メモリを自分のすべてを事前に割り当てて、これはほぼ確実にそうではありません。 OS は時折のこれをやってしまうかもしれませんが、ほとんどの時間は、任意の半分のまともなメモリ管理システムは、どこメモリがする小さな穴を見つけることができるようになることを十分な空き領域の断片化があるように起こっていますちょうどフィット。あなたが本当にチャンクをビットに取得したら、連続した作品で終わる可能性が高いが、それはもはや問題ではするために、その後で、あなたの割り当ては、あなたは彼らが十分な頻度で行っていないことを十分に大きいです。要するに、いくつかの理想的な数を使用すると、空きメモリ容量を最も効率的に使用できるようになりますことを想像するのも楽しいですが、現実には、あなたのプログラムが何もOSが存在しない、のように（ベアメタル上で実行されていない限り起こるだろうされていませんそれは）意思決定のすべてを作るの下ます。

質問に対する私の答え？いや、ない理想的な数はありません。誰が本当にさえしようとしないことをアプリケーションので、特定のです。あなたの目標は理想的なメモリ使用量がある場合は、運のうちほとんどです。パフォーマンスのために、あまり頻繁に割り当ては優れているが、我々はそれとちょうど行った場合、我々は、4あるいは8を掛けることができます！ Firefoxがワンショットで1ギガバイトを使用してから8ギガバイトにジャンプする場合は、当然、人々も意味がありませんように、文句をしようとしています。

：ここで私はしかしによって行く親指のいくつかのルールがあります あなたはメモリ使用量を最適化することができない場合は、

、少なくともプロセッササイクルを無駄にしないでください。 2倍することは速い浮動小数点演算を行うよりも少なくとも一桁です。それは大きな違いを生むないかもしれませんが、それは（より頻繁に、より小さな割り当ての際に、特に初期の）少なくともいくつかの違いを行います。

それをoverthinkしないでください。あなただけの既に行われている何かをする方法を把握しようとして4時間を費やしている場合、あなたは自分の時間を無駄にしました。 * 2より良いオプションがあった場合、完全に正直に、それは数十年前にC ++ベクトルクラス（および他の多くの場所）で行われていたであろう。

最後に、あなたはを場合は、実際にが最適化したい、小さなことにくよくよしないでください。今日は、誰もが、彼らは組み込みシステム上で作業している場合を除きおよそ4キロバイトのメモリが、無駄にしている気にしません。あなたが各1メガバイトと10メガバイトの間にあるオブジェクトの1ギガバイトを取得すると、倍増は、おそらくあまりにも多くの（私が意味する、それは100〜千のオブジェクトである）です。あなたが予想される膨張率を推定することができる場合は、特定の時点での線形成長率にそれを平準化することができます。あなたは、毎分約10オブジェクトを期待する場合、ステップごとに5〜10オブジェクトサイズ（分まで、30秒ごとに1回）のPRであるで成長obably細かいます。

それがすべてダウンすることです何が来るのか、以上のことを考えていない、何をすることができます最適化し、あなたがしなければならない場合は、アプリケーション（およびプラットフォーム）にカスタマイズします。

あと2セント

  • ほとんどのコンピュータには仮想メモリがあります。物理メモリでは、プログラムの仮想メモリ内の単一の連続したスペースとして表示されるランダムなページをあらゆる場所に配置できます。間接的な解決はハードウェアによって行われます。32 ビット システムでは仮想メモリの枯渇が問題でしたが、実際にはもう問題ではありません。それで、 穴 もう心配する必要はありません (特殊な環境を除く)。Windows 7 以降、Microsoft も特別な手間をかけずに 64 ビットをサポートしています。@ 2011
  • O(1) は、次のいずれかの条件で到達します。 r > 1 要素。同じ数学的証明はパラメータとして 2 だけでなく機能します。
  • r = 1.5 は次のように計算できます。 old*3/2 したがって、浮動小数点演算は必要ありません。（私は言う /2 コンパイラが適切と判断した場合、生成されたアセンブリ コード内でビット シフトに置き換えられるためです。)
  • MSVCが選んだのは r = 1.5 であるため、比率として 2 を使用しない主要なコンパイラが少なくとも 1 つあります。

誰かが言ったように、2 は 8 よりも良いと感じます。また、2 は 1.1 よりも優れていると感じます。

私の感覚では、1.5 がデフォルトとして適切であると思います。それ以外は、具体的なケースによって異なります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top