Linear Operations

<rant>

We all know O(n) = O(2n), right?  I mean, we’re talking about how algorithms scale here.  Linear is linear.  I add 100 more elements to my dataset and the time to finish what ever I was doing scales linearly.

Now that’s all fine and good but think a bit when working with code. Just because O(n) = O(2n) doesn’t mean that you should just throw loops around willy-nilly when with a bit of smarter design you can do O(n) instead of O(2n).

In the real world when iterating over datasets (especially potientially large datasets in my case) there is a big difference between O(n) and O(2n).

For example:

foreach(MyObjectType myObject in myList)
{
    //do something
}
foreach(MyObjectType myObject in myList)
{
    //do something
}

I know this may be a bit of an oversimplification but lately I’ve been looking at a lot of code that basically works out to the above. It’s really more like:

MyList stuffToProcessNext = new MyList();
foreach(MyObjectType myObject in myList)
{
    //do a lot of stuff here with a bunch more loops
    //rather then write some recursion to another method to handle children
    //and siblings just add to stuffToProcessNext
    stuffToProcessNext(myObject);
}
//now that MyObjects are processed and I don't have to worry about the
//siblings I can finish processing each of the children to MyObjects
foreach(MyObjectType myObject in myList)
{
    //do a lot of stuff here with a bunch more loops
    foreach(MyObjectType childObject in myObject.Children)
    {
        //do something relating to the siblings of myObject
    }
}

But don’t just look at your own code, understand how the underlying framework code works.
For example:

//assume myList is a List
//and myObject is MyObjectType
if(myList.Contains(myObject))
    myList.Remove(myObject);

No need to call Contains and force the framework to iterate over the list twice. Just remove it. No worries if it isn’t there.

</rant>

Please return to your regulary scheduled program.

Brian

Leave a Reply