The Road to Inefficient Code is Sometimes Paved with Good Intentions

 It’s been a while since I’ve done an analysis post but! I recently found some inspiring code. To be clear, I’m not trying to call out any developer here. I’m aiming only to use my findings to teach and the following is the gist of the matter at hand:

private SortedList<int, int> sortedList = new SortedList<int, int>();
   foreach(var value in GetSomeUnsortedCollectionOfInts())
        sortedList.Add(value, value);
   return sortedList.ContainsKey(someInt)

From inference, I think the noble intent was to use the SortedList to be able to quickly find out if the list contained some key. With the data sorted and as used above, a binary search can be performed to make finding out if the list contains some value a $$O(log_2(n))$$ operation. That part is fine. It is in populating the SortedList that the problem lies.

Written out mathematically, the foreach and the Add inside it (because per Microsoft documentation that Add will run in $$O(n)$$ time if the data isn’t sorted as is the case here) amount to this equation:

$$\sum\limits_{i=1}^n\sum\limits_{k=1}^i k$$

For those who might be a little rusty with your mathematical notation here’s an example of what it would do if $$n$$ was 3:


The numbers I’ve put in the parens are the summation from the inner $$\sum\limits_{k=1}^i k$$ and is just summing from $$1$$ to whatever $$k$$ is currently. The outer$$ \sum\limits_{i=1}^n$$ is adding between the parens, or summing the results of the inner sums. As it happens, this particular equation generates the number series called the Tetrahedral Numbers. For the purpose of this analysis, we’re most interested in the equation to find the $$n$$th tetrahedral which is:

$${n(n+1)(n+2)\over 6}$$

Cause that factors out to:

$${n^3+3n^2+2n\over 6}$$

And tells us that this particular implementation unnecessarily runs in $$O(n^3)$$ time because the $$n^3$$ dominates the equation. I say unnecessarily because with just a little reworking:

private int[] data = null;
   data = GetSomeUnsortedCollectionOfInts().OrderBy(k => k).ToArray();
   return Array.BinarySearch(data, someInt);

In this case the same goals are accomplished but in $$O(n$$ $$log(n))$$ time due to the the OrderBy() call. Graphically that’sgraph

A huge, very noticeable difference for even small values of $$n$$. To put the impact another way, imagine if that red line was how fast some code was going to drain your smartphone battery vs. the blue line for the same value of $$n$$. That’s why this stuff matters.

At this point in my career I’ve come to expect that these simple inefficiencies will be written, make it through code reviews and out into production because “the code works” and as per the Agile Manifesto “Working software is the primary measure of progress.”

Said manifesto also has, “Simplicity–the art of maximizing the amount of work not done–is essential.” The name of the analysis I’ve done above is called asymptotic analysis. It takes time and knowledge of Computer Science fundamentals to do and that I care to do this kind of analysis has gotten me told that I need to go be a professor instead of work in industry.

Given the demand for software today, I don’t think it’s realistic to expect all members of a development team to be up on their Computer Science fundamentals. I’ve said myself if you can tell a story, you can be a software engineer and I stand by that claim too. I also think it’s reasonable to expect these team members to be teachable. Otherwise business employing these teams will always be chasing what they could be doing instead of actually doing what they aim to do then moving on to the next thing, and/or throwing money away on “simply” written software that “works” but is inefficient and then unmaintainable from developers piling “simple” and inefficient code on top of “simple” and inefficient code. Which leaves me at:

Fundamentals, fundamentals, fundamentals, fundamentals.

Fundamentals, fundamentals, fundamentals, fundamentals.

Fundamentals, fundamentals, fundamentals, fundamentals. 😀

Takeoffs and Landings

I used to have a bunch of stories about my various adventures in Cessna a 150 or 172. I suppose I still have the stories but I haven’t told them in a long time because they’ve gotten so… vintage. 😀

Time to make some new ones!

True Colors Shining Through

I can’t help but believe the Microsoft CEO showed his true colors before the backtrack. I just don’t think enough guys care to listen. The “trust the system” comment he made is the worst cause it’s the system that’s letting women down.

Something big is amiss and the Microsoft CEO’s original statement betrays it. I mean, I’ve been doing this work for over 10 years and I’m crazy good at software engineering. Today, I want out of the field more than ever because of the treatment I’ve been taught to expect in the workplace. But! Student loans…

Sure, there are a some good advocates for women in a tech workplace. But there are way more than enough of those who prefer to tell us how to feel and prefer to tell us how to “fix” our lives rather than engage with us to see what we’re talking about.

And it ain’t just Nadella showing his true colors either:


I’m Still Here

When I was in High School I started a story that was intended to be like Ghostbusters only my characters would be busting aliens instead of ghosts. While that was my intent I didn’t end up writing that story because I never plan. What I ended up with was an epic mashup of The X-Files and Babylon 5 about an alien race called the Aklack and what they were doing on Earth.

Well, the Aklack are coming back!

In my mashup there were a few original ideas I’ve always liked and this year for this National Novel Writing Month I’ll be revisiting them and hopefully I’ll end up telling a good story this time.

What I’m sharing here is an exploration of the Universe I’ll be playing in and discovery of my main character, Regina Sinclair (I’ve decided to keep the last name despite being one of the many, many B5 echoes in the original story. Gotta have respect for the roots!)

I’m Still Here

5 Min: Full Moon Tonight

Been  a while since I’ve done one of these so a quick referesher is in order. I had five minutes to write to the prompt of, “Full Moon Tonight” What follows is what I came up with.

Travis looked at the sky, full moon tonight. Travis looked at the date on his phone, Halloween. Travis exhaled deeply as he held his hand on the Light Rail car’s controls. This could get, interesting.

Moving his train up from the Mall of America the night got colorful quick. Bloody brides, zombies, people embracing the opportunity to wear no pants. Why anyone would want to sit on any mode of public transportation in their underwear was lost on Travis. But, they filed on to his train in an orderly fashion and while he could hear the boisterous bunch growing behind him at each stop, they were behaved.

However, the thought weighed on him that he hadn’t gotten to Franklin. Ave yet, and the heart of the college crowd.

ReSharper Hurts Me

I’ve never outrun a tool before and been forced to wait for my IDE to catch up to me.

Though what gets me more are claims of, “How do you work with out ReSharper?” Then I show them. Then there is a, “Woah.”

Writing Sine Wave

OMG! This story is great! I’ve really got something here.

Oh wait.

That last bit was ok, but, will anyone be interested in this? Is this story even good?


Oh! I’ve got this great idea!

One of the rare times when going uphill is the fun part! 🙂