1w pieces of data were lost in the background

Thousands of calculations, or did not escape, the background is really tens of thousands of data lost to the front end. Well, good thing it’s not 10w. As follows, the background returns something like this:

const flatArr = [
  { id: '001'.name: Nodes' 1 ' },
  { id: '0011'.parentId: '001'.name: '1-1 nodes' },
  { id: '00111'.parentId: '0011'.name: 'the 1-1-1 nodes' },
  { id: '002'.name: Nodes' 2 '},]Copy the code

As you can see, this is actually a tiled array, and our requirement is to render this data in the cascading selector of the Element-UI, which receives the following tree structure:

let options = [
  {
    value: 'zhinan'.label: 'guide'.children: [{value: 'shejiyuanze'.label: 'Design Principles'.children: [{value: 'yizhi'.label: 'consistent' },
          { value: 'fankui'.label: 'feedback'}],}]}]Copy the code

Dude, that’s what I need to turn a tiled array into a tree!

A fierce operation such as tiger, without saying anything to write recursion.

recursively

Finished, code concise, clear thinking, a run, what? The page stuck, console.time() calculated, and it took about 18s to figure out the tree structure we needed.

I thought to myself, this is tens of thousands of pieces of data, and every time I recursively look for the children of the parent node, I have to go through the array once, which is time-consuming! And the calculation time has obviously led to the page card, this method is certainly not desirable, then, there is no better plan?

Non-recursive

We use the id of the current node as the key to save the reference information of the corresponding node, and update the children information of the objMap every time when traversing the group, so that all the nodes and their children are preserved in the objMap. Most importantly, All we have to do is walk through the array once, in order n time. Using this method, the calculation time only takes 60ms!

conclusion

  • Recursion: every time you recurse to find the children of the current node, you need to walk through the array again. The time complexity is O(nlogn).
  • Non-recursive mode: search for child nodes from the root node down, save the information of each node and its child nodes by Map, the child nodes save the reference on the Map, the child nodes of each node can be found by ID in the Map, the time complexity is O(n)

Let’s look at a comparison:

It can be seen from the trend of time complexity increasing with data volume above that, when the data gets bigger and bigger, the time of recursive algorithm will be much greater than that of non-recursive algorithm. Therefore, when the amount of data is small, the recursive algorithm has some advantages, but when the data is large enough, the recursive approach will become more and more obvious, using the non-recursive algorithm is much faster!

Finally, I have to say that through this comparison, we can also obviously feel the importance of the algorithm. Different implementation methods can vary greatly, which is worthy of attracting the attention of every developer to the algorithm!