Efficiently select a available number within a range

user_16571119 0
Viewed 99

I need to use and recycle ids(ints) within a range say from 1 to 20million.

what is the most efficient way to do this?

Somethings i tried.

  1. Generate a running sequence of numbers from 1 to k and store in a map. after k numbers if lets say if id 2 becomes free we delete it from the map. And continue our next id from k+1 (it will be good if i can choose the id that was freed from the beginning(2) instead of k+1. how can i do this ? )

  2. Generate random numbers in between range 1 to 20 million and check if its already used with a map lookup, if yes, choose another random number or do number+1 until map lookup fails.

  3. Storing all numbers from 1 to 20million in a set and taking one by one for use and add back when it's freed( this will have bigger memory footprint and don't want to do this)

    What is the most efficent way to solve this problem, if lets say around 50% of ids are used at any point of time

algorithm
3 Answers

20M of integers is about 80 Mb of RAM. If we are talking about Java, then according to this article, HashSet<Integer> can take up to 22 times more space, so it's about 1.7 Gb, wow.

You can implement your own bitset that supports fast selection of the next free ID. Bitset should take only about 2.4 Mb of RAM and we can find the next free ID in O(1). Haven't checked the code, it's mostly an idea:

int range = 20_000_000;
long[] bitset = new long[range / 64 + 1]; // About 2.4 Mb of RAM, array length is 312501
Stack<Integer> hasFreeIds = new Stack<Integer>(); // Slots in bitset with free IDs
for (int i = 0; i < bitset.length; ++i) { // All slots have free IDs in the beginning
  hasFreeIds.push(i);
}
// Now `hasFreeIds` is about (8 + 4) * 312_000 bytes = ~4Mb of RAM
// Our structure should be ~6.4 Mb of RAM in total

// Complexity is O(1), so should be fast
int getNextFreeId() {
  // Select the first slot with free IDs
  int freeSlotPos = hasFreeIds.pop();
  long slot = bitset[freeSlotPos];
  // Find the first free ID
  long lowestZeroBit = Long.lowestOneBit(~slot);
  int lowestZeroBitPosition = Long.numberOfTrailingZeros(lowestZeroBit);
  int freeId = 64 * freeSlotPos + lowestZeroBitPosition;
  // Update the slot, flip the bit to mark it as used
  slot |= lowestZeroBit;
  bitset[freeSlotPos] = slot;
  // If the slot still has free IDs, then push it back to our stack
  if (~slot != 0) {
    hasFreeIds.push(freeSlotPos);
  }
  return freeId;
}

// Complexity is also O(1)
void returnId(int id) {
  // Find slot that contains this id
  long slot = bitset[id / 64];
  boolean slotIsFull = (~slot == 0L); // True if the slot does not have free IDs
  // Flip the bit in the slot to mark it as free
  int bitPosition = id % 64;
  slot &= ~(1 << bitPosition);
  bitset[id / 64] = slot;
  // If this slot was full before, we need to push it to the stack
  if (slotIsFull) {
    hasFreeIds.push(id / 64);
  }
}
user_35854320

A space-efficient solution is to use a bit-mask to keep track of free entries. 20M bits is only 2.5MB.

If about half of them will be free, then when you need to allocate a new ID, you can just start at a random spot and walk forward until you find an entry with a free bit.

If you need a guaranteed time bound, then you can use an array of 64-bit words for your bit mask, and a bit mask of 1/64 the size to keep track of which words have free entries. Recurse until you get to one or two words.

If space isn't a problem, then the simplest fast way is to keep free IDs in a free list. That requires an array of up to 20M integers. You remember the last entry freed, and for every free node x, array[x] is the index of the preceeding freed node, or -1.

If your IDs actually point to something, then often you can use the very same array for the free list and the pointers, so the free list takes no extra memory at all.

user_54835260

Theoretically speaking, the fastest would be storing all free IDs in a linked list.

That is, push 20M sequential numbers into a linked list. To allocate an ID pop it from the front. And when an ID is free - push it at either top or bottom depending on your preferred staregy (i.e. would you reuse freed IDs first, or only after each preallocated one was used). This way both allocating an ID and freeing it is O(1).

Now, as an optimization you don't really need to preallocate all your IDs. You should only store the highest ID allocated. When you need to allocate an ID and the list of free IDs is empty - just increase the highest ID variable and return it. This way your list will never reach big numbers, unless they were really allocated and returned.

user_15608500
Related