Algorithm for determining derivative algorithms

I am trying to find an efficient deterministic way to allocate a 32 bit descriptor in such a way that it runs indefinitely. A simple tally counter won't work because it will end up going around. Expansion to 64 bits is not possible because the values ​​will be used in the network protocol, which expects a 32-bit value.

This is for a real-time system, so it must be deterministic and fast. While this will end up in a SQLite database, I can't just drag the power command every key after the loop, like ...

I think I need some sort of range tree that knows about all the previously allocated handles (filling this out on startup is fine). This appears to be a common (ish) problem, but it is not one that is solved with boost or STL.

Any pointers?

Edit: some additional clarification. At any given moment, I want to have something like 200k active pens in the system. The handles are removed at random.

+2


source to share


3 answers


You cannot allocate more than 2 ^ 32. But you can reallocate used handles if released and the problem is keeping track of free handles.

Wood is a good way to store loose handles. Each node has the lowest and highest descriptor, the left subtree contains descriptors that are less than the minimum, and the right subtree contains descriptors that are larger than the highest.

Example:

            6-9
            / \
           2   15
          / \
         0   4

      

If the descriptor is released, it is stored in the tree. For example, if 10 is released, the tree looks like this:

            6-10
            / \
           2   15
          / \
         0   4

      

If descriptor 5 is freed, you can opt to optimize the tree, because 4 can be added to 5-10 node, and also:

            5-10
            / \
           2   15
          / \
         0   4

      



To:

            4-10
            / \
           2   15
          / 
         0  

      

Allocate a descriptor, find a leaf node with 1 descriptor and remove it from the tree. If there are no 1-handle leaves, just use a leaf and shrink the side that is not parent-related:

         4-10
        /
      1-2

      

In the example above, we are allocating 1, not 2, because if 3 is freed, you can concatenate it with 4, and you want the number of nodes to be as low as possible.

Below is the pseudocode algorithm. Some parts are left for the reader:

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;

      

+3


source


If memory is not an issue, you can keep a list of free descriptors. When one of them is released, you add it back to the end of the free list.

In the beginning, you can add all ids to the free list, but this will be ineffective.



The optimization you can do is that you keep a value that is the minimum identifier as well as a free list. So when the list is empty, you add the number of ids (starting with the minimum id value that you support) to the free list and update the minimum id value.

+3


source


If the question is simply "how can I quickly and safely compute a unique, currently unused number," then a bittable will give you that.

For about 200K unique numbers, 200,000 / 8 = number of bytes needed = 25,000, which is just a shy 25KB of memory to keep track of.

Of course, if you need to keep track of usage descriptor-related data in memory, you need something else.

Another solution that would probably be faster to get a new handle would be to keep a stack of unused handles. Every time you need a handle, push it onto the stack.

You can align the stack with a given number, but the algorithm will also be such that if you try to pop a value off the empty stack, you just create a new one, incrementing the ever increasing value.

Since you say that you will have about 200k realtime handles at any given time, this stack should never grow larger than it contains many handles, so you can easily deal with this with an array. A 32-bit 200K stack will consume 800,000 bytes, about 781 KB of memory.

0


source







All Articles