16

I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).

My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have constant access via an index.

Looking over the documentation though, I realized that ArrayLists' additions are considered Amortized Constant Time, since an addition may require a reallocation of the underlying array, which is O(n).

Are Amortized Constant Time and Constant Time effectively the same, or do I need to look at some structure thay doesn't require a full reallocation on every addition?

I'm asking this because array based structures aside (which as far as I know will always have Amortized Constant Time additions), I can't think of anything that will meet the requirements:

  • Anything tree based will have at best O(log n) access
  • A linked list could potentially have O(1) additions (if a reference to the tail is kept), but a random removal should be at best O(n).

Here's the full question; in case I glazed over some important details:

Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.

  • Does the assignment specify how random removals are performed? Are you given an index to remove or a reference to a queue element? – user7043 Jun 20 '15 at 15:36
  • It doesn't give any specifics. The requirements are just a structure that implements the Queue interface and has O(1) additions and removals. – Carcigenicate Jun 20 '15 at 15:37
  • As an aside – a resizeable array with O(n) growing does not necessarily have O(1) addition: this depends on how we grow the array. Growing by a constant amount a is still O(n) for addition (we have an 1/a chance for an O(n) operation), but growing by a constant factor a > 1 is O(1) amortized for addition: we have a (1/a)^n chance of an O(n) operation, but that probability approaches zero for large n. – amon Jun 20 '15 at 15:46
  • ArrayLists use the latter correct? – Carcigenicate Jun 20 '15 at 16:02
  • 1
    The author of the question (me) was thinking of the amortized constant time solution. I'll clarify that in the next edition. (Although worst-case constant-time can be achieved here using the technique of de-amortization.) – Pat Morin Jun 21 '15 at 10:07
10

Amortized Constant Time can almost always be considered equivalent to Constant Time, and without knowing the specifics of your application and the type of usage you are planning to do to this queue, most chances are that you will be covered.

An array list has the concept of capacity, which is basically equal to the largest size/length/count of items that has ever been required of it thus far. So, what will happen is that in the beginning the array list will keep reallocating itself to increase its capacity as you keep adding items to it, but at some point the average number of items added per unit time will inevitably match the average number of items removed per unit time, (otherwise you would eventually run out of memory anyway,) at which point the array will stop reallocating itself, and all appends will be met at constant time of O(1).

However, keep in mind that by default, random removal from an array list is not O(1), it is O(N), because array lists move all the items after the removed item one position down to take the place of the removed item. In order to achieve O(1) you will have to override the default behavior to replace the removed item with a copy of the last item of the array list, and then remove the last item, so that no items will be moved. But then, if you do that, you do not exactly have a queue anymore.

  • 1
    Damn, good point on removals; I didn't consider that. And since we're randomly removing elements, doesn't that technically mean it's no longer a queue in that sense anyways? – Carcigenicate Jun 20 '15 at 15:48
  • Yes, it does mean that you are not really treating it as a queue. But I do not know how you are planning to find the items to remove. If your mechanism of finding them expects them to be present in the queue in the order in which they were added, then you are out of luck. If you do not care if the order of the items gets garbled, then you are fine. – Mike Nakis Jun 20 '15 at 15:50
  • 2
    The expectation is for my RandomQueue to implement the Queue interface, and for the supplied remove method to randomly remove instead of popping the head, so there shouldn't be any way to rely on a specific ordering. I think given the random nature of it then, that the user shouldn't expect it to keep any specific order. I quoted the assignment in my question for clarification. Thank you. – Carcigenicate Jun 20 '15 at 15:53
  • 2
    Yes then, it seems like you will be fine if you just make sure that item removal is done the way I suggested. – Mike Nakis Jun 20 '15 at 16:12
  • One last thing if you don't mind. I've thought it over more, and it doesn't seem like it's possible to have both "true" O(1) additions and "true" O(1) random removal; it'll be a tradeoff between the 2. You either have singly-allocated structure (like an array) that gives removal but not additon, or a chunk-allocated structure like a Linked-List that gives additions but not removal. Is this true? Again, thank you. – Carcigenicate Jun 20 '15 at 16:45
14

The question seems to specifically ask for constant time, and not an amortized constant time. So with respect to the quoted question, no, they are not effectively the same*. Are they however in real world applications?

The typical issue with amortized constant is that occasionally you have to pay the accumulated debt. So while inserts are generally constant, sometimes you have to suffer the overhead of reinserting everything again when a new block is allocated.

Where the difference between constant time and amortized constant time is relevant to an application depends on whether this occasional very slow speed is acceptable. For a very large number of domains this is generally okay. Especially if the container has an effective maximum size (like caches, temp buffers, working containers) you could effectively pay they costs only once during execution.

In response critical applications these times may be unacceptable. If you are required to meet a short time turnaround guarantee you cannot rely on an algorithm that will occasionally exceed that. I have worked on such projects before, but they are exceedingly rare.

It also depends on how high this cost actually is. Vectors tend to perform well since their reallocation cost is relatively low. If you go to hash map however, the reallocation can be a lot higher. Though again, for most applications probably fine, especially longer lived servers with an upper bound on the items in the container.

*There's a bit of an issue here though. In order to make any general purpose container be constant time for insertion one of two things must hold:

  • The container must have a fixed maximum size; or
  • you can assume memory allocation of individual elements is constant time.
  • "liver server" seems a strange phrasing to use here. Do you mean "live server" perhaps? – Pieter Geerkens Jun 21 '15 at 12:34
6

It depends – on whether you are optimizing for throughput or for latency:

  • Latency-sensitive systems need consistent performance. For such a scenario, we have to emphasize worst-case behaviour of the system. Examples are soft real time systems such as games that want to achieve a consistent framerate, or web servers that have to send a response within a certain tight timeframe: wasting CPU cycles is better than being late.
  • Throughput-optimized systems don't care about occasional stalls, as long as the maximal amount of data can be processed in the long run. Here, we are primarily interested in amortized performance. This is generally the case for number crunching or other batch-processing jobs.

Note that one system can have different components that must be categorized differently. E.g. a modern text processor would have a latency-sensitive UI thread, but throughput-optimized threads for other tasks such as spellchecking or PDF exports.

Also, algorithmic complexity often does not matter as much as we'd might think: When a problem is bounded to a certain number, then actual and measured performance characteristics are more important than the behaviour “for very large n”.

  • Unfortunately, I have very little background. The question ends with: "The add(x) and remove() operations in a RandomQueue should run in constant time per operation". – Carcigenicate Jun 20 '15 at 15:34
  • 2
    @Carcigenicate unless you know for a fact that the system is latency-sensitive, using amortized complexity to select a data structure should be absolutely sufficient. – amon Jun 20 '15 at 15:45
  • I have the impression this might be a programming exercise or a test. And certainly not an easy one. Absolutely true that it very rarely matters. – gnasher729 Jul 16 '15 at 17:18
1

If you are asked for an "amortized constant time" algorithm, your algorithm may sometimes take a long time. For example, if you use std::vector in C++, such a vector may have allocated space for 10 objects, and when you allocate the 11th object, space for 20 objects is allocated, 10 objects are copied, and the 11th added, which takes considerable time. But if you add a million objects, you may have 999,980 fast and 20 slow operations, with the average time being fast.

If you are asked for a "constant time" algorithm, your algorithm must always be fast, for every single operation. That would be important for real-time systems where you might need a guarantee that each single operation is always fast. "Constant time" is very often not needed, but it is definitely not the same as "amortized constant time".

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.