Детерминированный алгоритм распределения дескрипторов

Question

Я пытаюсь найти эффективный детерминированный способ выделения 32-разрядного дескриптора таким образом, чтобы он работал бесконечно.Простой увеличивающий счетчик не будет работать, потому что в конечном итоге он будет зацикливаться.Расширение до 64-бит невозможно, поскольку значения будут использоваться в сетевом протоколе, который ожидает 32-битное значение.

Это для системы реального времени, поэтому она должна быть детерминированной и быстрой.Хотя это окажется в базе данных SQLite, я не могу просто проверить каждую клавишу методом перебора, например, после цикла обхода...

Я думаю, что мне нужно какое-то дерево диапазонов, которое знает обо всех ранее выделенных дескрипторах (заполнение этого при запуске - это нормально).Кажется, это распространенная проблема, но она не из тех, которые решаются boost или STL.

Есть какие-нибудь указания?

Редактировать:Некоторое дополнительное уточнение.Я хочу, чтобы в системе одновременно было что-то порядка 200 тыс. активных дескрипторов.Дескрипторы удаляются случайным образом.

Answer 1

Вы не можете выделить больше, чем 2 ^ 32.Но вы можете перераспределить использованные дескрипторы, если они освобождены, и проблема заключается в том, чтобы отслеживать свободные дескрипторы.

Дерево - хороший способ хранения свободных дескрипторов.Каждый узел имеет самый низкий и самый высокий дескриптор, левое поддерево содержит дескрипторы, которые меньше самого низкого, а правое поддерево содержит дескрипторы, которые больше самого высокого.

Примером может служить:

            6-9
            / \
           2   15
          / \
         0   4

Если дескриптор отпущен, он сохраняется в дереве.Например, если выпущено 10, дерево будет выглядеть следующим образом:

            6-10
            / \
           2   15
          / \
         0   4

Если дескриптор 5 отпущен, вы можете выбрать оптимизацию дерева, потому что 4 может быть добавлено к узлу 5-10 по мере необходимости.:

            5-10
            / \
           2   15
          / \
         0   4

Для:

            4-10
            / \
           2   15
          / 
         0  

Выделение дескриптора выполняет поиск конечного узла с 1 дескриптором и удаляет его из дерева.Если нет листьев с 1 ручкой, просто используйте лист и уменьшите ту сторону, которая не соединена с родительской:

         4-10
        /
      1-2

В приведенном выше примере мы выделяем 1, а не 2, потому что, если выделено 3, вы можете объединить его с 4, и вы хотите сохранить количество узлов как можно меньшим.

Ниже приведен алгоритм псевдокода.Некоторые части оставлены для читателя:

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

Если память не является проблемой, вы можете сохранить список свободных дескрипторов. Когда он выпущен, вы добавляете его обратно в конец списка бесплатных объявлений.

В начале вы можете добавить все идентификаторы в свободный список, но это будет неэффективно.

Оптимизация, которую вы можете сделать, заключается в том, что вы сохраняете значение, равное минимальному доступному идентификатору, а также свободный список. Поэтому, когда список пуст, вы добавляете несколько идентификаторов (начиная с минимального значения идентификатора, которое вы поддерживаете) в свободный список и обновляете минимальное значение идентификатора.

Answer 3

Если этот вопрос просто "как я могу быстро и безопасно рассчитать уникальное, не используемое в настоящее время число", то битовая таблица даст вам это.

Для порядка 200К уникальных чисел 200.000 / 8 = необходимое количество байтов = 25000, что просто не хватает 25КБ памяти для отслеживания.

Конечно, если вам нужно отслеживать данные, связанные с используемыми дескрипторами, в памяти, вам нужно что-то еще.

Еще одно решение, которое, вероятно, позволит быстрее получить новый дескриптор, заключается в сохранении стека неиспользуемых дескрипторов. Каждый раз, когда вам понадобится дескриптор, извлекайте его из стека.

Вы можете заполнить стек заданным числом, но алгоритм также будет таким, что если вы попытаетесь извлечь значение из пустого стека, вы просто сгенерируете новое, увеличивая постоянно увеличивающееся значение.

Поскольку вы говорите, что в любой момент времени у вас будет около 200 тыс. дескрипторов, этот стек никогда не должен превышать количество дескрипторов, поэтому вы можете легко справиться с этим с помощью массива. 32-разрядный стек 200 КБ будет занимать 800 000 байт, что составляет около 781 КБ памяти.