Перечисление диапазона ImmutableSortedDictionary по ключу

11

Я читал о С # ImmutableSortedDictionaryв System.Collections.Immutableи думать о том , как применять его в своей программе. Мне очень нравятся C ++ lower_boundи upper_bound(см. Здесь ), и я скорее ожидал увидеть что-то подобное для поиска диапазона. Тем не менее, подобные методы, как ни странно, отсутствуют в документации . Я что-то пропустил? Или MS действительно предоставляет отсортированный словарь без эффективного доступа к отсортированным диапазонам? Это не совсем похоже на то, что можно сделать с одним IEnumerableиз ключей, как, например, метод расширения, поэтому я немного озадачен тем, что не вижу чего-то, предоставленного непосредственно коллекцией.

c# .net algorithm immutability immutable-collections Дж Трана
источник
Эрик Липперт поделился неизменной реализацией дерева AVL еще в 2008 году. Из комментариев я не думаю, что она еще была особенно оптимизирована для скорости или эффективности, но IBinarySearchTree<K,V>ее реализация выглядит ближе к тому, что я ожидал. Интересно, он когда-нибудь возился с этим дальше?
J
ImmutableList<T>Класс также реализован в виде дерева AVL. Из исходного кода :/// The root node of the AVL tree that stores this set.
Теодор Zoulias
Знаете ли вы, имеют ли они в виду, что в списке используется истина AVL для реализации неизменяемости или само дерево AVL является неизменным? (возможно, это не имеет значения, так как они все равно не выставляют дерево).
J
Вот преимущества ImmutableList<T>(подкрепленные деревом AVL) перед ImmutableArray<T>(подкрепленные массивом), согласно документации . Причины использования неизменяемого списка: 1) Обновление данных является распространенным явлением или число элементов не должно быть небольшим. 2) Обновление коллекции более критично для производительности, чем перебор содержимого.
Теодор Зулиас
Это связано с тем, что при добавлении или удалении элемента из большого дерева AVL вы можете получить новое дерево, не разрушая исходное, разделяя большинство узлов и создавая только несколько новых узлов. ( Постоянная структура данных - Деревья )
Теодор Зулиас

Ответы:

9

Вызывает раздражение тот факт, что доступные встроенные коллекции не предлагают полный набор функций (например, SortedDictionaryотсутствие BinarySearchметода), что вынуждает нас искать сторонние решения (например, библиотеку C5). ).

В вашем случае вместо a ImmutableSortedDictionaryвы, вероятно, могли бы использовать a ImmutableSortedSet, встраивая значения в ключи и используя соответствующий компаратор. По крайней мере, API этого класса содержит свойства Minи Max.

Теодор Зулиас
источник
2
Как примечание, другой неизменный класс ImmutableList<T>, реализован внутри как дерево . Так что это в 10 раз медленнее и выделяет в 12 раз больше памяти, чем a List<T>. Используйте ImmutableArray<T>вместо этого.
Теодор Zoulias
1
Хе-хе, я уже использую C5, но смотрю, чтобы увидеть, что было доступно для неизменяемых коллекций (помимо снимков). Спасибо! Я собираюсь оставить надежду, что кто-то еще решил это в той или иной форме или форме, но я буду иметь в видуImmutableSortedSet
J
@TheodorZoulias, какой смысл иметь метод BinarySearch в SortedDictionary, когда метод TryGetValue работает в log (N)? смотрите здесь
Георгий Чхиквадзе
2
@GiorgiChkhikvadze BinarySearch может дать вам следующий элемент, который больше, чем искомый элемент, в случае, если точное совпадение не найдено.
Теодор Зулиас
1
@GiorgiChkhikvadze Вероятно, самое большое отличие здесь состоит в том, что возвращаемое значение - это не просто одно значение в коллекции, а скорее эффективный способ индексации в коллекции. Метод BinarySearch является особенным не только потому, что он эффективно находит значение, но и потому, что он находит индекс даже в случае пропуска, как указал Теодор, - который обеспечивает быстрый доступ, например, к массиву. Однако в случае дерева целочисленный индекс не может быть эффективным способом доступа к структуре; C ++ решает эту проблему с помощью объекта итератора (хотя и со своими собственными сложностями).
J