2

I'm looking for an algorithm that assigns and releases integers from some interval [a,b].

Every time we request an assignment, the algorithm produces an integer in the [a,b] range that has not been assigned before. We may free integers that had previously been assigned by asking the algorithm to release them. Doing so makes them available for assignment again.

To summarise:

  • After an integer is assigned, it cannot be assigned again until it is released
  • If one or more integers are not assigned, the algorithm must assign one of them
  • If and only if all integers in the range are assigned, the algorithm assigns none

It is desired that both the time and space complexity of the algorithm be sub-linear (for n = b - a).

As a bonus requirement, assume that some specific integers in [a,b] are required to be initially assigned.

Nerius
  • 910
  • 6
  • 16
  • This sounds like the basis for implementing dynamic memory. I'd start with those concepts – Mooing Duck Jun 03 '14 at 22:56
  • If it's ok to assign the numbers in order then you just need to maintain a list of not-yet-assigned numbers and released numbers, no? – assylias Jun 03 '14 at 22:56
  • 4
    I could be wrong, but I feel we could use similar logic to [the pigeonhole principle](http://en.wikipedia.org/wiki/Pigeonhole_principle) to prove that using less than linear space is impossible. – Bernhard Barker Jun 03 '14 at 22:58
  • @Dukeling: You could use subliniar space on average quite easily using ranges. I'm not sold on it being impossible in the worst-case, but I can't think of a way. – Mooing Duck Jun 03 '14 at 22:59
  • 1
    Sounds like a sparse set. See http://stackoverflow.com/questions/361040/representing-sparse-integer-sets – Jim Mischel Jun 03 '14 at 23:01
  • I believe that hashing is your friend. The approach needs a hashtable with struct{integer value, bool assigned} type of data in it. You start by inserting all integers as 'not assigned'. After that every time an assignment is needed you scan linearly the table and assign the first no assigned value you see. It is the nature of hashing that can make the integer to be assigned "random". Other functions like free - ready to reassign, are more obvious... – user2007447 Jun 03 '14 at 23:03
  • @Thanix What you want sounds less like an algorithm, and a lot more like a container. As such, the assign/release could have different complexities. – Mooing Duck Jun 03 '14 at 23:03
  • 2
    @user2007447: (1) hashing uses far more than linear space, (2) linear search is just silly (3) I see no requirement or suggestion for "random". – Mooing Duck Jun 03 '14 at 23:04
  • @MooingDuck, as long as the complexities of assign and release are sub-linear they meet the requirements. They are algorithms themselves as well, but I agree that wrapping them in a container or similar abstraction makes sense. – Nerius Jun 03 '14 at 23:08
  • 1
    If O(n) space is acceptable, you can do this with a simple queue. That will give you O(1) assignment and O(1) release. – Jim Mischel Jun 04 '14 at 03:21
  • 1
    You definitely can't use sublinear space in the worst case, since there are 2^n possible distinct patterns of available numbers, and each one needs to be represented by a different bit pattern. That means we need at least lg(2^n) = n bits. – j_random_hacker Jun 04 '14 at 03:44
  • (To see that all of the 2^n states of available numbers are actually reachable, make 2^n "allocate" requests to start with, and then notice that you can get to any desired state by making "free" requests on that particular subset of numbers.) – j_random_hacker Jun 04 '14 at 03:51
  • @j_random_hacker: `n` bits is true for arbitrary objects, but in this case we're working with integers, so shortcuts can be taken. I don't think there's a known theoretical lower bound for sequential integers. (There exists a bound obviously, but I don't think anyone has bothered to calculate it) – Mooing Duck Jun 05 '14 at 16:22
  • @MooingDuck: Suppose it was possible to represent any subset of {1, 2, ..., n} using fewer than n bits: then given a set of n arbitrary objects, just map them each to a distinct integer (there are n! ways to do this, any one of them will work), and bam -- you can now represent any subset of n arbitrary objects in less than n bits too! ;) – j_random_hacker Jun 05 '14 at 17:19
  • @j_random_hacker: Yes. Of course, it would require the n aribtrary objects to be mapped to _sequential_ integers, and entirely reconstructable from the integer. I'm not saying I know of a way, merely that I can't prove to myself there _isn't_ a way. – Mooing Duck Jun 05 '14 at 17:23
  • @MooingDuck: Hmm, by "yes, I think it could be done" do you mean you think it's possible to represent any subset of n arbitrary objects using less than n bits? Or that you think it's possible my explanation is correct? – j_random_hacker Jun 05 '14 at 17:25
  • @j_random_hacker: I think it's possible to represent any subset of n sequential numbers in less than n bits, if you can figure out a way to map those to arbitrary objects, then the theory would also extend to representing a subset of n arbitrary objects. However, I think that integer<->object mapping is going to be just as complicated as the storing of the integer sets. – Mooing Duck Jun 05 '14 at 17:28
  • @MooingDuck: You were right on target with your original "pigeonhole principle" comment. If you have n objects, even if they are sequential integers, then you can form 2^n subsets of them (notice that this fact doesn't vary, regardless of what "type" of objects they are); but with n-1 bits you can only enumerate 2^(n-1) distinct values. 2^n > 2^(n-1) for all n >= 0, so it's impossible to map every element from the first set to a distinct element in the second -- IOW it's impossible to represent every subset of n objects uniquely and unambiguously using n-1 bits. – j_random_hacker Jun 05 '14 at 17:30
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/55152/discussion-between-mooing-duck-and-j-random-hacker). – Mooing Duck Jun 05 '14 at 17:31

1 Answers1

1

The first thing that comes to mind is start with a single "available" range. When the user assigns an integer, simply remove it from the range:

        [a,b]
a <---  [a+1,b]

This is an O(1) operation in all cases. Due to the way the return step works, this means that the maximum number is only assigned when no other number is available, and low numbers are reused as often as possible.

When the user returns an integer, do a binary search to figure out which range it either goes before, or merges into:

[28][30-50]     <---- user is going to release 29
[28-50]
-or-
[26][30-50]     <----- user is going to release 28
[26][28][30-50]

This is an O(log m) operation where m is the number of ranges, which is usually very small. It starts at 1, but can be at most n/2 depending on which numbers the user releases.

If you want to get really tricky, you can add an second ordering on the ranges, that moves smaller ranges closer toward the "front", and larger ranges closer to the "end", and when the user makes a number "available", you give them the first value in the "smallest" range, which would heuristically lead to smaller sets being "consumed", leaving fewer sets total, thus saving space on average. However, this adds a lot of complexity, and a small amount of space and time, so the worst cases get slightly worse. Measure first before trying this.

It's worth mentioning that this does use linear space, though I'm pretty sure the constant is <=1, so the memory overhead would be less than that of storing all of the numbers. It's hard to calculate an average without making wild assumptions about how the user assigns and releases integers, but I'm pretty sure the average memory usage is actually closer to logarithmic than linear. Hard to tell though, that might be optimism.

Some dynamic memory dispatches work on similar concepts to this, often storing the "unused" parts as a linked list inside the unused memory. This way, there's no additional overhead space required. Since you're dealing with integer ranges rather than heap memory, this optimization probably doesn't help you.

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158