Immutable collection algorithmic complexity
I received some feedback from my recent BCL blog post on the prerelease of the immutable collections that my algorithm complexity table left a few important entries out. Here is the table again, with more data filled in (particularly around list indexer lookup and enumeration):
|
Mutable (amortized) |
Mutable (worst case) |
Immutable |
|
|---|---|---|---|
|
Stack.Push |
O(1) |
O(n) |
O(1) |
|
Queue.Enqueue |
O(1) |
O(n) |
O(1) |
|
List.Add |
O(1) |
O(n) |
O(log n) |
| List lookup by index | O(1) | O(1) | O(log n) |
| List enumeration | O(n) | O(n) | O(n) |
|
HashSet.Add, lookup |
O(1) |
O(n) |
O(log n) |
|
SortedSet.Add |
O(log n) |
O(n) |
O(log n) |
|
Dictionary.Add |
O(1) |
O(n) |
O(log n) |
| Dictionary lookup | O(1) | O(1) – or strictly O(n) | O(log n) |
|
SortedDictionary.Add |
O(log n) |
O(n log n) |
O(log n) |
A noteworthy trait to call out here is that where a List<T> can be efficiently enumerated using either a for loop or a foreach loop, ImmutableList<T> does a poor job inside a for loop, due to its O(log n) time for its indexer. It does fine when using foreach however. This is because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.
Another point to call out from the above table is that SortedSet<T> has the same complexity as ImmutableSortedSet<T>, and in fact in perf tests they show up as pretty close. That’s because they both use binary trees. The significant difference of course is that ImmutableSortedSet<T> uses an immutable one. Since ImmutableSortedSet<T> also offers a Builder class that allows mutation, you can have your immutability and performance too. Woot.
Light
Dark
0 comments