3

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 Apr 23 '18 at 16:10
  • 1
    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 Apr 23 '18 at 16:12
  • 1
    What are you trying to do? What do you mean "checks for children"? – Euphoric Apr 23 '18 at 16:32
  • 1
    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 Apr 24 '18 at 11:26
3

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.

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.