Algoritmo di allocazione deterministica dell'handle

Question

Sto cercando di trovare un modo deterministico efficiente di allocare un handle a 32 bit in modo tale che funzioni a tempo indeterminato. Un semplice contatore incrementale non funzionerà perché alla fine si ripeterà. L'estensione a 64 bit non è possibile perché i valori verranno utilizzati in un protocollo di rete che prevede un valore a 32 bit.

È per un sistema in tempo reale, quindi deve essere deterministico e rapido. Anche se finirà in un database SQLite, non posso limitarmi a testare la forza bruta dopo ogni giro, ad esempio ...

Penso che ciò di cui ho bisogno sia una specie di albero di portata che conosca tutti gli handle precedentemente allocati (compilare questo all'avvio va bene). Questo sembra essere un tipo comune (ish) di problema ma non è quello risolto da boost o STL.

Qualche puntatore?

Modifica: alcuni chiarimenti aggiuntivi. Sto cercando di avere qualcosa dell'ordine di 200k handle attivi nel sistema in qualsiasi momento. Le maniglie vengono eliminate su base casuale.

Answer 1

Non puoi allocare più di 2 ^ 32. Ma puoi riallocare gli handle usati se vengono rilasciati e il problema è tenere traccia degli handle gratuiti.

Un albero è un buon modo per memorizzare gli handle gratuiti. Ogni nodo ha una maniglia più bassa e una più alta, la sottostruttura sinistra contiene le maniglie che sono inferiori alla più bassa e la sottostruttura destra contiene le maniglie che sono maggiori della più alta.

Un esempio è:

            6-9
            / \
           2   15
          / \
         0   4

Se viene rilasciato un handle, questo viene archiviato nella struttura. Ad esempio, se viene rilasciato 10, l'albero appare come:

            6-10
            / \
           2   15
          / \
         0   4

Se viene rilasciato handle 5, puoi scegliere di ottimizzare l'albero perché 4 possono essere aggiunti al nodo 5-10 come wel:

            5-10
            / \
           2   15
          / \
         0   4

A:

            4-10
            / \
           2   15
          / 
         0  

L'allocazione di un handle, cerca un nodo foglia con 1 handle e lo rimuove dall'albero. Se non ci sono foglie con 1 maniglia, basta usare una foglia e decrementare il lato che non è collegato al genitore:

         4-10
        /
      1-2

Nell'esempio sopra allociamo 1 e non 2 perché se 3 viene rilasciato, puoi combinarlo con 4 e vuoi mantenere il numero di nodi più basso possibile.

Di seguito è riportato un algoritmo pseudocodice. Alcune parti sono lasciate al lettore:

Node = ( int lowest, highest; [Node] left, right)


Node.Allocate() 
  if TryFindLonelyLeaf(handle)    return handle;
  else
    return FindLeafHandle(NULL);

Node.TryFindLonelyLeaf(handle)
  if (left == NULL & right == NULL) 
    if (lowest == highest)
      handle == lowest;
      return TRUE;
    else
      return FALSE;
  if (left != NULL & left.TryFindLonelyLeaf(handle))
    if (left.lowest == handle) 
      left == NULL; // Free node
    return TRUE;
  elsif (right != NULL & right.TryFindLonelyLeaf(handle))
    if (right.lowest == handle)
       right = NULL; // Free node
    return TRUE;
  else
    return FALSE;

Node.FindLeafHhandle(parent)
  if (left == NULL & right == NULL) 
    if (parent == NULL | parent.right == this) 
      handle = lowest;
      lowest++;
    else
      handle = highest;
      highest--;
    return handle;
  else if (left != NULL) 
    return left.FindLeafHandle();
  else // right != NULL
    return right.FindLeafHandle();

Node.DeAllocate(handle) 
  Assert(handle<lowest or handle>highest);
  if (handle == lowest-1)
    lowest = CompactLeft(handle);
  elsif (handle == lowest+1)
    highest = CompactRight(handle); 
  elsif (handle<lowest)          
    if (left == NULL)
      left = (handle, handle, NULL, NULL);
    else
      left.DeAllocate(handle);
  elsif (handle>highest)
    if (right == NULL)
      right = (handle, handle, NULL, NULL);
    else
      right.DeAllocate(handle);
  else ERROR           

Node.CompactLeft(handle)
  if (highest == handle-1) 
    handle = lowest;
    // deallocate node and replace with left subtree
    return handle;
  elsif (right != NULL) 
    return right.CompactLeft(handle)
  else
    return handle;

Node.CompactRight(handle)
  if (lowest == handle+1) 
    handle = highest;
    // deallocate node and replace with right subtree
    return handle;
  elsif (left != NULL) 
    return left.CompactRight(handle)
  else
    return handle;

Answer 2

Se la memoria non è un problema, è possibile mantenere un elenco di handle gratuiti. Quando ne viene rilasciato uno, lo si aggiunge alla fine dell'elenco gratuito.

All'inizio, potresti aggiungere tutto l'id alla lista libera, ma sarà inefficiente.

L'ottimizzazione che potresti fare è mantenere un valore che sia l'id minimo disponibile, così come l'elenco gratuito. Pertanto, quando l'elenco è vuoto, aggiungi un numero di ID (a partire dal valore ID minimo che stai mantenendo) all'elenco gratuito e aggiorni il valore ID minimo.

Answer 3

Se questa domanda è solo "come posso calcolare rapidamente e in modo sicuro un numero unico, non attualmente utilizzato,", allora una tabella di bit ti darebbe.

Per l'ordine di 200 K di numeri univoci, 200.000 / 8 = numero di byte necessari = 25000, che è solo timido di 25 KB di memoria da tenere traccia.

Naturalmente, se devi tenere traccia dei dati associati agli handle in uso, in memoria, allora hai bisogno di qualcos'altro.

Un'altra soluzione, che probabilmente sarebbe più veloce per ottenere un nuovo handle, sarebbe quella di mantenere una pila di handle non utilizzati. Ogni volta che hai bisogno di un handle, estraine uno dallo stack.

Potresti eseguire il seeding dello stack con un numero impostato, ma l'algoritmo sarebbe anche tale che se provi a estrarre un valore dallo stack vuoto, ne generi semplicemente uno nuovo incrementando un valore sempre crescente.

Dal momento che dici che avrai circa 200K handle attivi in ??un dato momento, questo stack non dovrebbe mai aumentare di dimensioni rispetto a contenere quel numero di handle, quindi puoi facilmente gestirlo con un array. Uno stack da 200 KB a 32 bit consumerebbe 800.000 byte, circa 781 KB di memoria.