c# - 既知のディストリビューションのベスト リスト キャパシティ

Question

最終的なサイズの一般的な分布がわかっている場合、コンストラクターで C# リストの容量を定義するための最適なアルゴリズムはありますか?

具体的な例として、各リストに配置する値の数が平均 500、標準偏差が 50 で、ほぼ正規分布に従う場合、メモリ消費の観点からリストの初期容量はどれくらいが最適ですか?

Answer 1

決定するためにリストを残します。具体的なパフォーマンスの問題が発生した場合を除き、わざわざ設定する必要はありません (空のコンストラクターを使用するだけです)。

時期尚早の最適化は諸悪の根源です。

Answer 2

これは研究に基づくものではなく個人的な意見ですが、リスト自体は各オブジェクトへの参照のみを保持することを覚えておいてください。必要な参照の量。それを念頭に置いて、完全に 2 または 3 の標準偏差の追加 (600 または 650) は、おそらく範囲外ではありません。繰り返しますが、これは調査結果ではなく、私の意見です。

Answer 3

少し調べてみたところ、この質問には「正しい」答えがあるようです。

まず第一に、これは時期尚早の最適化である可能性があることに同意します。そのため、切り替えを決定する前にプロファイリングを行うことが不可欠です。

上記のグラフは、10,000 サンプルと 10,000 の平均を使用して、正規分布を使用し、さまざまな初期リスト容量によって過剰に使用されたスペースをテストして、Excel で生成されました。ご覧のとおり、いくつかの興味深い機能があります。

1. 標準偏差が低い場合、不適切な初期容量を選択すると、最良の選択の最大 8 倍のスペースが無駄になる可能性があります。
2. 平均に比べて標準偏差が高い場合、可能な節約額は少なくなります。
3. 最小のメモリ消費量に対応する谷は、標準偏差に依存するポイントで発生します。
4. リストの再割り当てを避けるために、グラフの右半分から値を選択することをお勧めします。
5. 最小の無駄の正確な式は見つかりませんでしたが、この分析に基づくと、平均 + 1.75 x 標準偏差が最良の選択のようです。

警告: 他のディストリビューション、手段などを持つ YMMV。

Answer 4

3 シグマ ルールに従う場合、http://en.wikipedia.org/wiki/68-95-99.7_ruleでは、3 つの標準偏差を考慮すると、単一のサンプルは 99.7% の確率でその範囲内に収まります。

Answer 5

正しい答えはありません。これは、メモリ使用量とCPUの間のトレードオフになります。リストを初期化するサイズが大きいほど、おそらく無駄になるメモリが多くなりますが、後でサイズを変更する必要がないため、CPUを節約できます。