Начальная вместимость типов коллекций, например Словарь, Список

Question

Некоторые типы коллекций в .Net имеют необязательный параметр конструктора «Начальная емкость». Например:

Dictionary<string, string> something = new Dictionary<string,string>(20);

List<string> anything = new List<string>(50);

Не получается найти начальную емкость по умолчанию для этих объектов в MSDN.

Если я знаю, что я буду хранить только 12 или около того элементов в словаре, разве не имеет смысла устанавливать начальную емкость примерно на 20?

Я рассуждаю так: предположим, что емкость растет, как и для StringBuilder, который удваивается при каждом обращении к емкости, и каждое перераспределение обходится дорого, почему бы не установить заранее размер, который, как вам известно, будет содержать ваши данные с дополнительной комнатой на всякий случай? Если начальная емкость равна 100, и я знаю, что мне понадобится всего дюжина или около того, кажется, что остальная часть этой памяти выделена впустую.

Answer 1

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

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

Тем не менее, вы можете определить значения по умолчанию, используя Reflector. Например, в .NET 4.0 (и, возможно, также в предыдущих версиях),

• a Список инициализируется с емкостью 0. Когда добавляется первый элемент, он повторно инициализируется до емкости 4. Впоследствии, когда емкость достигается, емкость удваивается.

• Словарь также инициализируется с емкостью 0. Но он использует совершенно другой алгоритм для увеличения емкости: он всегда увеличивает емкость до простых чисел.

Answer 2

Если вы знаете размер, то сообщите это; небольшая оптимизация в большинстве «маленьких» случаев, но полезная для больших коллекций. Я бы в основном волновался по этому поводу, если я добавляю «приличное» количество данных, поскольку тогда можно избежать необходимости выделять, копировать и собирать несколько массивов.

В большинстве коллекций действительно используется стратегия удвоения.

Answer 3

При проверке источника емкость по умолчанию для List<T> и Dictionary<TKey, TValue> равна 0.

Answer 4

Еще одна проблема с ConcurrentDictionary (в настоящее время) и использованием его конструктора для установки начального размера заключается в том, что его производительность, как представляется, ограничена.

Например, вот пример кода и тесты Я попробовал.

Я запустил код на моей машине и получил похожие результаты.

То есть, когда указан начальный размер, он ничего не делает для увеличения скорости ConcurrentDictionary при добавлении объектов. Технически, я думаю, что должно , потому что не требуется времени или ресурсов, чтобы изменить свой размер.

Да, он может работать не так быстро, как обычный словарь, но я все же ожидал бы, что ConcurrentDictionary с его начальным установленным размером будет иметь согласованную, более высокую производительность, чем ConcurrentDictionary, у которого не установлен начальный размер, особенно если заранее знает количество предметов, которые будут добавлены к нему.

Так что мораль этой истории - установление начального размера не всегда гарантирует улучшение производительности.