Optimizing nested objects walk

Question

I have a nested object structure and I perform a serie of operations on each object and then I push it to an array. My current code looks like this:

var item;
var final_data = [];

function walk (items, level) {
    for (var i = 0; i < items.length; i++) {
        item = items[i];

        var final_item = Object.assign({}, item); // <-- required step, object's proper key/values must be cloned, but not recursively.
        delete final_item.children; // final_item shouldn't have children

        final_item.foo = level;

        final_data.push(final_item);

        if ("children" in item) walk(item.children, level + 1);
    }

}

walk(my_data, 0);

My current code works as expected, as in, it flattens the input data.

My question is if there is a way to improve that code (performance wise).

Edit:

my_data is an array of nested objects, like this:

my_data = [
    {a: 1, b: 2},
    {a: 3, b: 8},
    {a: 9, b: 3, children: [
        {...}, {...}, {...}
    ]},
    {...},
    {..., children: [{}, {}, {}...]}
];

Are you experiencing scaling issues or are you just trying to future-proof it? — meder omuraliev, Mar 26 '16 at 02:30
@mederomuraliev Neither of those actually. I'm just trying to squeeze all the performance I can get since this codepath is quite expensive. — alexandernst, Mar 26 '16 at 02:32
you should give us a fiddle with a timer so that we can try to make it faster and share results with you easily. right now, you're asking for quite a bit of effort to help you with something that already works... — dandavis, Mar 26 '16 at 02:51

score 1 · Answer 1 · edited May 23 '17 at 11:45

1

Only thing i can immediately see is optimizing your loops by assigning .length to a variable

i.e.:

for (var i = 0, j = items.length; i < j; i++)

instead of

for (var i = 0; i < items.length; i++)

Here's an answer to another post for more insight: Javascript Optimizing Loops

edited May 23 '17 at 11:45

Community

1
1

answered Mar 26 '16 at 02:57

Dan D

2,493
15
23

1

Compared to everything else this would be a trivial micro-optimization, and these days the JS engines will optimize it out anyway. – Dave Newton Mar 26 '16 at 03:04
Last time I checked, this "optimization" was as fast as the "unoptimized" code on Chrome, and even a bit slower on Firefox. So I no longer recommend it. – Oriol Mar 26 '16 at 03:07
length buffering helped a lot on IE, which is already really slow, so if it's a wash other places, it should still be done. lots of cavemen still out there, and that optimization is painless... $0.02 – dandavis Mar 26 '16 at 03:12

score 1 · Answer 2 · answered Mar 26 '16 at 03:25

To remove the recursion, I use an array as stack and visit all node of "my_data" find out if there are children and push all children on stack. Then, remove the children and push the visited node in final result

var item;
var final_data = [];

function walk(items, level) {
    var stack = items;

    while (stack.length > 0) {
        item = stack.shift();
        if ("children" in item) {
            var x = Object.assign({}, item)
            var children = item.children;
            // console.log(children);
            for (var z = 0; z < children.length; z++) {
                stack.push(children[z]);
            }
        }
        delete item.children;
        final_data.push(item);
    }
}

walk(my_data, 0);
for (var i = 0; i < final_data.length; i++) {
    //console.log(final_data[i].a);
}

The last loop in snippet is for testing result, jsfiddle: https://jsfiddle.net/cleopart/hx7espr9/ — VinhNT, Mar 26 '16 at 03:27
I have tried with 2 level, it works, did you checkmy jsfiddle? https://jsfiddle.net/cleopart/hx7espr9/3/ — VinhNT, Mar 26 '16 at 11:10

score -1 · Answer 3 · answered Mar 26 '16 at 03:03

-1

If you're going for performance, yes, it could definitely be improved. The Object.assign is unnecessary, and Object creation and destruction is extremely inefficient in javascript. Gains from assigning length a variable would be negligible compared to the gains from removing this.

answered Mar 26 '16 at 03:03

Zane Hitchcox

936
1
9
23

2

There will be object creation no matter what-OP started clones are necessary, no? – Dave Newton Mar 26 '16 at 03:07
Not if he modifies the original object. – Zane Hitchcox Mar 26 '16 at 03:09
Original object shouldn't be modified in any way. – alexandernst Mar 26 '16 at 03:10
Ah, well, then, no – Zane Hitchcox Mar 26 '16 at 03:23
Just had an idea for this. Do `JSON.stringify`, then come up with some way of parsing the string. Then call `JSON.parse`. Or you could just call `JSON.parse(JSON.stringify(obj))` on the original object to copy it. Then, you continue parsing without worrying about modifying the original object and not creating new objects. – Zane Hitchcox Apr 06 '16 at 02:22

Optimizing nested objects walk

3 Answers3