Coffeehouse Post

Single Post Permalink

View Thread: Immutable collections for .NET arrive
  • User profile image

    @evildictaitor: hopefully we'll have time to discuss the O(log n) time for adding and accessing ImmutableList in the video. But here's a quick explanation. Your whipped up example of how to achieve O(1) time breaks down quickly for certain mutations. For example, if I have a 1000 element list (that's backed by an array) and I add one more element to it, yes, I can stitch together a sort of segmented linked list by having a "1 + 1000" ImmutableList wrapper. But what if you want to remove one element from a segment? Now you have to copy the entire segment, which gives you O(n) time. Also, if you're building up your list one item at a time, the array segments will only be 1 item long, and all your accesses will be O(n) anyway because you'll effectively have a linked list.

    Now if all you have is a read-only list with no intention to efficiently handle mutation by allocation, then a single array, wrapped in a ReadOnlyCollection<T> is perfect. It will have the O(1) time you want for lookups. But the immutable collection strives both for an immutability guarantee and efficient mutation as well. In order to guarantee consistent and reasonably high performance for most scenarios we implemented the list not as a linked list of arrays but as a binary tree. Now any mutation or lookup takes O(log n) guaranteed, regardless of how the caller builds up the list in the first place. Again, this isn't right for everybody, but it's good for most applications. And you can still enumerate the list in O(n) time, just like an array.

    I hope that helps.