Archive for January, 2007

Microsoft::IE::hasHeadache(true);

hasLayout falsehasLayout true

I was building a little demo tonight to show how to create a multiple document interface (MDI) using divs, some image files and the “script.aculo.us” JavaScript library. Of course, when I was just about finished, Internet Explorer 6 starts acting up.

Firing up the old IE Developer Toolbar I discovered that my lil’ol div didn’t “have layout“. This one property (unique to Internet Explorer) has given me more grief than all of WCAG, CSS, div-hell and XHTML combined – well, that’s pushing it – but, you get the idea. Okay, give the little guy layout (sets height to some value) and voila; it works. The MDI article will have to wait another day; I’m going to bed.

Meebo is hiring!

Meebo is hiringWe’re building an Ajax-enabled chat client for ATutor so I was looking at how Meebo does their cool chat interface. Well, it looks like Meebo is hiring!

Go faster with Horner’s rule

Consider the following polynomial:
Fourth order polynomial
This is a fourth-order polynomial. To evaluate this thing, you might write the following code in Python.

def f(x):
    return x**4 + x**3 + x**2 + x + 1

The problem is that calculating exponents is computationally expensive, so you might try to create a closed form of the equation. In this example, you can use the well known generating function:
Generating function form of the polynomial
This reduces the number of exponents that Python has to deal with. Watch the division by zero error if you let x=1!

def genf(x):
	return (1 - x**5)/(1-x)

If we could reduce or eliminate the number of exponents even further, we might expect that the code would run faster. Fortunately, you can apply Horner’s Rule to this problem. The rule removes the exponents by factorizing the equation into a series of multiplication and addition steps:
Horner's Rule applied to fourth order polynomial
The equation, now missing the expensive exponents, can be implemented like this:

def hornerf(x):
	return (((x+1)*x+1)*x+1)*x+1

So now you’re probably thinking, “Show me the money!”

The following code is a test harness that counts how much time it takes to execute the functions on a large set of numbers.

def timeit(fn):
	begin = time.time()
	for element in bigset:
		fn(element)
	end = time.time()
	return end - begin

The following is a transcript of the test run on my laptop:

>>> ================================ RESTART ================================
>>> def f(x):
        return x**4 + x**3 + x**2 + x + 1

>>> def genf(x):
	return (1 - x**5)/(1-x)

>>> def hornerf(x):
	return (((x+1)*x+1)*x+1)*x+1

>>> import time
>>> bigset = range(2,1000000)
>>> def timeit(fn):
	begin = time.time()
	for element in bigset:
		fn(element)
	end = time.time()
	return end - begin

>>> timeit(f)
9.2969999313354492
>>> timeit(genf)
4.4679999351501465
>>> timeit(hornerf)
2.1099998950958252

In this example, you could gain a speed improvement of over 70% from eliminating the exponents in your code. Although not all optimizations will be this dramatic, you will almost always gain some improvement by eliminating exponents.

Thanks to D Yoo

MeeboMaker: for valid XHTML Meebo Widgets

Valid HTML Meebo Widgets with MeeboMakerMeebo is a web-based instant messaging client that allows users to integrate their instant message clients into one easy-to-use web interface. Rather than chatting from the MSN, AIM or Yahoo desktop clients, Meebo allows you to chat from a lightweight Ajax interface. You can also generate Meebo widgets that allow IM interaction from web sites or blogs.

The problem is that the code generated by Meebo’s widget factory is non-valid XHTML. This can be a problem for people who build web sites that require valid HTML. The Meebo widget factory produces a Flash container based on the embed tag which is not part of the XHTML 1.0 Transitional specification. I was able to build a valid container based on the object tag which will pass automatic validation.

Rather than get into the messy details, I have created a simple application that extracts the important bits of information from the embed tag and builds a new object tag. It is still kind of temperamental, but it works well as long as you don’t try to feed it bad code. Give MeeboMaker a try and let me know what you think.