Saturday, January 7, 2012

.NET Collection Runtimes

Each week my department holds a morning tech review. Subjects vary from testing tools, advanced caching mechanisms, to good ol' basic .NET facts. This week the tech review was an "Asymptomatic Analysis of .NET Collections". While most of the material was pretty straight forward, I always find getting back to the basics to be a good thing.

I thought that it was fun to see all of the collection run times aggregated into one table. As several of my coworkers pointed out, it can be a bit of a pain to find all these "simple" facts on the SEO crammed internet...so then why does no one simply blog about it?

In summary: here is some stolen content. Thanks Byron!

List-Like Collections

  List LinkedList SortedList
Add O(1) or O(N) O(1) O(Log N) or O(N)
Remove O(N) O(N) O(N)
Clear O(N) O(1) O(Log N)
Get O(1) O(N) O(Log N)
Find O(N) O(N) O(Log N)
Sort O(N log N) or O(N^2) - Already sorted
Underlying
Data
Structure
Array Dynamically allocated nodes Array

Hash-Like Collections

  Dictionary SortedDictionary HashSet SortedSet
Add O(1)
or O(N)
O(Log N) O(1)
or O(N)
O(log N)
Remove O(1) O(log N) O(1) O(N)
Clear O(N) O(Log N) O(N) O(N)
Get / Find O(1) O(Log N) O(1) O(Log N)
Sort - Already sorted - -
Underlying
Data
Structure
Array + Linked List Dynamically allocated nodes
(Binary Search Tree)
Array + Linked List Dynamically allocated nodes
(Binary Search Tree)

If you would like to see any updates/additions please feel free to leave a comment.

Enjoy,
Tom

1 comment:

  1. Reviews from former customers. Sometimes you have to https://essay.org/assignment-help confirm from others who have tried the essay service previously through their reviews or testimonials they write on the service.

    ReplyDelete

Real Time Web Analytics