Pumping Station: One has a location!

I just saw the new Pumping Station: One location for the first time, and it’s made me very excited. Getting a bunch of talented, interesting, friendly people together is just what I had in mind as I finished reading Earth Abides. Seeing everybody in the actual space today cemented the reality of the group in my mind, and has me full of anticipation of what we can accomplish.

Everybody is making me jealous with their ASUS EEE PCs, and now that I have somewhere to hang out and code I really need a laptop! So that’s my next project… The big decision is not really on the hardware but the software: Linux or Windows? The last time I ran Linux was in college, so I’m a little hesitant.

Speak & Spell!

Those of you who remember the Speak & Spell will probably love my first attempt at a website redesign based around it.

So far, you can type letters using the keys, and it has sounds I recorded from my actual Speak & Spell. The text is much bigger than the real thing, so it can be read, but it is limited to 8 characters like the real thing. The sounds are somewhat delayed on Firefox, and the text is in the wrong place in IE… but you can see the potential!

The image is from a patent application made by Texas Instruments. Hopefully they don’t mind if I use it!

Edit: it’s now my home page

Rails inconsistency

I like Ruby on Rails, but the design is sometimes inconsistent.

For example, consider the “text_method” parameter to the collection_select helper method. The argument forces you to call a method on the model object which returns the text which is used in the select list. That’s ok when you only want to display a single field from that object, for example “name”. It’s not ok if you want to display something more complicated, because then you’re putting display logic into the model. You’re supposed to use helpers for that! Since doing it right would make it ugly and more complicated, I end up giving in and doing it the wrong way by adding a method to the model. It frustrates me.

Duo Melis

This blog is notably lacking in the subjects of music and art, so to help remedy that here is a video of the classical guitar duo I had the delight of hanging out with this weekend. http://www.youtube.com/watch?v=gXMOB1BvpwY

They are amazing musicians, not to mention hilariously funny and smart. Besides hearing a totally INTENSE and inspirational performance, I got to hear really funny and endearing stories about their adventures. Susana is from Spain, while Alexis is from Greece, so they’re doubly interesting to talk to.

Unfortunately, writing about it tends to deflate the experience. But I will update if they are in Chicago again. Until then, check out their website http://www.duomelis.com/

Javascript Mergesort

A while ago, I couldn’t find any Javascript mergesort implementations, so I wrote one. The nice thing about mergesort is that it is “stable”, id est it retains the previous order of elements with equal value. Therefore it is great for sorting rows in a table on different columns sequentially. Also, the merge() function is handy for merging two sorted arrays into one big sorted array.

Check out Wikipedia for more info on mergesort and other sorting algorithms.

Here it is:

var MergeSorter = function(comparator) {
	var merge = function(a, b)
	{
		var aLen = a.length;
		var bLen = b.length;
	
		if(aLen == 0)
			return b;

		if(bLen == 0)
			return a;

		var i, j, k;
		i = j = k = 0;
		var result = Array();
		while(i < aLen && j < bLen)
		{
			if(comparator.compare(b&#91;j&#93;, a&#91;i&#93;))
				result.push(a&#91;i++&#93;);
			else
				result.push(b&#91;j++&#93;);
		}
		while(i < aLen)
			result.push(a&#91;i++&#93;);
	
		while(j < bLen)
			result.push(b&#91;j++&#93;);
	
		return result;
	};
	return {
		sort: function(a)
		{
			var aLen = a.length;
			if(aLen <= 1)
			{
				return a;
			} else {
				var middle = Math.round(aLen / 2);
				var left = a.slice(0, middle);
				var right = a.slice(middle);
				left = this.sort(left);
				right = this.sort(right);
				var result = merge(left, right);
				return result;
			}

		}
	}
};

var normalComparator = {
	compare: function(n1, n2)
	{
		return n1 >= n2;
	}
};

Here is sample code that makes use of the MergeSorter and does some sanity checks. It could easily be turned into a set of unit tests.

var mockComparator = {
		calls: 0,
		compare: function(n1, n2)
		{
			this.calls++;
			return n1.num &gt;= n2.num;
		}
};

function writeError(str)
{
	document.write(&#39;&lt;span style=&quot;color: red;&quot;&gt;&#39; + str + &#39;&lt;/span&gt;&lt;br&gt;&#39;);
}

var size = 100000;
var ary = new Array(size);
for(var i = 0; i &lt; size; i++)
{
	var num = Math.round(Math.random() * size);
	ary[i] = {num: num, id: i};
}
document.write(&#39;&lt;br&gt;&#39;);

var start = new Date().getTime();
var myMergeSorter = new MergeSorter(mockComparator);
ary = myMergeSorter.sort(ary);
var stop = new Date().getTime();
var executionTime = stop - start;

document.write(&#39;Merge sorting an array with &#39; + ary.length + &#39; random integers in it...&lt;br&gt;&#39;);
document.write(&#39;Execution time: &#39; + executionTime / 1000 + &#39;s&lt;br&gt;&#39;);
document.write(&#39;Result length: &#39; + ary.length + &#39;&lt;br&gt;&#39;);
document.write(&#39;Comparisons: &#39; + mockComparator.calls + &#39;&lt;br&gt;&#39;);

var ceilLgN = Math.ceil(Math.log(size) / Math.log(2));
var maxExpectedCompares = (size * ceilLgN - Math.pow(2, ceilLgN) + 1);
document.write(&#39;Worst case (for this size): &#39; + maxExpectedCompares + &#39;&lt;br&gt;&#39;);
document.write(&#39;Theoretical average (for this size): &#39; + (maxExpectedCompares - 0.2645 * size) + &#39;&lt;br&gt;&#39;);

if(ary.length != size)
{
	writeError(&#39;Result is not the right size: &#39; + ary.length);
}

for(var i = 0; i &lt; ary.length; i++)
{
	if(ary[i + 1])
	{
		if(ary[i].num &gt; ary[i + 1].num)
		{
			writeError(&#39;Sorting error at index &#39; + i + &#39;! &#39; + ary[i].num + &#39; greater than &#39; +
				ary[i + 1].num);
			break;
		}
		if(ary[i].num == ary[i + 1].num &amp;&amp; ary[i].id &gt; ary[i + 1].id)
		{
			writeError(&#39;Stability error at index &#39; + i + &#39;! &#39; + ary[i].id + &#39; greater than &#39; +
				ary[i + 1].id);
			break;
		}
	}
}

if(mockComparator.calls &gt; maxExpectedCompares)
{
	writeError(&#39;Too many comparisons executed!&#39;);
}

Edit on December 1, 2010: I modernized the code a bit by making use of object literals, closures, etc. The comparator no longer has to be passed down the recursion. In order to do that with merge() and sort() as top-level functions, the comparator would have to be assigned to a global variable. Also, I added a more thorough example of the usage, with sanity checks.

It is worthwhile to mention that some Javascript implementations, array.sort() is already stable. See, for example, the documentation on sort at the MDC. Since native implementations of sort() have the potential to be much faster, it may be worthwhile to check whether this is the case and if so implement user agent testing to determine whether to use Javascript’s sort, or your own implementation.

braindump – html 5

As pointed out on slashdot, the first public material on HTML 5 is now available from the W3C. http://www.w3.org/TR/2008/WD-html5-diff-20080122/

It’s a major victory that frames have been completely removed from the language. They have always been horrible for the UI, security, bookmarkability, etc.

However, I take major issue with their choice to standardize innerHTML into the DOM. The only reason I’ve ever used innerHTML is because sometimes it’s impossible to get IE to behave any other way. IE’s poor lack of support for DOM is no reason to standardize a workaround though! Not only does innerHTML promote bad programming practices, it can all-too-easily lead to injection attacks.