5

My application is building a hierarchical structure like this:

root = { 
  'id': 'root',
  'children': [ {
    'name': 'root_foo',
    'children': []
  }, {
    'id': 'root_foo2',
    'children': [ {
      'id': 'root_foo2_bar',
      'children': []
      } ]
  } ]
}

in other words, it's a tree of nodes, where each node might have child elements and unique identifier I call "id". When a new child is added, I need to generate a unique identifier for it, however I have two problems:

  • identifiers are getting too long
  • adding many children takes slower, as I need to find first available id

My requirement is:

  • naming of a child X must be determined only from the state in their ancestors
  • When I re-generate tree with same contents, the IDs must be same

or in other words, when we have nodes A and B, creating child in A, must not affect the name given to children of B.

I know that one way to optimize would be to introduce counter in each node and append it to the names which will solve my performance issue, but will not address the issue with the "long identifiers".

Could you suggest me the algorithm for quickly coming up with new IDs?

Improve this question
8
  • Can you just generate a GUID as an ID? I know it's long, but it doesn't rely on a thing.
    – Vic
    Apr 5, 2012 at 8:48
  • 1
    Can you expand on the long identifiers issue? What is considered long and why is it a problem?
    – Tamás Szelei
    Apr 5, 2012 at 8:48
  • @Vic: The thing is, when I re-generate the tree (I use this in web application) then identifiers must be the same. I added this to my question.
    – romaninsh
    Apr 5, 2012 at 8:50
  • 2
    Also, you are probably building the tree in a deterministic order, why not just use a counter as an id?
    – Tamás Szelei
    Apr 5, 2012 at 9:05
  • 1
    how about creating id only when it's necessary, e.g. on the fly. each element in this structure already has unique access path e.g 0-1-1 representing position in each subsequent children array.
    – jancha
    Apr 5, 2012 at 9:07

1 Answer 1

Reset to default
4

if children are ordered, then you can use the following schema:

  • empty string means the root
  • 1.0.3 means the fourth child of the first child of the second child of the root.

It is short, allows you to fetch a node from its ID, is unique, and is hierachical. It is a kind of prefix tree.

Improve this answer
8
  • But in theory the sequence would still get too long, right?
    – romaninsh
    Apr 5, 2012 at 9:38
  • 1
    Maybe if we md5('1.0.3.....') it would give us identifiers of consistent length...
    – romaninsh
    Apr 5, 2012 at 9:43
  • Yes, that's a good idea. I was going to suggest something along those lines (if the counter is not sufficient for some reason).
    – Tamás Szelei
    Apr 5, 2012 at 9:48
  • 1
    @romaninsh yes, hashing will give you consistant length. but you will loose the ability to use the name to fetch the item. It depends on what you want to do with this id.
    – Simon Bergot
    Apr 5, 2012 at 9:56
  • Such names can obviously be shortened. For instance, using Base-36, and by dropping the .. So 1A2 instead of 1.10.2.
    – MSalters
    Apr 5, 2012 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.