1
$\begingroup$

In a game application there is a session id assigned to each player every time they start a new session. Session id's are always unique and there can be billion users of this game. Whenever a user logs-in, get() function is called which basically assigns a bit to the user by setting a bit from a bitarray and when user logs out, set() function is called which resets that bit.

So,it may happen that at some point the bit array looks like below: 101010101000011111

For uint_32 bitarray[100000], 100000 integers needs to be searched for finding out reset bit in worst case if linear search is used. Is it possible to make this search constant time?

For a 32/64 integer and not using bit array this would be pretty much constant using bit operation (x&-x) but for a bit array getting constant time it would be not that easy.

Is there any data structure which I can use for this purpose? I think we can use skip list for this but need some information as to the right approach to insert and delete element from this skip list?

$\endgroup$
  • $\begingroup$ To check a small tangential point: Is it OK if session ids are guessable? Often we want session ids to be unguessable, so they need to be 128 bits long or so... so a bit array isn't workable in that case. $\endgroup$ – D.W. Nov 5 '17 at 17:58
  • $\begingroup$ @D.W.: Indexing into a bit array is constant time but how would you know which bit to assign in constant time? Indexing and finding out which bit to assign is obviously O(n) (worst case) but can we do better than that? $\endgroup$ – noman pouigt Nov 5 '17 at 19:45
  • $\begingroup$ See my updated answer. No, indexing and finding out which bit to assign is not O(n) time. $\endgroup$ – D.W. Nov 5 '17 at 21:28
  • $\begingroup$ @D.W.: sorry, but i think i was not clear. Suppose this is the bit array 10000000 11111111 (8 bit is the data type)so you have to go from index[0] to index[1] and and check one by one all bits to find out which bit is unallocated. If bit_array[100000] then you have to go from 0 to 100000 to find out which bit is unallocated as remember this bits represent user sessions and user can end the session any time. Finding out which bit to allocate for new user in a sparsely populated bit array has to be O(n) where n is the size of data type which can be 8, 32 or 64 and so on. $\endgroup$ – noman pouigt Nov 5 '17 at 21:41
  • $\begingroup$ No you don't have to do a linear scan -- there are better ways. You can pick a random index and see if it is allocated or not, and repeat. As long as the load factor is not too large, the average number of indices you have to try until you find one that is unallocated is a constant. All of this belongs in the question, not in the comments. Don't force us to guess what your question is, what you're trying to achieve, or why you've rejected certain natural solutions. If you update the question to clarify what you are asking I'll update my answer. $\endgroup$ – D.W. Nov 6 '17 at 6:43
3
$\begingroup$

Access into a bit array is constant time. In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, regardless of how large $i$ is. That's all that you need to do to access a bit array. In particular, if you have an array of bytes, then you can read the $i$th bit of the bit-array by reading $A[i/8]$ and doing a bit-masking operation to get the $(i \bmod 8)$th bit of that byte, and so on.

If you want to find a new session id that is not in use, that can be done in (expected) constant time as long as at least 1/2 of the session ids are not in use. You simply pick a random session id, check whether it is in use, and repeat until you find one that is not in use. If at least 1/2 of the session ids are not in use, the expected number of times you need to repeat this until you find one that is not in use is 2 (as it's expected the number of coin tosses until you get a heads, which is a geometric series), i.e., a constant. Each iteration takes constant time, so the whole thing can be done in $O(1)$ time.

So, a bit array already meets all of your requirements. Just make sure that at least 1/2 of the session ids are not in use.

(What do you do if more than 1/2 of the session ids are in use? Double the size of the array, copying over the old array if needed. The doubling will happen rarely enough that the amortized time for each operation remains constant, i.e., $O(1)$.)

$\endgroup$
  • $\begingroup$ Can you possibly explain how you arrived at a constant factor of 2? I understand the probability of selecting a used session is 1/2 and same goes for not used session. So, in worst case it will take n/2 times to find the unused session. $\endgroup$ – noman pouigt Nov 7 '17 at 5:52
  • $\begingroup$ @nomanpouigt, I added a brief explanation. You can simulate it: try writing some code to flip a fair coin repeatedly until the first heads. See how many flips are needed on average. Worst case might be very high but the worst case is exceeding unlikely (exponentially small probability); the average case is far far etter. Try it out! $\endgroup$ – D.W. Nov 7 '17 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.