for in to iterate sparse Array

[Manish Tomar]

Hi,

I know that using for in loop to iterate over array elements is a bad
idea but I have a situation where it is tempting me to use it. I have
a two dimensional sparse array say "arr" which will have length to be
some 50 but will have some elements like arr[1], arr[10], arr[23] at
random locations. Each of these elements is again an array (since it
is two dimensional) say arr[1][30], arr[1][24] & so on for arr[10 &
23] also. Currently I've coded it like this:

for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
if (arr && arr[j]) {
// do stuff with arr[j]
}
}
}

but i am tempted to do following

for (var i in arr) {
if (!arr.hasOwnProperty(i)) {
continue;
}
for (var j in arr) {
if (arr.hasOwnProperty(j)) {
// do stuff with arr[j]
}
}
}

thinking it to be faster. What are your views?

Thanks,
Manish
(http://manishtomar.blogspot.com)

 

[RobG]

Hi,

I know that using for in loop to iterate over array elements is a bad
idea but I have a situation where it is tempting me to use it. I have
a two dimensional sparse array say "arr" which will have length to be
some 50 but will have some elements like arr[1], arr[10], arr[23] at
random locations. Each of these elements is again an array (since it
is two dimensional) say arr[1][30], arr[1][24] & so on for arr[10 &
23] also. Currently I've coded it like this:

for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
if (arr && arr[j]) {
// do stuff with arr[j]
}
}
}

but i am tempted to do following

for (var i in arr) {
if (!arr.hasOwnProperty(i)) {
continue;
}
for (var j in arr) {
if (arr.hasOwnProperty(j)) {
// do stuff with arr[j]
}
}
}

thinking it to be faster. What are your views?

The issues with using for..in to iterate over an array are:

1. It usually indicates that a plain object should have been used -
this doesn't seem to apply here.

2. If Array.prototype has been exteded, you'll get it's extra
properties as well.

If your code is never used with any other library, the second issue
doesn't arise and your use of hasOwnProperty (you can also use
propertyIsEnumerable) accounts for it anyway.

Do it.

 

[Dr J R Stockton]

In comp.lang.javascript message <[email protected]

, Wed, 11 Jul 2007 02:40:46, David Mark <[email protected]> posted:

What makes you think it would be faster?

It seems rather obvious that the "in" method should be faster.

Did you benchmark it? You should
be able to speed up the first example like this:

var li = arr.length - 1;
var lj;
for (var i = li; i >= 0; i--) {
lj = arr.length - 1;
for (var j = lj; j >= 0; j--) {
if (arr && arr[j]) {
// do stuff with arr[j]
}
}
}

I didn't test (or benchmark) this code, but I know the theory is sound.

A pretty reliable indication of unreliable code.

That improvement will be small in comparison with that hoped for by
using the other method. But you should have been able to gain a little
more by using while loops, and by changing two lines to
if (T=arr && T[j]) {
// do stuff with T


To compare the two access methods, for a simpler case :-

function F1(A) { var T=0, J = A.length, x
while (J--) if (x=A[J]) T += x
return T }
function F2(A) { var T=0, J
for (J in A) T += A[J]
return T }
a = [] ; a[999] = 1


K_ = 2000 // increase
D0_ = new Date()
Q_ = K_ ; while (Q_--) {F1(a)}
D1_ = new Date()
Q_ = K_ ; while (Q_--) {F2(a)}
D2_ = new Date()
Q_ = [D1_-D0_, D2_-D1_] // Demo 6

which gives me results like 860,15 showing that "in" is very much faster
for a very sparse array.

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

 

[David Mark]

In comp.lang.javascript message <[email protected]



It seems rather obvious that the "in" method should be faster.

"Should be" or "will be" in this specific case? Perhaps you can
assume that it will, but I would benchmark it first.

Did you benchmark it? You should
be able to speed up the first example like this:

var li = arr.length - 1;
var lj;
for (var i = li; i >= 0; i--) {
lj = arr.length - 1;
for (var j = lj; j >= 0; j--) {
if (arr && arr[j]) {
// do stuff with arr[j]
}
}
}
I didn't test (or benchmark) this code, but I know the theory is sound.

A pretty reliable indication of unreliable code.

Are you having a laugh? That's what my disclaimer means. The idea
should be obvious from the example, but don't paste it into a
production page without testing it first. I didn't need to benchmark
it as I know the theory is sound from previous experience.

That improvement will be small in comparison with that hoped for by

So it will reliably speed up the process?

using the other method. But you should have been able to gain a little
more by using while loops, and by changing two lines to
if (T=arr && T[j]) {
// do stuff with T

Okay.

To compare the two access methods, for a simpler case :-

There were three: the one I posted, the one I compared it to and the
"for in" loop (which I did not address at all.)

function F1(A) { var T=0, J = A.length, x
while (J--) if (x=A[J]) T += x
return T }
function F2(A) { var T=0, J
for (J in A) T += A[J]
return T }
a = [] ; a[999] = 1

K_ = 2000 // increase
D0_ = new Date()
Q_ = K_ ; while (Q_--) {F1(a)}
D1_ = new Date()
Q_ = K_ ; while (Q_--) {F2(a)}
D2_ = new Date()
Q_ = [D1_-D0_, D2_-D1_] // Demo 6

which gives me results like 860,15 showing that "in" is very much faster
for a very sparse array.

Yes, in this case it is faster. But will it be faster for the OP's
example? I imagine it should be.

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

I have read much of the latter, but haven't had time to read the
newsgroup in its entirety. FWIW, I did Google JavaScript, "for in",
Jibbering, FAQ and arrays and found nothing, save for a lot of
warnings against using this method. For example:

http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Statements:for...in

Is there a specific FAQ entry you are referring to?

 

[Dr J R Stockton]

In comp.lang.javascript message <[email protected]
oglegroups.com>, Thu, 12 Jul 2007 11:32:03, David Mark

"Should be" or "will be" in this specific case? Perhaps you can
assume that it will, but I would benchmark it first.

If I had meant "will be", I should have written "will be".

So it will reliably speed up the process?
Slightly.



There were three: the one I posted, the one I compared it to and the
"for in" loop (which I did not address at all.)

The first two that you mention are basically the same method, one with a
partially-improved implementation. The OP presented two distinct
methods for comparison.

Yes, in this case it is faster. But will it be faster for the OP's
example? I imagine it should be.

Virtually certainly. Though we don't know exactly how sparse the data
is, and we don't know for sure what properties the array may have.
Consider
var A = [0,1,2]
A.rhubarb = 6
T = 0 ; for (J=0; J<A.length; J++) T += A[J] // 3
T = 0 ; for (J in A) T += A[J] // 9

FWIW, I did Google JavaScript, "for in",
Jibbering, FAQ and arrays and found nothing, save for a lot of
warnings against using this method. For example:

http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Stat
ements:for...in

You presumably mean the content of the yellow box? That shows that
Mozilla don't think of everything. Using for..in should be safe enough
provided that none of the warnings apply.