2

I have an array of objects. Each object looks like this:

{text: 'foo': level: N: children: M}

Both N and M are numbers. N represents how "deep" is located the object (think about the entire array as if it was a representation of a tree). M is the total number of children that the item has. Total means the sum of all nodes and leafs of all sub-levels.

The objects in the array that I have don't contain the children property and I must calculate it.

Example of "calculated" data:

{text: 'A': level: 0: children: 0}
{text: 'B': level: 0: children: 1}
{text: 'C': level: 1: children: 0}
{text: 'D': level: 0: children: 2}
{text: 'E': level: 1: children: 1}
{text: 'F': level: 2: children: 0}

A
B
|--C
D
|--E
   |--F

I could easily do a for loop, and then iterate one more time over the items, starting at the current position in the array and count the children (based on the level property), but I feel like this is not the best (as in "the fastest") way to do it.

How else could I do it?

Just to make sure nobody posts "worse" code than what I currently have, this is what I have:

for (var i = 0; i < data.length; i++) {
    var item = data[i];

    for (var j = i + 1; j < data.length; j++) {
        if (item.level < data[j].level) {
            item.children++;
        } else {
            break;
        }
    }
}
alexandernst
  • 14,352
  • 22
  • 97
  • 197

4 Answers4

2

In your current example you can't calculate children at all, because your data don't show parent/children relations. level:1 for text: 'C', for example, have no data if it should be attached (i.e. increase children counter) to A, B or D.

If you mean, but forgot to mention that child object should be attached to whatever closest parent was recently mentioned, then just keep an array where each entry would correspond to reference to last seen parent-element of that level and modify it's chlildren property with += directly after reading each new line.

Oleg V. Volkov
  • 21,719
  • 4
  • 44
  • 68
  • A and B are at the same level, so C can't be children of both. It can be a child only of B. So B's children count should be incremented. – alexandernst Feb 09 '16 at 15:27
  • RE to your edit: I can't do that because I'd won't have a reference to `D` when I'm on the `F` row. I'd be able to increment only `E`. Said in another way, I can't increment backwards and upwards in the tree. – alexandernst Feb 09 '16 at 15:29
  • "keep an array". When reading entry with `level: 2`, you will add children to two entries: `known_parents[0].children++; known_parents[1].children++;` In loop, of course, not verbatim like this. – Oleg V. Volkov Feb 09 '16 at 15:31
1

This is the answer that I think @Oleg V. Volkov suggested in his comment. I think it is a very good solution to the problem & very fast since you only look at each element 1 time. However, the down side is that it might be more memory intensive while it's calculating because of the array of parents.

function countChildren(tree) {
    var currentParents = [];

    for (var i = 0; i < tree.length; i++) {
        // Initialize value of children
        tree[i].children = 0;

        if (i == 0) {
            continue;
        }

        // Find if the level increased, decreased, or stayed the same.
        var levelChange = tree[i].level - tree[i-1].level;

        // If level increased (by 1)
        if (levelChange == 1) {
            // Add previous element to list of parents
            currentParents.push(tree[i-1]);

        // If level decreased by 'x'
        } else if (levelChange < 0) {
            // Remove 'x' number of elements from the end of the list of parents
            for (var j = 0; j > levelChange; j--) {
                currentParents.pop();
            }
        }

        // Increase the number of children for all parents
        for (var j = 0; j < currentParents.length; j++) {
            currentParents[j].children++;
        }
    }
}
4castle
  • 32,613
  • 11
  • 69
  • 106
  • I can tell you haven't even tested that code :) You mixed strong typed syntax (`for (int i...`) and you mixed a few leves of `i`. – alexandernst Feb 09 '16 at 18:10
  • Forgive me, but you never actually provided sample data for me to work with, so I just programmed it conceptually. – 4castle Feb 09 '16 at 18:47
  • The data is in my question. Look at the `Example of calculated data` and just remove the `children` property. – alexandernst Feb 09 '16 at 18:59
  • Ok, I used your data, and I can confirm that this algorithm works correctly now. Also, I deleted that other answer because of your edit, because yes, it's essentially the same as what you use now. However, using the algorithm that I suggested with the nested objects is still the most elegant because it is least prone to malformed data. (such as skipping over a level). Also it would take much less code to do other things like find parents or add new elements. Given your use case, it may be unsuitable, but for most situations it is the best way to approach this kind of nested data. – 4castle Feb 09 '16 at 22:38
  • I de-selected your answer as the right one because after running some tests it turns out my solution is faster. Do you happen to know why would that be? – alexandernst Feb 10 '16 at 15:29
  • Can you tell me how long yours took vs how long mine took? That will help narrow down what it could be. Also, could you try testing the nested data answer? Because if it's faster, and the recursion is still a problem, you may be able to create a way for it to limit the number of recursive calls before it decides to analyze a deep portion separately. – 4castle Feb 11 '16 at 00:12
  • Mine takes anywere from 0.31 to 0.39 ms, yours takes anywhere from 0.45 to 0.55ms in a random dataset of 300 elements. I think analyzing recursively until a certain limit and then falling back to some other method will create even more performance loss. – alexandernst Feb 11 '16 at 00:39
  • What purpose does this algorithm actually serve? Why would you be using random datasets? And why do you need it to be faster? Is even 1 second too long? Also, why aren't you doing a calculation this big on a server? – 4castle Feb 11 '16 at 04:40
  • The 300 elements dataset is just an example to test the algo. The daata is created and managed at the client side, so I just can't process it on the server. And I need it to be faster because that will speed up the work process. – alexandernst Feb 11 '16 at 11:04
1

This is a different approach, despide all other solutions, starting from the bottom.

The advantage is, whenever a smaller level is reached, the sum is taken and the actual level accumulator is set to zero.

This solution features only one loop and an array count for the level accumulation.

I made a bigger test with this data (exception of property children, which is the result of the algorithm).

{ text: 'A', level: 0, children:  0 },    // A
{ text: 'B', level: 0, children:  1 },    // B
{ text: 'C', level: 1, children:  0 },    //   C
{ text: 'D', level: 0, children:  3 },    // D
{ text: 'E', level: 1, children:  2 },    //   E
{ text: 'F', level: 2, children:  0 },    //     F
{ text: 'F', level: 2, children:  0 },    //     G
{ text: 'H', level: 0, children: 18 },    // H
{ text: 'I', level: 1, children:  5 },    //   I
{ text: 'J', level: 2, children:  1 },    //     J
{ text: 'K', level: 3, children:  0 },    //       K
{ text: 'L', level: 2, children:  2 },    //     L
{ text: 'M', level: 3, children:  1 },    //       M
{ text: 'N', level: 4, children:  0 },    //         N
{ text: 'O', level: 1, children: 10 },    //   O
{ text: 'P', level: 2, children:  9 },    //     P
{ text: 'Q', level: 3, children:  7 },    //       Q
{ text: 'R', level: 4, children:  5 },    //         R
{ text: 'S', level: 5, children:  2 },    //           S
{ text: 'T', level: 6, children:  0 },    //             T
{ text: 'U', level: 6, children:  0 },    //             U
{ text: 'V', level: 5, children:  0 },    //           V
{ text: 'W', level: 5, children:  0 },    //           W
{ text: 'X', level: 4, children:  0 },    //         X
{ text: 'Y', level: 3, children:  0 },    //       Y
{ text: 'Z', level: 1, children:  0 },    //   Z


var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }],
    i = data.length,
    count = [];
 
while (i--) {
    if (data[i].level > 0) {
        count[data[i].level - 1] = (count[data[i].level - 1] || 0) + (count[data[i].level] || 0) + 1;
    }
    data[i].children = count[data[i].level] || 0;
    count[data[i].level] = 0;
}

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');

Version with prefilled array count (no checks for undefined) and a variable for the level.

var data = [{ text: 'A', level: 0 }, { text: 'B', level: 0 }, { text: 'C', level: 1 }, { text: 'D', level: 0 }, { text: 'E', level: 1 }, { text: 'F', level: 2 }, { text: 'F',level: 2 }, { text: 'H', level: 0 }, { text: 'I', level: 1 }, { text: 'J', level: 2 }, { text: 'K', level: 3 }, { text: 'L', level: 2 }, { text: 'M', level: 3 }, { text:'N', level: 4 }, { text: 'O', level: 1 }, { text: 'P', level: 2 }, { text: 'Q', level: 3 }, { text: 'R', level: 4 }, { text: 'S', level: 5 }, { text: 'T', level: 6 }, {text: 'U', level: 6 }, { text: 'V', level: 5 }, { text: 'W', level: 5 }, { text: 'X', level: 4 }, { text: 'Y', level: 3 }, { text: 'Z', level: 1 }],
    i = data.length, l,
    count = Array.apply(null, { length: 50 }).map(function () { return 0; });
 
while (i--) {
    l = data[i].level;
    if (l) {
        count[l - 1] += count[l] + 1;
    }
    data[i].children = count[l];
    count[l] = 0;
}

document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • Very nice! Will that work if the last item of the array is/isn't at level 0? I believe "yes", because of how you wrote your example data. – alexandernst Feb 10 '16 at 14:26
  • @alexandernst, obviously yes. – Nina Scholz Feb 10 '16 at 14:29
  • Ok, I tested your solution. It does output the correct values, but it's slower than what I currently have (the solution in my question). Do you know why could it be? – alexandernst Feb 10 '16 at 15:27
  • you can prefill the count array, if you know the depth. the assignment of `l = data[i].level;` should make it faster. please see edit., if that does not help a reverting of the original array should make it faster, the the iterater should go up. – Nina Scholz Feb 10 '16 at 15:45
  • I ran more tests, but this keeps being slower than my solution. – alexandernst Feb 10 '16 at 16:02
  • and what is your solution? – Nina Scholz Feb 10 '16 at 16:06
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/103123/discussion-between-nina-scholz-and-alexandernst). – Nina Scholz Feb 10 '16 at 16:08
0

The only way I can think of to do this without a for loop would require you to reform your tree structure. JavaScript objects can be nested, and so I would suggest using a format such as:

[
    {
        text: 'A',
        children: []
    },
    {
        text: 'B',
        children: 
        [
            {
                text: 'C',
                children: []
            }
        ]
     },
     {
         text: 'D',
         children:
         [
             {
                 text: 'E',
                 children:
                 [
                     {
                         text: 'F',
                         children: []
                     }
                 ]
             }
         ]
     }
]

Then for each object, the formula for "total number of children" would be something like:

function countChildren(obj) {
    var count = obj.children.length;
    for (int i = 0; i < children.length; i++) {
        count += countChildren(children[i]);
    }
    return count;
}
4castle
  • 32,613
  • 11
  • 69
  • 106
  • This won't count nested children. – alexandernst Feb 09 '16 at 15:43
  • @alexandernst Good spot! I fixed it so that it executes recursively. – 4castle Feb 09 '16 at 15:48
  • This is pretty much the same thing as what I have, just that instead of a nested for loop you solved it with a recursive function. I doubt there is any performance improvement with this. – alexandernst Feb 09 '16 at 15:49
  • @alexandernst Yeah, this is such a simple task, that there really aren't going to be many differences between answers. This is the most elegant solution though in my opinion. – 4castle Feb 09 '16 at 15:56
  • Your solution will work only for small subsets of data. The amount of data I'm working with will easily exceed the recursion limit of node/chrome. Hence, I can't see how this is the most elegant solution. – alexandernst Feb 09 '16 at 15:58
  • You should include that in your question. But that's not likely, unless you have elements where the 'level' is >500 (where safari crashes). The recursive part only gets called when it's going 'down' a level on the tree, not when it's going 'sideways'. http://stackoverflow.com/questions/2805172/what-are-the-js-recursion-limits-for-firefox-chrome-safari-ie-etc – 4castle Feb 09 '16 at 16:10
  • I know how recursion works, and yes, I do have +500 (in fact, +10.000) nested elements. – alexandernst Feb 09 '16 at 16:11
  • Do you mean that the elements are nested that many times? Or that there are that number of total elements. Once again, the recursive part will only blow up if you have {text: 'A', children: [{text: 'B',children: [{text: 'C' children: [... (thousands of levels deep) ... {text: 'X', children: []]... (thousands of closing brackets)] – 4castle Feb 09 '16 at 16:14
  • Once again, I know how recursion works and how recursion breaks. And once again, I have +10.000 nested elements. – alexandernst Feb 09 '16 at 16:15
  • Both Opera & Chrome can handle recursion stacks that large. What are your compatibility requirements? – 4castle Feb 11 '16 at 04:43
  • According to http://stackoverflow.com/questions/2805172/what-are-the-js-recursion-limits-for-firefox-chrome-safari-ie-etc only Chrome will handle such a deep recursion. My compaatibility requirements are "make it work with the latest version of every major browser". – alexandernst Feb 11 '16 at 11:07