Generazione economica di ID univoci gerarchici

4

La mia applicazione sta costruendo una struttura gerarchica come questa:

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

in altre parole, è un albero di nodi, in cui ogni nodo potrebbe avere elementi figlio e identificatore univoco che chiamo "id". Quando viene aggiunto un nuovo figlio, ho bisogno di generare un identificatore univoco per questo, tuttavia ho due problemi:

  • gli identificatori stanno diventando troppo lunghi
  • l'aggiunta di molti bambini è più lenta, poiché ho bisogno di trovare il primo ID disponibile

Il mio requisito è:

  • nome di un bambino X deve essere determinato solo dallo stato nei loro antenati
  • Quando re-generi albero con lo stesso contenuto, gli ID devono essere uguali

o in altre parole, quando abbiamo i nodi A e B, la creazione di child in A, non deve influire sul nome dato ai figli di B.

So che un modo per ottimizzare sarebbe introdurre il contatore in ogni nodo e aggiungerlo ai nomi che risolveranno il mio problema di prestazioni, ma non risolverà il problema con gli "identificatori lunghi".

Potresti suggerirmi l'algoritmo per ottenere rapidamente nuovi ID?

    
posta romaninsh 05.04.2012 - 10:43
fonte

1 risposta

3

se i bambini sono ordinati, puoi utilizzare il seguente schema:

  • stringa vuota indica la radice
  • 1.0.3 indica il quarto figlio del primo figlio del secondo figlio della radice.

È breve, ti permette di recuperare un nodo dal suo ID, è unico ed è gerarchico. È una specie di albero dei prefissi .

    
risposta data 05.04.2012 - 11:10
fonte

Leggi altre domande sui tag