6
\$\begingroup\$

Trying to implement a deep-iteration function with some constraints, I've noticed the faster solution is iterating it twice! Any attempt to avoid this resulted in slower code. So, the challenge: can you redesign the function below removing the code duplicate and doubled iteration, without making it slower?

Constraints:

  • It must deeply iterate through a tree, providing, for a callback function, the node value and it's path.
  • It must work for arrays and objects.
  • Arrays must be iterated by ascending numerical keys first and non-numerical keys last.
  • It must allow for early interruption by using "return", and must return that value.

Code:

function iter(obj,fn,iter_pos){
    var ret, iter_pos = iter_pos || [];
    for (var i=0; i<obj.length; ++i)
        if (ret = typeof(obj[i]) == "object" ? iter(obj[i],fn,iter_pos.concat(i)) : fn(iter_pos.concat(i),obj[i]))
            return ret;
    for (var key in obj)
        if (isNaN(Number(key)))
            if (ret = typeof(obj[key]) == "object" ? iter(obj[key],fn,iter_pos.concat(key)) : fn(iter_pos.concat(key),obj[key]))
                return ret;
};

Test:

var tree = [1,2,[3,3,3],4];
tree.x = 5;
tree.y = {x:6,y:7,z:8};
tree.z = 9;
console.log(
    iter(tree,function(path,val){ 
        console.log("Value ",val," at path: ",path); 
        if (val==7)
            return "Returned early!";
    })
);

Output:

Value  1  at path:  [ 0 ]
Value  2  at path:  [ 1 ]
Value  3  at path:  [ 2, 0 ]
Value  3  at path:  [ 2, 1 ]
Value  3  at path:  [ 2, 2 ]
Value  4  at path:  [ 3 ]
Value  5  at path:  [ 'x' ]
Value  6  at path:  [ 'y', 'x' ]
Value  7  at path:  [ 'y', 'y' ]
Returned early! 
\$\endgroup\$
9
\$\begingroup\$

Let me start by asking how would you like to iterate over your object? Because what you are doing is not the same as calling a function for every property of an object.

function iter(obj,fn,iter_pos){
    var ret, iter_pos = iter_pos || [];
    for (var i=0; i<obj.length; ++i)

The above for loop may access elements in the array that are not even defined. For example, take this array:

var a = [0, 1];
a[9] = 9;
console.log(a.length);  // -> 10
console.log(a.hasOwnProperty(0)); // -> true
console.log(a.hasOwnProperty(1)); // -> true
console.log(a.hasOwnProperty(2)); // -> false !!
console.log(a.hasOwnProperty(9)); // -> true

The above array has a length of 10, but it only has three properties (it has 10 elements, but not all are defined). If you do an a.forEach(), you'll iterate over the array's properties, only those that are defined.

If you do a for (i=0; i<a.length; i++) loop over the array, you'll get properties that are not defined. To avoid those, you should check a.hasOwnProperty(). Or just use the native forEach, if you can, that will iterate over the array correctly.

Note that checking against undefined would not be sufficient either, array elements can be present but undefined:

a[5] = undefined;
console.log(a.hasOwnProperty(5)); // -> true !!
        if (ret = typeof(obj[i]) == "object" ? iter(obj[i],fn,iter_pos.concat(i)) : fn(iter_pos.concat(i),obj[i]))
            return ret;
    for (var key in obj)
        if (isNaN(Number(key)))

Here you're trying to do the opposite of forEach: enumerating properties that are not elements of the array.

But this code will miss properties that still evaluate as numbers! Have a look at the following array:

var a = [0, 1, 2, 3, 4];
a[100] = 99;
a[1.5] = 'this is not an array element';
a[-1] = 'this one is not an array element either';
a['20'] = 'this one *is* an array element!';

Also, watch out for rounding:

a[30.00000000000001] = 'this is *not* an array element';
a[30.000000000000001] = 'this *is*, however, because it rounds to 30'

But also for the string representations:

a[30.000000000000001] = 'array element';
a['30.000000000000001'] = 'not array element';

Especially the ones that evaluate the same:

a[1e1] = 'element number ten';
a['1e1'] = 'a completely different element';

'-1', '1.5', '1e1', '30.000000000000001', etc. can all be properties of an array, but they will all evaluate false for isNaN(Number(key)).

            if (ret = typeof(obj[key]) == "object" ? iter(obj[key],fn,iter_pos.concat(key)) : fn(iter_pos.concat(key),obj[key]))
                return ret;
};

You can easily fix your script by changing the line

        if (isNaN(Number(key)))

to

        if (!key.match(/^\d+$/))

, but unfortunately that makes your code about 18% slower.

TL; DR

I've removed the double loop from your code:

function iter(obj, fn, iter_pos){
    var ret, iter_pos = iter_pos || [];
    for (var key in obj)
        if (ret = typeof(obj[key]) == "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key]))
            return ret;
};

and it does not seem to be any slower, or at least not according to jsperf.com/iter.

I tried it in a number of browsers I could find.

UPDATE 1:

Here is a version that uses two loops, but is much faster. It will fix the ordering, but only in cases where the array indexes come before other array properties.

__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
    var ret, i = 0,
        iter_pos = iter_pos || [];
    if (__toString.call(obj) === '[object Array]') {
        obj.forEach(function (item) {
            if (!ret) {
                ret = typeof (obj[i]) === "object" ? iter(obj[i], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[i]);
                i++;
            }
        });
        if (ret)
            return ret;
    }
    for (var key in obj)
        if (--i < 0)
            if (ret = typeof (obj[key]) === "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key])) return ret;
};

UPDATE 2:

This is your original version, with two loops, but using forEach and Object.prototype.toString. It seems to output the same result, but is about 2000× faster.

__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
    var ret, iter_pos = iter_pos || [];
    if (__toString.call(obj) === '[object Array]') {
        obj.forEach(function (item) {
            if (!ret)
                ret = typeof (obj[i]) === "object" ? iter(obj[i], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[i]);
        });
        if (ret)
            return ret;
    }
    for (var key in obj)
        if (!("" + key).match(/^\d+$/))
            if (ret = typeof (obj[key]) === "object" ? iter(obj[key], fn, iter_pos.concat(key)) : fn(iter_pos.concat(key), obj[key]))
                return ret;
};

UPDATE 3:

This version is about as fast as the other one, but uses only Object.prototype.toString and does not use typeof.

__toString = Object.prototype.toString;

function iter(obj, fn, iter_pos) {
    var ret, obj_type, iter_pos = iter_pos || [];
    if (__toString.call(obj) === '[object Array]') {
        obj.forEach(function (item) {
            if (!ret)
                ret = ((obj_type = __toString.call(item)) === "[object Object]") || (obj_type === "[object Array]") ? iter(item, fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), item);
        });
        if (ret)
            return ret;
    }
    for (var key in obj)
        if (!("" + key).match(/^\d+$/))
            if (ret = ((obj_type = __toString.call(item)) === "[object Object]") || (obj_type === "[object Array]") ? iter(obj[key], fn, iter_pos.concat(i)) : fn(iter_pos.concat(i), obj[key]));
                return ret
};
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Awesome answer! I thought nobody would answer this question. Thanks! Enlightening in many aspects. I had no idea numeric keys worked that way. Yet your implementation has a problem I have faced before: it is not guaranteed to iterate numeric keys in ascending order in some implementations (the double loop is actually a bugfix for this behavior!) Sucks, no? \$\endgroup\$ – MaiaVictor Mar 1 '13 at 2:07
  • \$\begingroup\$ Hmm, I've only checked that in Chrome, and there it iterated in ascending order. Let me try something else now (another double-loop idea that may be faster). \$\endgroup\$ – Attila O. Mar 1 '13 at 2:09
  • \$\begingroup\$ I'm not sure how/when, but sometimes it just doesn't iterate in the right order. I know it have something to do with defining numeric keyvals after the array was created, on safari I think. Very specific, but broke many things. \$\endgroup\$ – MaiaVictor Mar 1 '13 at 2:12
  • \$\begingroup\$ @Dokkat please look at my second update. It keeps the two loops, but uses the built-in forEach for arrays, and uses the regex match to correctly exclude array elements in the second loop. It is 2000× faster than the original code. \$\endgroup\$ – Attila O. Mar 1 '13 at 3:19
  • \$\begingroup\$ What the heck!? Hold on while I test. But how did you find that out? How did you even consider that regex could be faster than isNaN? \$\endgroup\$ – MaiaVictor Mar 1 '13 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.