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

Tuesday, January 3, 2012

Why Atwood's Law is a Good Thing

Any application that can be written in JavaScript, will eventually be written in JavaScript.

Jeff Atwood proposed this simple rule way back in 2007. Now, as his predictions come true, we may find ourselves asking "why would anyone want to do such a crazy thing?" Well here are three simple reasons:

1: Because we can!
Software development is an art that requires practice. Why do college students write compilers? Why did John Carmack port Rage to iOS? Why did I port Chrono Trigger to a graphing calculator? Software engineers are artisans, these challenges represent our art form at it's best.

2: JavaScript represents true platform independence.
Windows, Mac, Linux, x86, x64, iOS, Android, the list goes on; frankly, there are just too many platforms out there to develop for. The beauty of JavaScript is that it is a universally recognized spec that is supported everywhere. This level of accessibility is advantageous for developers and consumers alike.

3: It shows the power of modern technology.
The fact that we can run a Java Virtual Machine in the browser shows just how far modern browsers and house hold hardware have come. It was only a few years ago that Virtual Machines were a concept reserved for only the most powerful of server farms. The tower of Dubia was not built out of necessity, it instead stands as a monument to human achievement; that is how I view emulator hardware in a browser, a virtual monument of human engineering.

...also, why wouldn't you want to play NES games in your browser?

Tom

Real Time Web Analytics