Algorithme déterministe d'affectation de handles

Question

J'essaie de trouver une manière déterministe efficace d'allouer un handle 32 bits de telle sorte qu'il fonctionne indéfiniment. Un simple compteur incrémentiel ne fonctionnera pas car il finira par tourner. L'extension à 64 bits n'est pas possible car les valeurs seront utilisées dans un protocole réseau qui attend une valeur de 32 bits.

Pour un système en temps réel, il doit être déterministe et rapide. Bien que cela finisse dans une base de données SQLite, je ne peux pas tester chaque force après chaque boucle par exemple ...

Je pense que j'ai besoin d'une sorte d'arborescence qui connaît toutes les poignées précédemment allouées (peupler cela au démarrage est très bien). Cela semble être un problème commun (ish) mais ce n'est pas un problème résolu par boost ou par le STL.

Des pointeurs?

Modifier: Quelques précisions supplémentaires. Je cherche à avoir quelque chose de l'ordre de 200k poignées actives dans le système à la fois. Les poignées sont supprimées au hasard.

Answer 1

Vous ne pouvez pas allouer plus de 2^32. Mais vous pouvez réaffecter les poignées utilisées si elles sont libérées et le problème est de garder une trace des poignées libres.

Un arbre est un bon moyen de stocker les poignées libres. Chaque nœud a un handle le plus bas et un handle le plus haut, le sous-arbre de gauche contient les handles qui sont inférieurs au plus bas et le sous-arbre de droite contient les handles qui sont supérieurs au plus haut.

Un exemple est:

  6-9 
      /\ 
      2 15 
     /\ 
     0 4 

Si une poignée est relâchée, elle est stockée dans l'arbre. Par exemple, si 10 est libéré, l'arbre ressemble à:

  6-10 
      /\ 
      2 15 
     /\ 
     0 4 

Si la poignée 5 est libéré, vous pouvez choisir d'optimiser l'arbre parce que 4 peut être ajouté au noeud 5-10 comme wel:

  5-10 
      /\ 
      2 15 
     /\ 
     0 4 

pour:

  4-10 
      /\ 
      2 15 
     /
     0 

l'attribution d'une poignée, recherche un nœud feuille avec 1 poignée et il enlève de l'arbre. S'il n'y a pas de feuilles avec 1 poignée, il suffit d'utiliser une feuille et décrémenter le côté non connecté au parent:

  4-10 
     /
     1-2 

Dans l'exemple ci-dessus nous allouons 1 et non 2 parce que si 3 est libéré, vous pouvez combinez-le avec 4 et vous voulez garder le nombre de nœuds aussi bas que possible.

Voici un algorithme de pseudocode. Certaines parties sont laissées au lecteur:

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

Si la mémoire n'est pas un problème, vous pouvez gérer une liste de descripteurs libres. Quand on est libéré, on l'ajoute à la fin de la liste libre. Au début, vous pouvez ajouter tous les identifiants à la liste libre, mais ce sera inefficace.

L'optimisation que vous pourriez faire est de maintenir une valeur qui est l'identifiant minimum disponible, ainsi que la liste libre.Ainsi, lorsque la liste est vide, vous ajoutez un certain nombre d'identifiants (à partir de la valeur d'identifiant minimale que vous maintenez) à la liste libre et mettez à jour la valeur d'identifiant minimale.

Answer 3

Si cette question est simplement «comment puis-je calculer rapidement et en toute sécurité un numéro unique actuellement inutilisé», un tableau de bits vous le donne.

Pour l'ordre de 200K nombres uniques, 200.000/8 = nombre d'octets requis = 25000, ce qui est juste timide de 25KB de mémoire à garder la trace.

Bien sûr, si vous avez besoin de garder une trace des données associées aux handles en cours d'utilisation, en mémoire, vous avez besoin d'autre chose.

Une autre solution, qui serait probablement plus rapide pour passer une nouvelle poignée, consisterait à conserver une pile de poignées inutilisées. Chaque fois que vous avez besoin d'un handle, en retirer un de la pile.

Vous pourriez graver la pile avec un nombre défini, mais l'algorithme serait également de sorte que si vous essayez d'enlever une valeur de la pile vide, vous en générez simplement une nouvelle en incrémentant une valeur toujours croissante. Puisque vous dites que vous aurez environ 200K poignées en direct à tout moment, cette pile ne devrait jamais devenir plus grande que de contenir autant de poignées, vous pouvez donc facilement gérer cela avec un tableau. Une pile de 200 Ko de 32 bits consommerait 800 000 octets, soit environ 781 Ko de mémoire.