Is it more efficient to convert to string than to iterate an object to find something?-CodePudding

I have a dilemma of which case is more efficient.
I have a javascript array with this structure

elements = 
  [ { id: 'uuid',         children: [] } 
  , { id: 'uuid',         children: [] } 
  , { id: 'uuid',         children: 
      [ { id: 'uuid',     children: [] } 
      , { id: 'uuid',     children: 
          [ { id: 'uuid', children: [] } 
          , { id: 'uuid', children: [] } 
          ] 
        } 
      , { id: 'uuid',     children: [] } 
      ] 
    } 
  ]

To find a specific object, I have two ways of working, one is to iterate each element until I find it and the other is to convert it to string and if the id exists in the children, I enter the node

function findElementById(id_, elements){
for (el of elements){
    if(el.id == id_) return el
    if(JSON.stringify(el.children).includes(id_)) return findElementById(id, el.children)
}
}

function findElementById(id_, elements){
for (el of elements){
    if(el.id == id_) return el
    if(el.children.length > 0) result = findElementById(id, el.children)
    if (result) return result
}
}

It's efficient to convert to string to avoid entering nodes that will not return anything or in cases where the object is very large, converting to string uses a lot of resources.

CodePudding user response：

I suggest you maintain a flat, sorted array of nodes:

const flat = Array.from('12345678').map(x => ({ 'id': `uuid${x}`, 'children': [] }))

... and assemble a tree on top of that (this is equivalent to your elements):

const tree = Array.from('012').map(x => flat[x])
flat[2].children.push(flat[3], flat[4], flat[7])
flat[4].children.push(flat[5], flat[6])

Now so long as you keep the array sorted you can conduct a binary search on it using functions like:

const id_compare = (x, y) => (x.id > y.id) - (x.id < y.id)
const search = (tab, element, compare) =>
    function search_(min, max) {
       let x = min   (max - min >> 1)
       switch (compare(element, tab[x])) {
           case -1: return min < x && search_(min, x)
           case  0: return tab[x]
           case  1: return x < max && search_(x, max)
       }
   }(0, tab.length)

Due to unforeseen circumstances I can only postulate that this will be an order of magnitude faster than your first solution. I can't do any practical tests (beyond searching for and comparing all elements, and some 'rubbish', such as below) because I don't have a computer to test on; this is all based on theory (an O(log n) solution might be faster than an O(n) function