What is best practice for handling mapping arbitrary depth in arrays?

Question

I have a set of data:

id | name     | parentid
------------------------
1  | parent   | 0
2  | child    | 1
3  | child    | 1
4  | parent   | 0
5  | child    | 4
6  | subchild | 5
7  | child    | 4

Which I can map to a hierarchy that looks like:

1   parent   
2   |-- child    
3   |-- child    
4   parent   
5   |-- child    
6       |-- subchild 
7   |-- child

At the moment, I'm using a recursive function that checks for children, but this is really slow.

function dothings(currentid) {
  //do stuff for item

  //check if anything has a parentid of currentid
  if (let children = checkforchildren(currentid) > 0) {
    foreach(children as child) {
      dothings(child['id']);
    }
  }
}

Is there a best practice when working with data that needs to be mapped into an arbitrarily deep array?

_{(If it matters, I'm using MySQL and PHP to handle this. I can provide more information specific to my use case if that's necessary, but I am looking for a best practice here, not just optimization debugging.)}

So are you saying that recursion is in fact the best way to handle the situation? — amflare
– amflare, Commented Apr 23, 2018 at 16:10
A recursive data type maintains the parent/child relationships for you. If you use references, you can have it both ways: you can maintain a flat list and a hierarchical list, both pointing to the same collection of items. Read the Wikipedia article. — Robert Harvey
– Robert Harvey, Commented Apr 23, 2018 at 16:12
What are you trying to do? What do you mean "checks for children"? — Euphoric
– Euphoric, Commented Apr 23, 2018 at 16:32
Have you investigated the actual cause of it being slow? Do you have a huge amount of nodes in your tree? Or do you have some time consuming operation you do for each node? Or maybe your actual code is not efficiently handling the recursive aspect of the tree? — Jonathan van de Veen
– Jonathan van de Veen, Commented Apr 24, 2018 at 11:26

user1118321 · Accepted Answer · 2018-04-25 05:23:21Z

Just because the data is stored in one format doesn't mean you have to hold it in memory in that format. Generally for a tree-like structure, rather than using an array, it would be stored as a tree. Each parent node would have a list of children nodes. This eliminates the need to search all the nodes to figure out which ones have the parent you're currently working with. So the data would look something like this in memory:

id | name     | children
------------------------
 1 | parent   | 2, 3
 2 | child    | 0
 3 | child    | 0
 4 | parent   | 5, 7
 5 | child    | 6
 6 | subchild | 0
 7 | child    | 0

Now your loop becomes

function dothings(currentid) {
  //do stuff for item

  foreach(children as child) {
      dothings(child['id']);
  }
}

We've removed the linear search of all nodes to find the children of each node.

Stack Exchange Network

What is best practice for handling mapping arbitrary depth in arrays?

1 Answer 1

Your Answer

Hot Network Questions

What is best practice for handling mapping arbitrary depth in arrays?

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions