Лучшая емкость списка для известного распределения

Question

Существует ли лучший алгоритм для определения емкости списка C # в конструкторе, если известно общее распределение возможных размеров?

В качестве конкретного примера, если число значений должно быть помещено вкаждый список имеет среднее значение 500 и стандартное отклонение 50 с примерно нормальным распределением, какова наилучшая начальная емкость для списка с точки зрения потребления памяти?

Answer 1

Я провел небольшое исследование, и кажется, что есть «правильный» ответ на этот вопрос.

Прежде всего, я согласен, что это может быть преждевременной оптимизацией, поэтому профилирование перед принятием решения о переключенииessential.

График, приведенный выше, был сгенерирован в Excel с использованием нормального распределения и тестирования пространства, израсходованного различными объемами начального списка, с использованием 10 000 выборок и среднего значения 10 000.Как вы можете видеть, у него есть несколько интересных особенностей.

1. При низких стандартных отклонениях выбор плохой начальной емкости может потратить в восемь раз больше места, чем лучший выбор.
2. Для высокогостандартные отклонения относительно среднего значения, возможна меньшая экономия.
3. Падения, соответствующие наименьшим потерям памяти, происходят в точках, зависящих от стандартного отклонения.
4. Лучше выбрать значение изправая половина графика, чтобы избежать перераспределения списков.
5. Я не мог найти точную формулу для минимальных потерь, но среднее значение + 1,75 x стандартное отклонение, кажется, лучший выбор на основе этого анализа.

Предупреждение: YMMV с другими дистрибутивами, средствами и т. Д.

Answer 2

Если вы используете правило трех сигм, http://en.wikipedia.org/wiki/68-95-99.7_rule заявляет, что если вы учитываете 3 стандартных отклонения, один образец будет в этом диапазоне 99,7% времени.

Answer 3

Это личное мнение, а не основанное на исследованиях, но помните, что сам список содержит только ссылку на каждый объект, и поэтому, вероятно, лучше немного ошибиться, выделяя место для несколько слишком много ссылок, вместо того, чтобы случайно удвоить количество ссылок, которые вам нужны. Имея это в виду, полные два или даже три дополнительных стандартных отклонения (600 или 650), вероятно, не совпадают. Но, опять же, это мое мнение, а не результат исследования.

Answer 4

Оставьте список, чтобы решить.Я бы не стал его настраивать (просто используйте пустой конструктор), если только у вас не возникнут конкретные проблемы с производительностью, и в этот момент, вероятно, есть другие вещи, которые вы можете исправить в первую очередь.

Преждевременная оптимизация - корень всех зол.

Answer 5

Там нет правильного ответа.Это будет компромисс между использованием памяти и процессором.Чем больше вы инициализируете список, тем больше памяти вы, вероятно, тратите, но сохраняете свой ЦП, поскольку его не нужно снова изменять в дальнейшем.