Performance bug in RandomizedQueue of 1-2-queues

[vladkinoman]

Performance bug in RandomizedQueue of 1-2-queues

Description

Test case on Coursera says that StdRandom() should be called at most once per method (enqueue() and dequeue()). So, in this case I have a problem with current implementation because I use random enumeration to select non-empty (!null) items to dequeue them off.

To reproduce

Test 1: make n calls to enqueue() followed by n calls to dequeue();
count calls to StdRandom

• n = 10

  • enqueue() and dequeue() should call StdRandom() at most once per item
  • number of items = 10
  • number of elementary StdRandom() operations = 14

• n = 100

  • enqueue() and dequeue() should call StdRandom() at most once per item
  • number of items = 100
  • number of elementary StdRandom() operations = 154

• n = 1000

  • enqueue() and dequeue() should call StdRandom() at most once per item
  • number of items = 1000
  • number of elementary StdRandom() operations = 1686

==> FAILED

A possible solution

Maybe it would be nice to copy non-empty (!null) items into a new array, instead of random enumeration, and then enumerate them uniformly at random. But in this case the implementantion might not support all operations in constant amortized time.

Methods that need to be changed: dequeue(), sample(), resize() and RandomizedQueueIterator() constructor. If we don't want to keep track head and tail, enqueue() could be changed in the next lines of code:

if (count == resizingArray.length || tail == resizingArray.length)
            resize(2 * resizingArray.length);