12

I was reading about C#'s ImmutableSortedDictionary in System.Collections.Immutable and thinking about how to apply it in my program. I quite like C++'s lower_bound and upper_bound (see here), and I was rather expecting to see something of the sort for range lookups. However, similar methods seem to be strangely absent from the documentation. Am I missing something? Or does MS truly provide a sorted dictionary without efficient access to the sorted ranges? That doesn't exactly seem like something one could do on an IEnumerable of the keys as say an extension method, so I'm a bit puzzled I'm not seeing something provided directly by the collection.

Agnel Amodia
  • 765
  • 8
  • 18
J Trana
  • 2,150
  • 2
  • 20
  • 32
  • Eric Lippert shared an [immutable AVL tree implementation](https://blogs.msdn.microsoft.com/ericlippert/2008/01/21/immutability-in-c-part-nine-academic-plus-my-avl-tree-implementation/) back in 2008. From the comments, I don't think it's been particularly optimized for speed or efficiency yet, but the `IBinarySearchTree` it implements looks closer to what I would expect. I wonder if he ever tinkered on it further? – J Trana Nov 11 '19 at 14:37
  • The [`ImmutableList`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablelist-1) class is also implemented as an AVL tree. From the [source code](https://github.com/dotnet/corefx/blob/7d3a7b7fb8fe648c1f402bb63b55f623c3065e42/src/System.Collections.Immutable/src/System/Collections/Immutable/ImmutableList_1.cs#L28): `/// The root node of the AVL tree that stores this set.` – Theodor Zoulias Nov 13 '19 at 19:07
  • Do you know if they mean that the list uses an AVL true to implement immutability or if the AVL tree itself is immutable? (maybe it doesn't matter as they don't expose the tree anyway). – J Trana Nov 14 '19 at 01:10
  • Here are the advantages of the `ImmutableList` (backed by an AVL tree) over the `ImmutableArray` (backed by an array), according to the [documentation](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablearray-1#remarks). *Reasons to use immutable list: 1) Updating the data is common or the number of elements isn't expected to be small. 2) Updating the collection is more performance critical than iterating the contents.* – Theodor Zoulias Nov 14 '19 at 09:19
  • This is because when adding or deleting an element from a large AVL tree, you can get a new tree without destroying the original one, by sharing most of the nodes and creating only a few new nodes. ([Persistent data structure - Trees](https://en.wikipedia.org/wiki/Persistent_data_structure#Trees)) – Theodor Zoulias Nov 14 '19 at 09:25
  • SortedDict wraps SortedSet and i see it has an internal Node SortedSet.FindRange(T from, T to) You could create delegates to the internal methods and then access your Ranges. Or just copy the implementation from SortedSet.FindRange – Charles Nov 15 '19 at 04:53
  • @Charles copying the implementation of the internal [`FindRange`](https://referencesource.microsoft.com/system/compmod/system/collections/generic/sortedset.cs.html#03df9da9e6b0283e) method of the `SortedSet` class is not helpful because we don't have access to the internal `Node` class. So not only this method but all code of the `SortedSet` class must be copied, and then heavily modified to make it compile. The other idea of accessing this method throw reflection is an act of desperation IMHO. Much better to use a tested third-party library than following this dangerous route. – Theodor Zoulias Nov 15 '19 at 10:53

1 Answers1

8

It is irritating that the available built-in collections are not offering a full set of features (like the SortedDictionary lacking a BinarySearch method), forcing us to search for third-party solutions (like the C5 library).

In your case instead of an ImmutableSortedDictionary you could probably use a ImmutableSortedSet, embedding the values in the keys and using an appropriate comparer. At least the API of this class contains the properties Min and Max.

Theodor Zoulias
  • 34,835
  • 7
  • 69
  • 104
  • 2
    As a side note, another immutable class, the [`ImmutableList`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablelist-1), is implemented internally [as a tree](https://alexatnet.com/immutablelist-performance/). So it is 10 times slower and allocates 12 times more memory than a `List`. Use [`ImmutableArray`](https://learn.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutablearray-1) instead. – Theodor Zoulias Nov 07 '19 at 08:38
  • 1
    Hehe, I use C5 already but looking to see what was available for immutable collections (beyond snapshots). Thanks! I'm going to hold out hope that someone else has solved this in some way shape or form, but I'll keep in mind the `ImmutableSortedSet` – J Trana Nov 07 '19 at 14:08
  • @TheodorZoulias what is point of having BinarySearch method in SortedDictionary, when TryGetValue method is working in log(N)? [see here](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sorteddictionary-2.trygetvalue?view=netframework-4.8) – Dzliera Nov 13 '19 at 18:48
  • 2
    @GiorgiChkhikvadze the [BinarySearch](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch) can give you the next element that is larger than the item you are searching for, in case an exact match is not found. – Theodor Zoulias Nov 13 '19 at 18:55
  • 1
    @GiorgiChkhikvadze Probably the biggest difference here is that the return value is not just a single value in the collection, but rather a way to index into the collection efficiently. The method BinarySearch is special not only because it finds the value efficiently but because it finds an index even in the case of a miss as Theodor pointed out - which allows for fast access into e.g an array. In the case of a tree though, an integer index might not be an efficient way to access the structure; C++ solves this through the use of an iterator object (albeit with its own complexities). – J Trana Nov 14 '19 at 01:23
  • @GiorgiChkhikvadze some other methods that are missing from the `SortedDictionary` are the `TryGetPredecessor`, `TryGetSuccessor` and `GetRangeFromTo`. All these are well within the capabilities of the internal tree data structure, and without them these operations are extremely inefficient. You can see [here](https://c5docs.azurewebsites.net/classC5_1_1SortedDictionaryBase.html) how rich is the API of the corresponding `C5.SortedDictionaryBase` class (from the [C5](https://github.com/sestoft/C5) library). – Theodor Zoulias Nov 14 '19 at 10:27