2
$\begingroup$

I have an Object Pool and I will be using it to create Objects. I want to generate an unique id for each object. id should be an integer starting from 0. Ids should be continuous. When an object is deleted that id should be reusable. So that next object created can reuse that id instead of a new id.

And also if there are too many objects deleted this can result in too many reusable ids. For example we created 10 objects. with id 0 to 9. Lets say object with id 2 and object with id 4 are deleted. So ids 2 and 4 are now reusable. And it would be nice if it was possible to shift ids such that object with id 3 will use id 2. and object with id 5 will use id 3 like that. So in the end last id will be 7. Is there any algorithm which makes it possible to do this efficiently? Id generation in O(1) and id shifting in O(n)

$\endgroup$
2
  • 2
    $\begingroup$ changing object id while object is active is a bad practice since id may be used to match object against other objects, so changing id during this process can have unpredictable results (eg imagine parallel processing of objects based on their ids) $\endgroup$
    – Nikos M.
    Jul 22, 2021 at 8:05
  • $\begingroup$ @NikosM. You are right. changing id is risky, but this Id is going to be used inside a specific module only and that module wont have any parallel processing. But since object deletion occurs if we allocate 1 M objects and Delete first 900 thousand objects, active ids are only from 900 K to (1M - 1) . Ids from 0 to (900K - 1) are not used. Probably some memory is going to be required to store these ids for reuse. So if we shift ids after a huge deletion we can save memory. $\endgroup$
    – thambi
    Jul 22, 2021 at 11:12

1 Answer 1

2
$\begingroup$

A simple observation is that when an object is assigned an id, that id never increases, i.e., it either stays the same or decreases. So keep a global counter $g$ for giving ids, initially set to 0.

Let $A$ be your list of indices (or objects). Consider a deletion event $D$ consisting of ids you want to delete. To reindex, scan $A$ starting from the 0th index. Whenever $i \in D$, delete the corresponding entry in $A$ and increment a counter, say $d$, initially set to zero. For each subsequent index $j > i$, decrement each entry by $d$ (again, if you encounter an index you must delete, you decrement $d$ etc.).

So let me describe the basic idea with $A = [0,1,\ldots,9]$. Let $D = [2,4]$. Scan $A$, and at $i = 2$ set $d = 1$ and $A = [0,1,x,3,4,5,6,7,8,9]$. Continuing from $i=3$, we get $A=[0,1,x,2,4,5,6,7,8,9]$. Next, at $i = 4$, we mark $A[i]$ deleted and get $d = 2$. Thus, we are left with $A=[0,1,x,2,x,3,4,5,6,7]$. As $d = 2$, we update $g$ to $g - d$.

We can implement the above by looping over the elements in $D$. If $i'$ is the index in $D$, mark $A[i'] = x$, increment $d$ by one, and scan $A$ until $j' > i'$ where $j'$ is the next index in $D$ (or if there is no $j'$, scan until the end of $A$), and decrement each element of $A$ by $d$. You can implement this scheme to run in $\Theta(n)$ time, where $n$ is the number of elements in $A$. Indeed, we scan over $D$ once (and note that $|D| \leq |A|$ as it only contains indices to $A$) and also scan over $A$ once, essentially only skipping as many elements from the beginning of $A$ as the first index $i'$ in $D$ lets us. Finally, as $g$ is always kept up to date, you can generate new ids in $O(1)$ time too.

So with this implementation, the above example becomes as follows. Loop over $D$, i.e., start at $i' = 2$. Mark $A[i'] = x$. Check that $j' = 4$, so decrement $A[3]$ by one and mark $A[j'] = x$. Now, we see that there is no $j'' > j'$, so decrement each $A[\ell]$ by two, for $j' + 1 \leq \ell \leq n$. Set $g := g - 2$ and halt.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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