c# - 已知分布的最佳列表容量

Question

如果最终大小的一般分布是已知的，是否存在用于在构造函数中定义 C# 列表容量的最佳算法？

作为一个具体的例子，如果要放置在每个列表中的值的数量的平均值为 500，标准差为 50，并且近似正态分布，就内存消耗而言，列表的最佳初始容量是多少？

Answer 1

留下名单来决定。除非您遇到具体的性能问题，否则我不会费心设置它（只需使用空的构造函数），此时您可能可以先解决其他问题。

过早优化是万恶之源。

Answer 2

这是个人观点，而不是基于研究的，但请记住，List 本身只保存对每个对象的引用，因此最好在为一些过多的引用分配空间时稍微犯错，而不是意外加倍您需要的参考数量。考虑到这一点，额外的两个甚至三个标准偏差（600 或 650）可能不会超出标准。但是，同样，这是我的意见，而不是研究结果。

Answer 3

如果您遵循 3 sigma 规则，http ://en.wikipedia.org/wiki/68-95-99.7_rule指出，如果您考虑 3 个标准偏差，则单个样本将在 99.7% 的时间范围内。

Answer 4

我做了一些研究，似乎这个问题有一个“正确”的答案。

首先，我同意这可能是过早的优化，因此在决定切换之前进行分析是必不可少的。

上图是在 Excel 中生成的，使用正态分布，并使用 10,000 个样本和 10,000 个平均值来测试各种初始列表容量过度使用的空间。如您所见，它有几个有趣的功能。

1. 对于低标准偏差，选择一个糟糕的初始容量可能会浪费最多八倍于最佳选择的空间。
2. 对于相对于平均值的高标准偏差，可能会节省较少的费用。
3. 对应于最低内存浪费的波谷出现在取决于标准偏差的点上。
4. 最好从图表的右半部分选择一个值以避免列表重新分配。
5. 我找不到最小浪费的确切公式，但基于此分析，平均值 + 1.75 x 标准偏差似乎是最佳选择。

警告：YMMV 与其他分布、手段等。

Answer 5

没有正确的答案。这将是内存使用和 CPU 之间的权衡。初始化列表越大，您可能浪费的内存就越多，但您可以节省 CPU，因为以后不必再次调整它的大小。