Inexpensive generation of hierarchical unique IDs
- by romaninsh
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?
