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

Question

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

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

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

Есть указатели?

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

Answer 1

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

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

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

Answer 2

Вы не можете выделить более 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 3

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

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

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

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

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

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