2
\$\begingroup\$

I am using the following Depth-first search algorithm to compute value of a property called rotation_absolute based on previous values of rotation of parent elements recursively.

The result of the script is correct (open console to see the result) but I would like your code review regarding performance, considering that app.data could contained thousands of objects... how could I further improve my code?

Notes: I am targeting latest versions of Chrome and FireFox.

     var app = {
            getById: function (id) {
                var result;
                this.data.some(function (item) {
                    if (item.id === id) {
                        result = item;
                        return true;
                    } else {
                        return false;
                    }
                });
                return result;
            },
            findChildren: function (id) {
                var result = this.data.filter(function (item) {
                    if (item.parent === id) {
                        return true;
                    } else {
                        return false;
                    }
                });
                return result;
            },
            data: [
                {
                    id: 'root',
                    parent: '',
                    rotation: 0,
                    rotation_absolute: 0
                },
                {
                    id: 'a',
                    parent: 'root',
                    rotation: 10
                },
                    {
                        id: 'a-a',
                        parent: 'a',
                        rotation: 10
                    },
                    {
                        id: 'a-b',
                        parent: 'a',
                        rotation: 10
                    },
                        {
                            id: 'a-b-a',
                            parent: 'a-b',
                            rotation: 10
                        },
                            {
                                id: 'a-b-a-a',
                                parent: 'a-b-a',
                                rotation: 10
                            },
                                {
                                    id: 'a-b-a-a-a',
                                    parent: 'a-b-a-a',
                                    rotation: 10
                                },
                            {
                                id: 'a-b-a-b',
                                parent: 'a-b-a',
                                rotation: 10
                            },
                {
                    id: 'b',
                    parent: 'root',
                    rotation: 0
                },
                    {
                        id: 'b-a',
                        parent: 'b',
                        rotation: 10
                    },
                        {
                            id: 'b-a-a',
                            parent: 'b-a',
                            rotation: 10
                        },
                            {
                                id: 'b-a-a-a',
                                parent: 'b-a-a',
                                rotation: 10
                            },
                    {
                        id: 'b-b',
                        parent: 'b',
                        rotation: 10
                    },
            ],
            calculate: function () {
                var recursion = function (id) {
                    var children = this.findChildren(id);
                    var parent = this.getById(id);
                    children.forEach(function (item) {
                        if ('rotation_absolute' in item === false) {
                            item.rotation_absolute = 0;
                        }
                        item.rotation_absolute += item.rotation + parent.rotation_absolute;
                        recursion.call(this, item.id)
                    }, this);
                };

                recursion.call(this, 'root')
            },
        };
        app.calculate();
        console.clear();
        console.log(JSON.stringify(app.data));

\$\endgroup\$
  • \$\begingroup\$ Why do you use Array.some() within getById()? You don't do anything with the returned boolean value. Array.forEach() seems more appropriated to me. \$\endgroup\$ – michael.zech Mar 15 '16 at 10:51
2
\$\begingroup\$
            this.data.some(function (item) {
                if (item.id === id) {
                    result = item;
                    return true;
                } else {
                    return false;
                }
            });

I find such constructions weird, something about return true else return false always bothers me. In this case, there's not much you can do about it, best you could probably do is use an implicit else by removing the else:

            this.data.some(function (item) {
                if (item.id === id) {
                    result = item;
                    return true;
                }
                return false;
            });

            var result = this.data.filter(function (item) {
                if (item.parent === id) {
                    return true;
                } else {
                    return false;
                }
            });

Here, however, there's no reason to have this construction.

You can just return boolean comparisons like so:

            var result = this.data.filter(function (item) {
                return item.parent === id;
            });

For the calculate function... well, if you could restructure your data, that'd be nice. Right now you refer to each element by id, which means that you need unique ids throughout the entire list.

Depending on how accessing elements of the list works, you either have \$O(1)\$ for retrieving an element or \$O(n/2)\$. That is, either you can use the id to say "oh, that's entry number 35, let me see, one memory page fits 24 items, so I'd have to look at page 2, entry 11... there it is!" Whereas if you don't have such a translation ready, you're stuck with checking each item.

For 13 items, it does not matter. For 100 items, it does. 100 items accessed via direct access means you have 100 retrievals, 100 items accessed via linear search means you have 5050 retrievals (1+2+3+4...+100). Look up "triangular numbers" if you wanna see how bad it gets.

To fix this, you could do one of two things:

  1. Make it so that the id gives direct access. This could be done with hash functions or arrays or... look up data structures with \$O(1)\$ access.

  2. Make it so that the search space is smaller. For instance, instead of linking nodes together by ID, nest nodes via providing a children attribute containing more nodes. Then you only have to search in a sublist, meaning that you'd be searching in lists anywhere from 1 to 20% of your main list. Given the way access iterations scale, 5*20 is only 1050 iterations, compared to the 5050 we had earlier.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your time on this, do you see any improvement for function calculate() ? \$\endgroup\$ – GibboK Mar 15 '16 at 8:48
  • 1
    \$\begingroup\$ @GibboK only on a high level scale; I updated my answer but it's not a quick fix \$\endgroup\$ – Pimgd Mar 15 '16 at 9:16

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.