Brendan Enrick

Daily Software Development

The Joys of Windows Live Writer

I've just downloaded and started trying out windows live writer, and I think it is excellent. This has got to be just about the easiest and best program for blog writing I've ever seen.

Features I love

  • View Web Preview - This view actually shows me what the blog is going to look like and it actually shows it with my blog there including the content from the left column and the previous blog posts beneath this one.
  • The generated html is reasonably well formed.
  • I can type in my tags without having to have added them to the blog in advance.
  • Plug-ins, plug-ins, and more plug-ins. I haven't looked at it but I am assuming that it is easy to write plug-ins for Live Writer.
  • Inserting Images, Tables, and Maps is incredibly easy.
  • I have no trouble finding what I need in the toolbar even with my plug-ins installed.
  • Auto-saving my blog posts as drafts as I type.
  • Insert link has a button to select a previous post so rather than finding that post somewhere and copying the link I just found it in this application.
  • I can also save my links from within the insert link window.
  • Formatting is simple and easy (unlike other programs which I have used).

Ok I give up. I refuse to write any more about how great this program is. Now is the time for me to go and look at some more of these plug-ins. I recommend you go and download Windows Live Writer and blog away.

Generic List AddRange, Remove, and Count Performance

The .NET System.Collections.Generic.List class is not a linked list as non-.NET users might expect. This list class is actually more like an array list than a linked list. Because of this it has some of the benefits of arrays. Simply because of the array data structure which exists within the generic list class, the class is able to achieve a constant time Count function. The basic array data structure is a collection of objects which are stored contiguously in memory, and because of this it makes counting them easy. It also makes it quite easy to index into a specific location, because you can just jump straight to the correct location in memory. With a linked list one has to traverse the list. The advantage of the linked list is that it is held together using pointers, so if you want to add nodes it is simply an update to pointers. This means that adding a collection of nodes can take constant time.

I would highly recommend against the array list if you will be adding and removing objects from this collection often. Since there is an allocated amount of space in memory for the array this means that if you need to exceed this space then you will need to create a new list. Using Big O notation the AddRange function of list will take O(n) time to complete. The n in this case is the number of elements to add. This doesn't seem to bad, but when the allotted space is exceeded the array will need to move and recreate itself with more space. This is the big performance hit. For this operation it will have O(n+m) time, because you will have to do the regular n operations plus m operations for the original data in the array.

Removing an element from an array requires a little bit of work. One reason for this is that the array data structure should never contain an empty space. This means that first you will need to perform a linear search algorithm to find the element to remove. Stepping one by one through the list. Upon reaching the element to remove, it is removed, but then all the elements after that one must be moved forward in the array so no space exists. This causes the remove function to perform in linear time.

  • Capacity O(1)
  • Count O(1)
  • AddRange O(n) or O(n+m)
  • Remove O(n)

I am planning to write of series of little bits of stuff. If you catch any mistakes in any of this series please comment on the correction ASAP. I don't want to be passing along incorrect information.

Enjoy! 

C++ List Operation Performance

I am fairly certain that the C++ Standard Template Library's list object's size function is an O(n) operation. For those of you less algorithmically informed people I am saying that a linked list which uses pointers to the next object in the list has to take linear time (directly corresponding to the number of elements) to find out the size of the list. At first this seems kind of odd. One would wonder why not just keep the count of the elements stored somewhere.

Keeping the count of the number of elements in a linked list will make what I believe is the linked list's greatest asset less valuable. The splice function (which is like the AddRange function) is able to just update pointers. This is amazingly useful because added n number of elements can take constant time. Meaning that it takes just as long to add 10 elements as to add 1000 elements. When needed that is a life saver. Having that ability though prevents being able to keep track of the size of the list, because the list doesn't know how many elements you are splicing in. It would need to take linear time to count them. Because of this it would make it linear instead of constant time. Ouch.

Because of this close relationship between the size and splice functions one will have to be linear and one constant. It seems that it was decided that with a linked list it would just be easier to iterate to the end instead of using the size. Splicing is a lot more important in my opinion to the usefulness of a linked list. I suggest perhaps a second object which is a linked list which has a constant size and a linear splice for when size will be checked more often than splicing will occur.  

I was discussing this with someone recently and found it quite interesting, and I now think I am going to go and start reading more about the algorithms of the functions used in C#. Perhaps in the future I will write about the algorithms in .NET and the runtime of these algorithms. I hope so.