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:

$$(1)+(1+2)+(1+2+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.

http://www.npr.org/blogs/thetwo-way/2014/10/09/354964666/microsoft-ceo-backtracks-on-suggestion-that-women-shouldnt-ask-for-raises

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

http://www.businessinsider.com/grace-hopper-celebrations-male-panel-2014-10

*sigh*

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! 🙂

“Purging” by Paige Alexis Rudnick

Ever since I read Julia Seranno’s Whipping Girl, where she points out that in media practically without fail when a transwoman is depicted there is a scene of her putting on makeup that trope has bothered me. It seemed to me that there were more interesting topics to portray such as, what do you when you realize you’re trans at a very young age?

My short story “Purging” is about just that.

It ain’t autobiographical, but you could say it’s inspired by true events. And! It’s available here.

In Browser, Computer Vision Based, Pong

Screen Shot 2014-03-10 at 2.09.59 PM To begin, I just couldn’t resist using an a Atari harkening font in this one. 🙂

This particular project evolved my GLSL skills and started to teach my brain how to work on a GPU better which, naturally, means I have a very nicely decorated whiteboard to my right at the moment. And I’ll be sharing it too, in a moment…

I’ve been thinking about doing a Computer Vision project for a little while now. I was inclined to do a desktop app and use OpenCV but on doing some research on what goes in to computer vision I realized, “Hey, I know the tools to make this work in browser.” So, I did.

My first task to get Computer Vision working was take the RGB feed from my WebCam and convert it to HSV. I’ve done chroma keys before just using the raw RGB values but with the recommendation that HSV might work better, I figured why not give it a try? This is where the GLSL came in and what I had to write was an implementation of the following:

Let $$R = $$ the Red RGB component in the range 0.0 to 1.0

Let $$G = $$ the Green RGB component in the range 0.0 to 1.0

Let $$B = $$ the

Blue RGB component in the range 0.0 to 1.0

Let $$Epsilon =$$ a inconsequential float value to prevent division by 0.

The definition of $$max$$ is elided, but it just returns the maximum of the values it was passed in.

$$H =\begin{cases} G – B & max(R, G, B) = R \\ B – R & max(R, G, B) = G \\ R – G & max(R, G, B) = B\end{cases}$$

$$H$$ had to be accompanied with a related offset value:

$$H’ =\begin{cases} 0 & max(R, G, B) = R \\ 1/3 & max(R, G, B) = G\\ 2/3 & max(R, G, B) = B\end{cases}$$

So my final result for Hue is actually $$H”=H+H’$$ This was because in the HSV colorspace, $$H$$ is represented as a circle going round from \(R \rightarrow G \rightarrow B \rightarrow R\) So, in order to get select the right hue, an offset will need to be applied to get the value round to the right place.

$$S=\frac{\Delta}{max(R, G, B) + Epsilon}$$

And finally

$$V=max(R, G, B)$$

I found some other documentation about this calculation online and found it messy. That might be normal when discussing math like, I don’t really know,  this but my engineering brain likes things broken down into their individual components. Hopefully, the above will help someone else out! 🙂 Now to calculate that on the GPU making it time to live up to my promise of bringing the whiteboard in… analysis

I ended up being heavy on mix() and step() in order to reduce the branching I had to write. Branching, as I understand, is getting to be less of a concern in GPU programs but the article saying that branching implementation was improving was from 2011 and that’s too recent to assume all GPU’s will behave nicely. Below those function notes, there’s a tracking of how my values were going to flow through in the vectors so I could end up with a the maximum in the first position, the two values I needed to subtract to get my $$H$$ and finally the offset $$H’$$ that went with the selected $$H$$ so I could calculate $$H”$$ properly. For the curious, the shuffling that’s done with mix() and step() was effectively a vectorized ternary operator.

The conversation of RGB to HSV and writing the GLSL shader to do that was most of the effort. But the shader wasn’t quite done yet. The final step was passing Min and Max values for each value: H, S, V. When all three where within the defined min and max, the shader needed to return white, when any of them were out of bounds, the shader had to return black. This way, the user can select an object in the real world by its color that will function as a paddle. Now I did look for and find shader implementations of RGB to HSV online, however, I opted to roll my own to make sure I understood what was going on as this was pretty much the beating heart of this project.

On the JavaScript side of things I did run into a problem. I wanted to use sliders so users could hone in on the color they wanted to select. However, HTML5 only allocates one thumb per slider. I know I could have used jQueryUI for to get two thumbs but I opted to stay away and handle the problem myself. It was also tempting to use three.js to handle the WebGL side of things but I decided to not bring it in either. The changes weren’t too significant from my ANSI.WebGL project so I saw no need to take on another dependency.

The JavaScript I did write is pretty straight forward. There’s a ball (a div that’s been styled to look like aball) that flys around and when it hits a paddle it flies back the other way. Hitting here has been defined as the left or right side of the ball hits a white paddle pixel. When that happens, the column of pixels is counted for connected white pixels to figure out the length of the paddle. If it’s above a threshold (provided to filter out artifacts) the calculation figures out where the ball was hit in relation to the paddle then the ball will bounce away at an angle. The only “gotcha” I ran into with this part was when I read the pixels from the buffer, I found them inverted which broke my hit detection! But it was a simple fix to right them thankfully.

For much larger computer vision problems I probably would turn to something like OpenCV. Still getting to understand something like sometimes, we convert to the HSV color space, is I think very important! Understanding how the tools you are using work I hold to be key to actually using them well. It also allows you to answer a question I’ve mentioned before as being part of my process. 😉

You will need either a recent version of Firefox or Chrome in order to run this project due to the needs of getUserMedia() and WebGL.

https://github.com/dreambbqchild/CVPong

http://www.animetedstudios.com/webapps/CVPong/