JavaScript Performance – Part I

This is the first in a series of articles I plan to write on improving performance in JavaScript heavy web-applications. More specifically I will discuss some of the ways you can improve on JavaScript based animations, reducing object chains, cross-browser DOM, clever ways of writing/designing objects and so on.

Improving on Animations
No matter what type of animation it is if it’s written using JavaScript it’s most likely going to make use of setTimeout or setInterval. Both of these function work like a timeline in Flash and therefore it’s ideal for doing animations.

To begin with setInterval is much faster than setTimeout. The reason is setInterval causes a function to continously run until it’s stopped using clearInterval, where as setTimeout runs a function after a given time and stops; therefore if you wanted to animate something using setTimeout you would somehow have to keep calling setTimeout (until the animation ended) where as in setInterval this is done only once.

The down-side of this is setInterval is supported only by Internet Explorer so to get really high performance you might want to write one version (separate files) of your JavaScript that’s geard towards Internet Explorer and another for Netscape (which supports setTimeout).

Next time I will discuss how to run multiple animations at once using one-thread (or one setTimeout or setInterval).

Using XSLT to view graphical poll results

How I came to this is not relevant I think, so I will jump straight to the examples. The idea was to convert this XML document to produce this output. So I set out to do it — and it was finally done using this XSLT stylesheet.

The idea is quite basic. Count the number of ‘I agree’ responses and store it in a variable. Count the number of ‘I disagree’ responses and store it into another variable, and so on…

Once that’s done, the count values are multiplied with the expansion factor (variable: efactor) and this number is set to the height of a div element. That’s all.

Let’s all resolute to producing a standardized web!

Overloading STL sorting algorithm

The STL sorting algorithm allows you to pass in a function pointer that the algorithm will use to compute the sorting transformation. This can be particularly useful when you need a set of data sorted in an order other than plain ascending or descending. The STL sorting algorithm further gurantees the sorting to be done in O(n lg*n) time (given your function is constant time).

The function pointer however has to meet the following requirements:

• Return type bool
• Accepts two const reference arguments of type Template <T> where T is the type of the current iterator

Here’s a small sample of how this can be used:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
string order;

bool newSortType(const string& s1, const string &s2) {
	int i=0;
	while(s1[i] == s2[i] && s1[i]!='' && s2[i]!='') ++i;
	if(s1[i]=='' && s2[i]!='') return true;
	return order.find(s2[i]) > order.find(s1[i]);
}
int main(void) {
	char tmp[255];
	vector<string> cand;

	cin.getline(tmp, 255);
	order = tmp;

	while(tmp[0]!='') {
		cin.getline(tmp, 255);
		cand.push_back((string)tmp);
	}
	sort(cand.begin(), cand.end(), newSortType);

	for(int i=0;i<cand.size();++i) {
		cout << (string)cand[i] << endl;
	}
	return 0;
}

How Presidential Elections work?

A surprising number of people actually do not know how American presidential elections work. In one of my classes yesterday my friends got into an argument with the teacher about the whole “who elects the president issue”. So I studied this matter in depth and hope to clarify the concept for the readers of my blog.

Each state has two groups of people: (1) The senate (2) House of representatives. For each state there are always 2 senates. The number of people in the house of representative however depends on the population census (more population means more individuals in the house of representative) of the state. In California for example, there are 53 members in the House of Representatives. South Dakota on the other hand has 1 member in their House of Representative.

The senate and the House of Representatives are collectively called: The Electoral College. Therefore, in this year’s election California will be represented by 55 (53+2) individuals.

What does all this have to do with voting? Well it turns out our (the peoples’) vote do not directly elect the president. It’s the vote by the Electoral College that actually elects the president.

Let me clarify. For instance, let’s say in California the majority of the people vote democrat then the all of the members of the Electoral College will vote democrat; they have the option not to; but in the history of US elections a disagreement between Electoral College votes and majority votes has happened only 4 times. Gore vs. Bush in 2000 was one of them.

An important consequence of this is the number of states a presidential-candidate control is not an issue but the total number of representatives is what makes the difference. So even if Bush controls majority of the states — Kerry could (theoretically) win by controlling only few of the large (in terms of population) states in the US.

The key idea here is that all of the members of the Electoral College have to vote the same. They cannot vote independently. The only exception being the swing states: Nebraska (5 members) and Maine (4 members) — which means members of the Electoral College from these two states can vote independently. Making them potential swingers in the final presidential decision.

Finally a vote of 271 (538 (total # of electoral college) / 2 + 1) by the Electoral Colleges’ wins presidency. To find out how many representatives are in your state visit the: Electoral College Calculator.

Election 2004

This year’s election is going to be one of the most tightly contested elections in history of US. So I urge anyone who can vote TO VOTE!. See the current poll results (49% Kerry / 49% Bush):

Source: USA Today News

Automatic Red-eye removal (AI) ?

The field of AI had made lots of promises to us. For instance, automatic sentence correction, context based spell checking (eg: then, than both spelled and sound [almost] the same yet depends on the context to be correct), shape extraction (extract human faces from crowded environments) and so on… I was under the impression those are still further away into the future until Moore’s law numerically exponentiates several times over.

I was surprised to find out about this project called: RedBot which is lead by Hewlet-Packard (HP). The idea is you upload an image file with Red-Eye issues in it and a computer program processes your image and lets you download the fixed image all for free. This is very different from a photo correction software. In softwares like this you usually have to define the area (or at least the approximate vicinity) where the Red-eye is and then the software does the processing to fix it (in Photoshop you have to do it manually!)

Anyway, at first this might seem like a simple problem but there are several major issues to take care of. (1) RedBot automatically recognizes shapes of human beings within a picture (no matter what age group they are). To prove this, if you upload an image with a dog that has Red-eye and a human that has a Red-Eye all in the same picture then RedBot will only fix the human’s eye and leave the animals’ eye alone.

How might this work?
The internals of this software obviously can detect human faces. I would assume it extract the edges of the complete picture and searches for shapes that match a range of human faces. This is not at all full proof. Issues like overlapping faces or cut of faces would cause the software to fail completely. A way to fix these issues is to search for shapes of eyes including eye-brows and nose (based on the edge) only. This takes care of lot of the issues. For instance overlapping face is OK, as long as there is nothing overlapping the eye (in which case there cannot be any Red-eye). Secondly partial faces wouldn’t be a problem because the software isn’t really searching for a face, but searching for the shape of the eye (using edges). But what if part of the eye is cut-off from the picture? This seems to be a complex problem to solve and I haven’t tested RedBot to see if it works.. But any thoughts on this would be interesting.

Google Book Search

Google launched a new book search feature to their search engine. This is how it works, when you do a search Google looks for the words in web-sites and in addition to that Google looks at for the words within books. If a match is found within a book that page of that book is loaded and displayed (of course you can also see the book cover, index/table of contents and so on). For instance, try the following search: mastering digital photography at the top of the page you will see “Book results for…” which will link you to the following page.

Quite useful and a great feature I think!

100% height in Netscape

Since the height attribute in table isn’t standard XHTML/HTML this renders differently in each browser. To get the correct output in Netscape (or most Mozilla based browsers) do the following:

First set the table height to 100%:

<table height="100%" ... >
<tr height="100%"> ...
<td> ... </td>
</table>

The above code alone will display correctly in Internet Explorer however in Netscape (Firefox/Mozilla (Linux)) there is one more trick that you need to add:

<style type="text/css">
html, body {
	height:100%;
}
</style>

Hope that helps.

Solution to Line Tracker

In my previous post I discussed an algorithm that it is much better than the general line following algorithm that one might think of at first. Last night I implemented the algorithm with NQC with descent results. Here’s the solution:

/***********************************************
	* Salman Quazi
	* CS-595EA
	* Date: September 19, 2004
***********************************************/
/* Constant Definitions */
#define SENSOR		SENSOR_1
#define LEFT_MOTOR	OUT_C
#define RIGHT_MOTOR	OUT_A

/* Speed settings */
#define NORMAL_SPEED 7
#define TURN_SPEED 2
#define DELAY	20

/* This setting depends on several conditions like: lighting, contrast between the tape and the floor ... */
#define LINE_COLOR 768
#define FLOOR_COLOR 710

int eye;

/* I have been thinking about taking the average color of the
floor and the black tape for more reliable results */
int average_color = (LINE_COLOR+FLOOR_COLOR)/2;

task main() {
	SetPower(LEFT_MOTOR,  NORMAL_SPEED);
	SetPower(RIGHT_MOTOR, NORMAL_SPEED);
	OnFwd(LEFT_MOTOR+RIGHT_MOTOR);

	while(true) {
		eye = SENSOR;
		SelectDisplay(DISPLAY_SENSOR_1);

		if (eye <= FLOOR_COLOR) {
			SetPower(LEFT_MOTOR+RIGHT_MOTOR, TURN_SPEED);
			Fwd(RIGHT_MOTOR);
			Rev(LEFT_MOTOR);
			On(LEFT_MOTOR+RIGHT_MOTOR);
			while(SENSOR <= FLOOR_COLOR);
		}
		else if (eye >= LINE_COLOR) {
			SetPower(LEFT_MOTOR+RIGHT_MOTOR, TURN_SPEED);
			Fwd(LEFT_MOTOR);
			Rev(RIGHT_MOTOR);
			On(LEFT_MOTOR+RIGHT_MOTOR);

			while(SENSOR >= LINE_COLOR);
		}
		else
			continue;

		SetPower(LEFT_MOTOR+RIGHT_MOTOR, NORMAL_SPEED);
		Fwd(LEFT_MOTOR);
		Fwd(RIGHT_MOTOR);
		On(LEFT_MOTOR+RIGHT_MOTOR);
	}
}

This was compiled with NQC version 2.5 r3 on RCX 2.0 (on a Windows 2000 Professional system).

Of course there is room for improvement. (1) Increase NORMAL_SPEED and still be able to follow the line (by reducing latency speed). (2) If the system encounters an object while travelling the line then it should get around it somehow, and so on…