Блог

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

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

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

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

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

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

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

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

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

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

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

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