The Software Purist |

Archive for December 2015



Binary Search Part II

A while back (read: years ago), I wrote this post: Software Purist – Binary Search. It wound up being an exercise in algorithm design, along with some interesting points I made about the 80/20 principle and testing. Without looking at what I had done previously, I decided to try to write binary search again. Here’s what I came up with. You should note that this example will use C++11. Here’s the code:

#include <array>
#include <cassert>

using namespace std;

template<class T, class... Tail>
auto make_array(T head, Tail... tail)
  -> std::array<T, 1 + sizeof...(Tail)>
	std::array<T, 1 + sizeof...(Tail)> a = { head, tail ... };
	return a;

template <class TContainer>
int binarySearch(const TContainer& container,
                 const typename TContainer::value_type& val)
	auto oldBegin = -1;
	auto oldEnd = -1;
	auto begin = 0;
	auto end = container.size() - 1;

	while ((oldBegin != begin || oldEnd != end) && (begin <= end))
		oldBegin = begin;
		oldEnd = end;

 		const auto half = (end - begin + 1) / 2 + begin;
		if (container[half] == val)
			return half;
		else if (container[half] < val)
			begin = half + 1;
		else if (container[half] > val)
			end = half - 1;

	return -1;

int main()
	auto x = make_array(1, 2, 5, 9, 13, 18, 72, 1385);

	assert(binarySearch(x, 0) == -1);
	assert(binarySearch(x, 1) == 0);
	assert(binarySearch(x, 2) == 1);
	assert(binarySearch(x, 3) == -1);
	assert(binarySearch(x, 5) == 2);
	assert(binarySearch(x, 8) == -1);
	assert(binarySearch(x, 9) == 3);
	assert(binarySearch(x, 12) == -1);
	assert(binarySearch(x, 13) == 4);
	assert(binarySearch(x, 15) == -1);
	assert(binarySearch(x, 18) == 5);
	assert(binarySearch(x, 36) == -1);
	assert(binarySearch(x, 72) == 6);
	assert(binarySearch(x, 1000) == -1);
	assert(binarySearch(x, 1385) == 7);
	assert(binarySearch(x, numeric_limits<int>::min()) == -1);
	assert(binarySearch(x, numeric_limits<int>::max()) == -1);

It took me a few tries to make it work flawlessly on paper. However, I noticed my test cases were more robust. Obviously, the use of C++11 clouds the issue slightly, as well. I also noted I’m more willing to use int as a data-type now and more likely to use automatic-typing. I’m sure this is due to the influence of other programming languages, like C# and Python. In comparing to the previous, I also noticed better naming, using half rather than newIndex. But, the most striking thing was the fact that my solution was actually different than the previous solution. It encapsulated the same idea, and it’s similar, but not exact. Both solutions work. It’s interesting to see how one’s programming-style evolves ever so slightly (or significantly) over time. It would be hard to say one solution is better than the other.

Going back to the original thought, I still find it amazing that only 10% of programmers get this right. But, as I tried it out on paper, it definitely took me a few goes through my test cases to get it quite right. So, maybe it’s not so far fetched. I think what this is really saying is that 90% of programmers don’t put enough time into unit testing and their test cases. So, let’s discuss that a bit more.

My test cases in this example encompassed all of the following:

  • All values in the array
  • Values not in the array
  • Values not in the array between values that were in the array
  • Negative values
  • Very negative values (checking for underflow)
  • Very large values (checking for overflow)
  • Values less than the minimum value in the array
  • Values larger than the maximum value in the array
  • Zero

If you look at the above, that’s a pretty robust way to approach boundary testing and I encourage you to do the same (where feasible). All of the above can be sources of errors. Also note that sometimes a test case covers multiple conditions, which is great. Just make sure you have a sufficient amount of test cases, to be confident. And then, of course, automate. Normally, one would use a unit test framework, but I wanted to make the code simple enough to run on modern compilers with no additional libraries.

· · ·



First Post Using Dvorak Keyboard

Hello everyone. This is my first post using the Dvorak keyboard layout. If you’re not familiar with Dvorak, it’s an alternate layout which has a different order of keys for efficiency purposes.

The normal QWERTY keyboard layout was developed at a time when very limited typewriters were the norm. Typing too fast risked damaging the typewriter, so the keys were oriented so that the most used keys were all on the left side of the keyboard. This was done to ultimately limit typing speed.

What Dvorak does is reorient the keys so the most used keys are near the center and split at a much more reasonable ratio. This results in typing a lot more with the right hand (Most people are righties) and faster typing speeds, due to better distribution.

I’ve been trying it out this week and so far the results are positive. I normally type around 100 wpm. While my speed has been nowhere near that so far, it is steadily climbing every day. I can see myself topping that in a few weeks, as long as I keep at it.

As far as using Dvorak, you don’t need a special keyboard to use it. You can just choose a different layout in your operating system. On Windows, you can change this in control panel -> Keyboards and Languages -> Change keyboards. Then go to add, expand your language and choose the appropriate Dvorak layout.

One final useful tip is to keep the On-Screen Keyboard visible while you’re learning. On Windows, you can find this in All Programs -> Accessories -> Ease of Access -> On-Screen Keyboard.

No tags

Recently, one of my colleagues at a previous job mentioned to me something to the effect of, “I’m less of a versioning geek that I feel I’m supposed to be as a Software Developer”. This comment sparked an interesting discussion.

First, I’ll start with some background. My former colleague used to work with me at the gaming company I worked at and tends to work on small projects and with artists. For him: the main features of an SCM he finds useful are commit, check out and the ability to tag a set of code.

As you might expect, my perspective is quite a bit different. I’ve worked on some small projects, for sure. But, my specialty is larger systems working with teams that have been as large as 50 people or more. In these cases, obviously an SCM has to be quite a bit more. When we talked further, he talked about “a normal case” being that one person owns a particular file, so why make it so complicated? This brought up the fact that for large projects, someone owning a file is not a normal case and tends to be a bottleneck. This is why locking-style SCMs are rarely used at most companies I work for—the overhead is too immense and it requires the file owner to be available 24/7 and instantly responsive, which is certainly an unrealistic expectation.

The killer features for large teams are the ability to commit often without conflict and be able to merge at critical points smoothly and efficiently. Distributed SCMs like Mercurial and Git are prime examples of systems that handle this well. For developers that work on smaller projects, like my friend, the main reason use to SCMs is to be able to go back to an old revision. Of course, this is useful for everyone, especially when you’re trying to understand a system, but I still find the case of merging to happen far more frequently for me.

The other interesting point of this discussion was specific to Git, since I didn’t realize his complaint was specific to Git at the time. Git has a lot of commands, but only a small subset are actually useful to most users. Furthermore, the vast number of commands can make things complicated to non-technical people. In his company, game artists were also using Git as a versioning mechanism for their artwork. I would debate whether this is a good approach for asset management for a variety of reasons (maybe this can be a future post). It definitely seems very complex for an artist.

Overall, I found the discussion very interesting from the perspective of someone working on different-style project than I tend to work on. What are some of the interesting ways you use source control? Do you find patterns that tend to ease things more for large projects vs. small projects?

No tags

Theme Design by