Immutable Trie (nuget)
Immutable collections that use trie as their internal data structure, and provide a direct replacement for the .NET's implementation of ImmutableList and ImmutableDictionary.
This is an immutable dictionary that's aimed to replace the use of ImmutableDictionary. This collection uses comparable or less memory and provides at least 2x speed up in most operation comparing to .NET's ImmutableDictionary. This collection is based on hash array mapped trie.
A proposal was made in corefx's repo to use this data structure as the internal structure of ImmutableDictionary.
| Methods | Complexity |
|---|---|
| Get | O(log32 N) |
| Set | O(log32 N) |
| Remove | O(log32 N) |
This is an immutable list that's aimed to replace the use of ImmutableList. In general, this collection uses less memory and provides higher speed on most operations, except Insert and RemoveAt. These operations will re-index and reallocate the whole trie. If you want performance gain and in general didn't use Insert and RemoveAt, you can expect a performance gain by replace the existing usage of ImmutableList to this ImmutableTireList. This collection is based on vector trie.
A proposal was made in corefx's repo to use this data structure as the internal structure of ImmutableList. However, due to the expensive InsertAt and RemoveAt operation, which will change the performance of the already shipped ImmutableList, the proposal was dismissed.
| Methods | Complexity |
|---|---|
| GetRange | O(log32 N) |
| Get | O(log32 N) |
| Add | O(1) |
| Pop | O(1) |
| InsertAt | O(N log32 N) |
| RemoveAt | O(N log32 N) |