algoritmo de alocação de alça determinista

https://stackoverflow.com/questions/1413193

06-07-2019
|

Pergunta

Eu estou tentando encontrar uma maneira determinista eficiente de alocar um identificador de 32 bits, de tal forma que ele irá operar indefinidamente. Um simples incremento contador não vai funcionar porque ele acabará por laço em torno. Estendendo-se a 64-bits não é possível, porque os valores serão usados ??num protocolo de rede que está à espera de um valor de 32 bits.

É para um sistema em tempo real assim que tem que ser determinista e rápido. Embora ele vai acabar em um banco de dados SQLite que eu possa testar a força não apenas bruta cada tecla depois de laço em torno, por exemplo ...

Eu acho que o que eu preciso é uma espécie de árvore de intervalo que sabe sobre todas as alças anteriormente atribuídos (preencher esta no arranque é bom). Este parece ser um comum (ish) tipo de problema, mas não é aquele que é resolvido por impulso ou a STL.

Os ponteiros?

Edit: Alguns esclarecimentos adicionais. Eu estou olhando para ter algo da ordem de 200 mil alças ativos no sistema a qualquer momento. Alças são eliminados de forma aleatória.

Solução

Você não pode alocar mais de 2 ^ 32. Mas você pode realocar alças usados ??se eles são liberados e o problema é manter o controle das alças livres.

Uma árvore é uma boa maneira de armazenar as alças livres. Cada nó tem um menor e uma maior alça, a sub-árvore esquerda contém as alças que são menores do que as de baixo e sub-árvore direita contém as alças que são maiores do que o maior.

Um exemplo é:

Se um identificador é liberado, ele é armazenado na árvore. Por exemplo, se 10 for lançado, os olhares de árvores como:

Se pega 5 é lançado, você pode escolher para otimizar a árvore porque 4 pode ser adicionado ao nó 5-10, bem assim:

Para:

A alocação de um punho, procura por um nó de folha com uma alça e remove-lo a partir da árvore. Se não houver folhas com uma alça, basta usar uma folha e diminuir o lado que não está ligado ao pai:

         4-10
        /
      1-2

No exemplo acima, alocamos 1 e não 2, porque se 3 é lançado, você pode combiná-lo com 4 e quiser manter o número de nós o mais baixo possível.

Abaixo está um algoritmo pseudocódigo. Algumas peças são deixados para o leitor:

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;

Outras dicas

Se a memória não é um problema, então você pode manter uma lista de identificadores livres. Quando um é lançado, você adicioná-lo de volta para o final da lista livre.

No início, você pode adicionar todo o id à lista livre, mas será ineficiente.

A otimização que você poderia fazer é que você mantenha um valor que é o ID mínimos disponíveis, bem como a lista livre. Então, quando a lista estiver vazia, você adicionar um número de ids (a partir do valor id mínimo você está mantendo) à lista livre e atualizar o valor id mínimo.

Se esta questão é apenas "como eu posso rapidamente e com segurança, calcular um número único, não-atualmente utilizado,", em seguida, um pouco mesa-lhe daria isso.

Para o fim de 200K números exclusivos, 200.000 / 8 = número de bytes necessários = 25000, que é apenas tímido de 25KB de memória para manter o controle de.

Claro que, se você precisa manter o controle de dados associados com alças em uso, na memória, então você precisa de algo mais.

Outra solução, que provavelmente seria mais rápido para obter uma nova alça através, seria a de manter uma pilha de alças não utilizadas. Cada vez que você precisar de uma alça, um pop da pilha.

Você pode semear a pilha com um número definido, mas o algoritmo também seria de modo que se você tentar pop um valor fora da pilha vazia, você simplesmente gerar uma nova incrementando um valor cada vez maior.

Uma vez que você diz que vai ter cerca de 200K alças vivem em um determinado momento, esta pilha nunca deve crescer mais do que segurando que muitos número de identificadores, então você pode facilmente lidar com isso com uma matriz. Uma pilha 200K 32-bit iria consumir 800.000 bytes, cerca de 781KB de memória.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow