I received some feedback from my recent BCL blog post on the prerelease of the immutable collections<\/a> 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):<\/p>\n
| <\/p>\n<\/th>\n | \n Mutable (amortized)<\/p>\n<\/th>\n | \n Mutable (worst case)<\/p>\n<\/th>\n | \n Immutable<\/p>\n<\/th>\n<\/tr>\n |
|---|---|---|---|
| \n Stack.Push<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n<\/tr>\n |
| \n Queue.Enqueue<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n<\/tr>\n |
| \n List.Add<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n<\/tr>\n |
| List lookup by index<\/td>\n | O(1)<\/td>\n | O(1)<\/td>\n | O(log n)<\/td>\n<\/tr>\n |
| List enumeration<\/td>\n | O(n)<\/td>\n | O(n)<\/td>\n | O(n)<\/td>\n<\/tr>\n |
| \n HashSet.Add, lookup<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n<\/tr>\n |
| \n SortedSet.Add<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n<\/tr>\n |
| \n Dictionary.Add<\/p>\n<\/td>\n | \n O(1)<\/p>\n<\/td>\n | \n O(n)<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n<\/tr>\n |
| Dictionary lookup<\/td>\n | O(1)<\/td>\n | O(1) – or strictly O(n)<\/td>\n | O(log n)<\/td>\n<\/tr>\n |
| \n SortedDictionary.Add<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n | \n O(n log n)<\/p>\n<\/td>\n | \n O(log n)<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n A noteworthy trait to call out here is that where a List<T> can be efficiently enumerated using either a for <\/strong>loop or a foreach <\/strong>loop, ImmutableList<T> does a poor job inside a for<\/strong> loop, due to its O(log n) time for its indexer. It does fine when using foreach<\/strong> 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.<\/p>\n Another point to call out from the above table is that SortedSet<T> has the same<\/em> 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<\/em> have your immutability and performance too. Woot.<\/p>\n","protected":false},"excerpt":{"rendered":" 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) […]<\/p>\n","protected":false},"author":2685,"featured_media":37840,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[106,4617,3916],"class_list":["post-36050","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-permierdev","tag-net","tag-andarno","tag-immutability"],"acf":[],"blog_post_summary":" 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) […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts\/36050","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/users\/2685"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/comments?post=36050"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/posts\/36050\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/media\/37840"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/media?parent=36050"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/categories?post=36050"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/premier-developer\/wp-json\/wp\/v2\/tags?post=36050"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |