Почему нет Dictionary.TrimExcess ()? - PullRequest
       8

Почему нет Dictionary.TrimExcess ()?

10 голосов
/ 26 октября 2009

В .NET есть конструктор для Dictionary<TKey, TValue>, который принимает один параметр, int capacity. Это то же самое, что и во многих других коллекциях, таких как List<T>, Queue<T> и Stack<T>; кроме того, согласно документации MSDN :

Емкость словаря - это количество элементов, которые можно добавить в словарь, прежде чем потребуется изменение размера. Когда элементы добавляются в словарь, емкость автоматически увеличивается по мере необходимости путем перераспределения внутреннего массива.

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

Почему Dictionary<TKey, TValue> не имеет такой же TrimExcess метод?

(Отказ от ответственности: я хорошо знаком с ответом «функции не существуют по умолчанию»; я думаю, что я в основном просто задаюсь вопросом, есть ли конкретная причина, по которой TrimExcess для Dictionary не имеет смысла, или почему это будет значительно сложнее реализовать, чем для более простых коллекций, таких как List.)

Ответы [ 5 ]

6 голосов
/ 26 октября 2009

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

5 голосов
/ 26 октября 2009

Это отчасти предположение: словарь «упорядочен» как хеш-таблица.Емкость, которая зарезервирована, это не просто набор адресов свободной памяти поверх вашего словаря.Вместо этого он состоит из пустой комнаты по всему словарю.Это сделано для того, чтобы сделать добавление / перемещение / удаление и т.д. очень эффективным.Если бы у вас был метод TrimExcess для словаря, весь словарь должен был бы скопировать все в новое место без каких-либо пробелов между элементами.

На самом деле: пробелы должны остаться, иначе преимущество хеш-таблицы становитсяvoid, обрезка (TrimExcess), если она реализована, должна обрезать только внутренние ValueCollection.

Обновление: расширено и изменено неправильно выбранные слова
Обновление: команда BCL говорит, что TrimExcess для словарей "может быть полезен" .
Обновление: запрос функции разрешен как Не будет исправлено :«К сожалению, мы не сможем добраться до этого в следующем выпуске .NET, поэтому я решаю это как не исправить».

4 голосов
/ 26 октября 2009

В MSDN словарь реализован в виде хэш-таблицы. Если вы урежете избыток, вам придется придумать алгоритм, который все еще обеспечивает время поиска, близкое к O (1), в том, что фактически будет случайным образом отсортированным списком.

1 голос
/ 23 апреля 2019

К 2019 году .Net Standard 2.1+ и .Net Core 2.1+ реализуют Dictionary<TKey, TValue>.TrimExcess():

см .: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.trimexcess?view=netstandard-2.1

.Net Framework не реализует его ни в одной версии.

1 голос
/ 18 апреля 2014

На самом деле я был тем, кто попросил Microsoft внедрить TrimExcess. Я уже представил более одной статьи, которая касается словарей, и во всех случаях я реализовал TrimExcess. Фактически, Resize, используемый, когда сегменты слишком малы, может быть вызван при увеличении или уменьшении размера блоков.

Сегодня я только что опубликовал еще одну статью, это реализация словаря на C ++, которая поддерживает TrimExcess: http://www.codeproject.com/Articles/761040/A-NET-like-Dictionary-in-Cplusplus

Другая реализация (.NET) может быть найдена в этой статье: http://www.codeproject.com/Articles/548406/Dictionary-plus-Locking-versus-ConcurrentDictionar

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...