Friday, January 23rd, 2009
Speed up your JavaScript with memoization and queueing
Category: JavaScript, Performance
This time he again discusses the problem with loops, and in this case nested loops:
-
-
function bubbleSort(items){
-
for (var i=items.length-1; i>= 0; i--){
-
for (var j=i; j>= 0; j--){
-
if (items[j] <items[j-1]){
-
var temp = items[j];
-
items[j] = items[j-1];
-
items[j-1] = temp;
-
}
-
}
-
}
-
}
-
What can you do to minimize the steps? He first talks about splitting it up asynchronously, and then goes into Doug Crockfords memoizer function, applying it to the standard Fibonnaci:
-
-
function memoizer(memo, fundamental) {
-
var shell = function (n) {
-
var result = memo[n];
-
if (typeof result !== 'number') {
-
result = fundamental(shell, n);
-
memo[n] = result;
-
}
-
return result;
-
};
-
return shell;
-
};
-
-
var fibonacci =
-
memoizer([0, 1], function (recur, n) {
-
return recur(n - 1) + recur(n - 2);
-
});
-
Finally, he attacks functions that just do too much, and kicks off the pieces so the browser can get back to its work:
-
-
function schedule(functions, context){
-
setTimeout(function(){
-
var process = functions.shift();
-
process.call(context);
-
-
if (functions.length> 0){
-
setTimeout(arguments.callee, 100);
-
}
-
}, 100);
-
}
-
-
schedule([doSomething, doSomethingElse, doOneMoreThing], window);
-
Of course, for serious workload, this is what Web Workers are ideal for. In fact I just saw a new post on using Workers in extensions that shows the API nicely.
Also, just in case you are going for a Google front end position and you want to marry JavaScript and algorithms, how about remembering binarySearch to go along with the earlier bubbleSort:
-
-
Array.prototype.binarySearch = function binarySearch(find, comparator) {
-
var low = 0;
-
var high = this.length - 1;
-
var i, comparison;
-
while (low <= high) {
-
i = parseInt((low + high) / 2);
-
comparison = comparator(this[i], find);
-
if (comparison <0) { low = i + 1; continue; };
-
if (comparison> 0) { high = i - 1; continue; };
-
return i;
-
}
-
return null;
-
};
-
Related Content:
dejavu … and in my “Stressfull procedure? Distribute your task!” entry I implemented the delay and the in-line or propagated scope.
The result with the queue callbacks stack is a slower application that is more responsive instead of a “not that quick” one that is stuck till the end of the loop. As summary, a slower execution for a faster, non modal, interaction, sounds weird, doesn’t it? :D
Just out of interest, regarding the Zakas “schedule” example how would I pass parameters to each function.
I did a “more generic” version of a memoization function not so long ago, if someone’s interested.
http://blog.thejit.org/2008/09/05/memoization-in-javascript/
@ doomedlung: I tried creating a method for that. It accepts any number of arguments as long as those arguments has a string representation. If you can imporve it please let me know.
You can find it at http://www.jslab.dk/library/Function.memoize
I like building the memoization right into the function, using the fact that a function is an object that can have properties.
Wow, takes me right back to Intro to Programming…nice.