HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavascriptMinor

Challenge: solution for this deep-iteration JavaScript function dilemma?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
design-patternscodereviewjavascriptstackoverflowoptimizationalgorithm
thisdilemmachallengejavascriptfunctioniterationdeepforsolution

Problem

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!

Solution

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; ipresent 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) {

Code Snippets

function iter(obj,fn,iter_pos){
    var ret, iter_pos = iter_pos || [];
    for (var i=0; i<obj.length; ++i)
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
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)))
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!';

Context

StackExchange Code Review Q#23280, answer score: 9

Revisions (0)

No revisions yet.