Следует ли предпочесть ImmutableDictionary или ImmutableSortedDictionary?

Я слышал, что коллекции .NET System.Collections.Immutable реализованы в виде сбалансированных двоичных деревьев, чтобы удовлетворить их ограничениям неизменяемости, даже коллекции, которые традиционно моделируют хеш-таблицы, такие как Dictionary, используя интегральное значение GetHashCode как ключ сортировки.Следует ли предпочесть ImmutableDictionary или ImmutableSortedDictionary?

Если у меня есть тип, для которого он является дешевым, чтобы создать хэш-код, и который является дешевым для сравнения (например string или int), и я не заботиться о отсортированных-Несс моей коллекции, будет имеет смысл предпочесть ImmutableSortedDictionary, потому что базовая структура данных сортируется в любом случае?

источник

2015-04-08 Billy ONeal

* Если у меня есть тип, для которого дешево создавать хеш-код, и для которого дешево сравнивать (например, string или int), и я не забочусь о сортировке моей коллекции. * Я думаю, вы ответили сами. Будь проще. С другой точки зрения программистов, я бы смутился, чтобы прочитать код и узнать, что сортировка сортированного словаря бесполезна, и я задаюсь вопросом, почему это было использовано в первую очередь. –

@Yuval: Учитывая, что структура данных является деревом AVL, IMHO имитирует интерфейс хеш-таблицы сверху, менее прост. –

В какой структуре данных вы говорите? –

На мой взгляд, правильный ответ на такие вопросы чаще всего «кто заботится»?

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

источник

2015-04-08 18:49:21 Colin

1. Рассмотрите на мгновение, что приложение, над которым я работаю, тратит 40%% своего времени на то, чтобы делать слова в словарях; что не является необоснованным. 2. Существует множество «эмпирических правил» производительности, которые демонстрируют практические преимущества, хотя их трудно локализовать в профилировщике; например 'x.Count' лучше, чем' x.Any() 'лучше, чем' x.Count() '. 3. Это не ответ и не отвечает на вопрос. –

@BillyIneal - Ваш пример надуман, и, хотя вам может не понравиться мой ответ, он будет правильным в огромном, подавляющем большинстве случаев. Я бы согласился на то, что вы никогда не закодируете программу реального мира, где вы увидите ЛЮБЫЕ заметные преимущества в производительности (что означает более 1/10 секунды времени обработки) с одним над другим. Преждевременная оптимизация - это антипаттерн, и большинство проблем с производительностью являются алгоритмическими. Этот вопрос является академическим, а не практическим. Сожалею. – Colin

Я говорю, как программист высокого уровня, заметьте.Это может быть иначе, если вы работаете с драйверами устройств или что-то еще на низкоуровневой бахроме. Во всяком случае, еще одна точка разногласий заключается в том, что профилирование (возможно, незначительных) результатов работы не должно быть сложным, и лучше полагаться на реальные данные, а не на спекуляции, не подкрепленные доказательствами. – Colin

Это не должно иметь значения. Временные сложности из this blog post показывают, что в то время как вы получаете лучшую производительность от Dictionary.Add чем SortedDictionary.Add (O(1) против O(log n)) как ImmutableDictionary и ImmutableSortedDictionary имеют временную сложность O(log n)

источник

2015-04-08 18:51:47

1. Ну, меня больше интересует практическое поведение; Например, 'ImmutableArray' намного быстрее итерации, чем' ImmutableList', например; но имеет ту же сложность. 2. Конечно, ImmutableDictionary возвращается к линейному поведению в случае, когда значения «GetHashCode» одинаковы ... –

@BillyONeal Единственное, что неясно в статье, это худший случай «ImmuteableSortedDictionary». Я не уверен, это 'O (n log n)' или 'O (n)'. –

Хэш на основе сбора должна быть значительно быстрее на .NET, потому что:

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

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

источник

2015-04-14 01:15:01

Ответ да, это может иметь смысл предпочесть ImmutableSortedDictionary в определенных условиях, например, с Int32 ключами.

В моем случае, с Int32 ключами Я узнал, что ImmutableSortedDictionary был лучшим выбором.

я запустить небольшой тест, используя 1 миллион пунктов:

Вставка 1,000,000 элементы в порядке возрастания ключевых
Update 1000000 случайных элементов
сканирования 1,000,000 пунктов, т.е.перебора один раз по каждому элементу коллекции
Read 1,000,000 случайные элементы
Удалить 1,000,000 случайные элементы

ImmutableDictionary < ИНТ приемлю >

Insert: 2499 ms 
Update: 7275 ms 
Scan: 385 ms 
Read: 881 ms 
Delete: 5037 ms

ImmutableSortedDictionary < Int, объект >

Insert: 1808 ms 
Update: 4928 ms 
Scan: 246 ms 
Read: 732 ms 
Delete: 3522 ms

ImmutableSortedDictionary немного быстрее, чем ImmutableDictionary по всем операциям. Обратите внимание, что вставка выполняется по одному элементу за раз в порядке возрастания ключа (потому что это соответствует моему конкретному варианту использования).

Однако вы также должны рассмотреть возможность использования измененной коллекции с некоторой блокировкой. Запись на изменчивый Dictionary<int, object> на один порядок выше.

источник

2015-06-04 08:21:32 ZunTzu

Следует ли предпочесть ImmutableDictionary или ImmutableSortedDictionary?

ответ

Смежные вопросы