Производительность: SortedDictionary против SortedSet

Question

Должен ли я поддерживать
1.) SortedDictionary (двойной, STRUCT)
2.) или просто обычный словарь (двойной, STRUCT) плюс SortedSet (двойной)?

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

Я чувствую, что время работает мудро - Оба такие же, SortedSet<double> просто делает дополнительную работу. Можете вы, ребята, подтвердить?

Часть, о которой я не знаю, поддерживает ли сортировка, SortedDictionary перемещается только по клавишам (удваивает) или обе клавиши и значения. В последнем случае 2.) превысит 1.), не так ли?

Кроме того, неясно, как SortedDictionary внутренне реализован. Sortedset - это красно-черное дерево, которое является проверенным исполнителем.

Answer 1

SortedDictionary<K, V> - это путь. Не только потому, что это правильная структура для вашего использования, но даже с точки зрения производительности и обслуживания, это будет только лучше.

---

Я просто хочу быстро вставки

1. Во втором случае вам придется вставить как в Dictionary<K, V>, а также SortedSet<K>. Это две вставки (одна O (1) и другая O (log n)). Я ожидал бы, что это будет медленнее, чем одиночная вставка в SortedDictionary<K, V> (O (log n)).

2. SortedDictionary<K, V> внутренне реализована как SortedSet<KeyValuePair<K, V>> с сравнение делается на Key части KeyValuePair<K, V>. Поэтому, если вас устраивает производительность SortedSet<T>, тогда не стоит оглядываться назад.

в SortedDictionary движется вокруг только ключи (двойные), или и ключи и значения

Это ясно микро-оптимизации. Это всего лишь вопрос перемещения нескольких лишних байтов, и это вряд ли имеет значение.

его непонятно, как отсортированныйdictionary внутренне реализован. Сортировка - это красно-черное дерево, которое является проверенным исполнителем.

SortedDictionary<K, V> внутренне реализована как SortedSet<KeyValuePair<K, V>> с сравнение делается на Key части KeyValuePair<K, V>. It is a red-black tree. Так что это доказанный исполнитель тоже ...

---

Также отметим, что SortedDictionary<K, V> будет легче на память, а также приводит к более быстрому удалению, а также перечисление. Гибридный подход даст вам быстрый поиск, но он должен будет выполнить поиск каждого ключа в словаре для соответствующей части значения во время перечисления. Это будет медленнее.

---

Alert: я не читаю ваши комментарии, когда я писал выше !!

структура Я использую это своего рода тяжелый ~ 100 байт

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

Я сделал быстрый и грязный Dictionary<K, V>/SortedSet<K> гибридной конструкции и протестировал его.

• Действительно, это было быстрее для 100-байтовой структуры, когда дело дошло до ввода (более чем в два раза быстрее). Конечно, существует штраф (кто создал бы 100-байтовую структуру?).

• Когда я изменил его на класс, они оба дали одинаковые показатели вставки.

• Когда я уменьшил размер структуры, даже тогда производительность вставки была сопоставимой.

Таким образом, мое предложение переключается на класс и использует SortedDictionary<K, V>. Если вы застряли со структурой, то Dictionary<K, V>/SortedSet<K> будет лучше. Хорошее q и +1.