﻿ JavaScript ﻿

Main Page

# JavaScript

This algorithm is fairly common because iterating over the values in an array is a very common tech-
nique. However, another linear algorithm is used commonly in JavaScript: the
named property lookup
.
Named properties are just basic properties of objects, such as
oDog.name
. Although this may look like
a variable that is local to the given object, in reality, it’s actually a search through the properties of the
object looking for the one matching
name
. For this reason, it’s always best to use local variables or
numerically indexed array values instead of named properties.
Consider this example:
var aValues = [1, 2, 3, 4, 5, 6, 7, 8];
function testFunc() {
for (var i=0; i < aValues.length; i++) {
alert(i + “/” + aValues.length + “=” + aValues[i]);
}
}
Here are the algorithms represented in this code:
?
i
in
i < aValues.length
— constant(O(1))
?
aValues.length
in
i < aValues.length
— linear(O(
n
))
?
i
in
alert(i + “/” + aValues.length + “=” + aValues[i]);
— constant(O(1))
?
aValues.length
in
alert(i + “/” + aValues.length + “=” + aValues[i]);
linear(O(
n
))
?
aValues[i]
in
alert(i + “/” + aValues.length + “=” + aValues[i]);
constant(O(1))
The linear algorithms are of particular interest here because they can easily be replaced with constant
algorithms. All the linear algorithms are run twice every time the loop runs: once when the
i <
aValues.length
test is run after each loop iteration, and once in the
alert()
call. That means the
linear algorithms are executed 16 times throughout the function execution.
The following code does the exact same thing, but uses only one linear algorithm:
var aValues = [1, 2, 3, 4, 5, 6, 7, 8];
function testFunc() {
for (var i=0, iCount=aValues.length; i < iCount; i++) {
alert(i + “/” + iCount + “=” + aValues[i]);
}
}
In this example, a second variable is initialized in the
for
loop,
iCount
, which is assigned the value of
aValues.length
. Then, the test after each iteration of the loop becomes a constant algorithm because
it is accessing the variables
i
and
iCount
instead of
aValues.length
. Likewise, by replacing
aValues.length
with
iCount
in the
alert()
call, another linear algorithm is eliminated. Ultimately,
this code executes with only one linear algorithm instead of 16, which decreases execution time.
583
Deployment Issues
22_579088 ch19.qxd 3/28/05 11:43 AM Page 583

Free JavaScript Editor     Ajax Editor

©
﻿