JavaScript Optimization TheoryPart 1 of Chapter 10 from Speed Up Your Site (2/5)WebReference.com
[previous] [next] 
Speed Up Your Site, Chapter 10: Optimizing JavaScript for Execution Speed
Algorithms and Data Structures
As we learn in computer science classes, global optimizations (such as algorithm and data structure choices) determine in large part the overall performance of our programs. For larger values of "n," or the number of input elements, the complexity of running time can dominate any local optimization concerns. This complexity is expressed in Onotation, where complexity or "order" is expressed as a function of n. Table 10.1 shows some examples.
Table 10.1 RunTime Complexity of Classic Algorithms^{[12]}^{,}^{[13]}
Notation 
Name 
Example 
O(1) 
constant 
array index, simple statements 
O(logn) 
logarithmic 
binary search 
O(n) 
linear 
string comparison, sequential search 
O(nlogn) 
nlogn 
quicksort and heapsort 
O(n^{2}) 
quadratic 
simple selection and insertion sorting methods (two loops) 
O(n^{3}) 
cubic 
matrix multiplication of nxn matrices 
O(2^{n}) 
exponential 
set partitioning (traveling salesman) 
Array access or simple statements are constanttime operations, or O(1).
Wellcrafted quicksorts run in nlogn time or O(nlogn).
Two nested for
loops take on the order of nxn or O(n^{2})
time. For low values of n, choose simple data structures and algorithms.
As your data grows, use lowerorder algorithms and data structures that
will scale for larger inputs.
Use builtin functions whenever possible (like the Math
object),
because these are generally faster than custom replacements. For critical
inner loops, measure your changes because performance can vary among different
browsers.
Refactor to Simplify Code
Refactoring is the art of reworking your code to a more simplified or efficient form in a disciplined way. Refactoring is an iterative process:

Refactoring clarifies, refines, and in many cases speeds up your code. Here's a simple example that replaces an assignment with an initialization. So instead of this:
function foo() {
var i;
// ....
i = 5;
}
Do this:
function foo() {
var i = 5;
// ....
}
For More Information  Refactoring is a discipline unto itself. In fact, entire books have been written on the subject. See Martin Fowler's book, Refactoring: Improving the Design of Existing Code (AddisonWesley, 1999). See also his catalog of refactorings at http://www.refactoring.com/.
[previous] [next] 
12. Kernighan and Pike, The Practice of Programming, 41. Back
13. Andrew Hunt and David Thomas, The Pragmatic Programmer: From Journeyman to Master (Boston, MA: AddisonWesley, 1999), 179. Back
Created: January 8, 2003
Revised: January 8, 2003
URL: http://webreference.com/programming/optimize/speedup/chap10/1/2.html