Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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 '12 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 '12 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 '12 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 '12 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 '12 at 9:07
show 3 more comments

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
But in theory the sequence would still get too long, right? –  romaninsh Apr 5 '12 at 9:38
1  
Maybe if we md5('1.0.3.....') it would give us identifiers of consistent length... –  romaninsh Apr 5 '12 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 '12 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 Apr 5 '12 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 '12 at 11:43
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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