A calm sea does not make a skilled sailor.
- African proverb
Last week, we implemented a Stack and a Queue class for exercise purposes. A Queue is a list of objects that operate on a first-in, first-out basis. However, we noticed that the time it took to process a Queue increased linearly as the number of objects inside the Queue increased. This led us to a challenge: Can we design a Queue where the processing time is constant?
In order to complete this challenge, it is necessary for us to analyze two things. What method increases the processing time, and how can we adjust the method so that it behaves differently?
As it turns out, calling .pop() on a list is significantly faster than calling .pop(0). The reasoning behind this is due to how lists work inherently. Removing an element from the end of a list is easy, but removing an element from the beginning will require every single element to be shifted.
Thus, the implication is very straight forward - Always call .pop() and never .pop(0). However, the complication is that by definition: removing an object from a Queue results in the removal of the first object, and not the last.
This conveys to us that we must design our algorithm in a way such that attempting to remove an object from a Queue results in the removal of the last element, but at the same time, the last element must be the first object.
It is then a necessity that we should swap the first element with the last element, before calling .pop(). Luckily, swapping two elements is very simple. My proposed algorithm is as follow:
- A variable is needed to keep track of our "front". This variable will tell us the index of the element that is to be removed next. Our "front" will begin at index 0.
- A variable is needed to keep track of our "back". This variable will tell us the index of the element that we have just swapped our "front" with. Our "back" will begin at index -1.
- If we try to add more items to the Queue in the middle of our algorithm, it will give us problems. A easy way out is to add a "buffer" that keeps track of newly added items until our algorithm has finished with the removal of all the items in the original Queue.
- When enqueuing onto an empty Queue, our "front" remains at index 0, but our "back" increases by 1.
- When we attempt to dequeue from a newly enqueued Queue, our "front" element is swapped with our "back" element. The last element is then removed from the Queue. "front" is increased by 1, while "back" is now the previous "front"
- When attempting to enqueue after any attempts of dequeue has been made, all objects will be appended to our "buffer" instead.
- Eventually, our "front" will become greater than or equal to last index. This signifies that we have reached the end of our list.
- Upon reaching the end of our list, any further dequeues can be completed without swapping.
- When the list becomes empty, our "buffer" is transfered over into our Queue, and all indicators are reset. (i.e. "front" becomes 0 again, and "back" becomes the last index.)
Here is a visual example of each step outlined above:
>>> q = Queue() >>> q._data [] >>> q._front 0 >>> q._back -1 >>> q.enqueue(0) >>> q.enqueue(1) >>> q.enqueue(2) >>> q.enqueue(3) >>> q._data [0, 1, 2, 3] >>> q._front 0 >>> q._back 3 >>> q.dequeue() 0 >>> q._data [3, 1, 2] >>> q._front 1 >>> q._back 0 >>> q._dequeuing True >>> q.enqueue(4) >>> q._data [3, 1, 2] >>> q._front 1 >>> q._back 0 >>> q._buffer [4] >>> q.dequeue() 1 >>> q._data [3, 2] >>> q._front 2 >>> q._back 1 >>> q._eol True >>> q.dequeue() 2 >>> q._data [3] >>> q.dequeue() 3 >>> q.is_empty() False >>> q._data [4] >>> q._buffer [] >>> q._front 0 >>> q._back 0
I verified this algorithm with the testqueue.py and timequeue.py provided for us. testqueue.py passed successfully in under 0.001 seconds, and timequeue.py gave me the following results:
Running time on 100000 items: 0.056036949157714844
Running time on 200000 items: 0.056036949157714844
Running time on 300000 items: 0.0570378303527832
Running time on 400000 items: 0.05903792381286621
Running time on 500000 items: 0.0570368766784668
Running time on 600000 items: 0.057038068771362305
Running time on 700000 items: 0.057038068771362305
Running time on 800000 items: 0.05803799629211426
Running time on 900000 items: 0.057038068771362305
Running time on 1000000 items: 0.057038068771362305
(I increased the number of items to make the difference more noticeable)
Here is my complete code for reference. I hope it helped!
class Queue:
'''A list on a first in first out basis.
Challenge: Optimize Queue so that execution time of enqueue and dequeue
does not grow linearly. You must actually remove the object from the Queue.
You cannot simply "hide it".
The Problem: Attempting to pop/add an item at beginning of a list takes
significantly longer than trying to pop/add at the end.
Implication: We should only pop/add items at the end of the list.
Concept:
Example Queue: _data = [0, 1, 2, 3, 4, 5]
We keep track of a front and back index
_front = 0 # item is 0
_back = 5 # item is 5
We keep track of a buffer incase we are enqueuing in between dequeues
_dequeuing = false
_buffer = []
We need to keep track of whether we reached the end of the list
_eol = false
When you enqueue before dequeuing, the _back is moved to the very end:
_data.append(6) # [0, 1, 2, 3, 4, 5, 6]
_back = len(_data) - 1 # index 6, item is 6
When you dequeue, we want to swap the front and the back.
_data = [6, 1, 2, 3, 4, 5, 0].pop()
_back = _front # item is 6, index is 0
Since we are poping the front, the front is now technically at index 1
_front = front + 1 # index 1, item is 1
_data = [6, 1, 2, 3, 4, 5]
The first dequeue requires us to indicate this
_dequeuing = true
Another regular pop
_data = [6, 5, 2, 3, 4, 1].pop()
_back = _front # Item is 5, index is 1
_front = _front + 1 # index 2, item 2
_data = [6, 5, 2, 3, 4]
Enqueuing in the middle of dequeuing adds to the buffer
_data = [6, 5, 2, 3, 4]
_buffer = [7]
Dequeue #3
_data = [6, 5, 4, 3, 2].pop()
_back = _front # index 2, item 4
_front = _front + 1 # index 3, item 3
_data = [6, 5, 4, 3]
Enqueueing again
_buffer = [7, 8]
Dequeue #4 reaches the end
_front == len (_data) - 1
i.e. _front = _back + 1
_data = [6, 5, 4, 3].pop()
_data = [6, 5, 4]
Now we can just pop only.
_eol = true
furthur dequeues:
if _eol == true:
_data.pop()
When the queue is empty, we put in the buffer and reset everything
_data = _buffer
_buffer = []
_dequeuing = false
_eol = false
'''
def __init__(self: "Queue") -> None:
'''Initalize an empty Queue
>>> q = Queue()
>>> q._data
[]
>>> q._front
0
>>> q._back
-1
>>> q.enqueue(0)
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> q.enqueue(3)
>>> q._data
[0, 1, 2, 3]
>>> q._front
0
>>> q._back
3
>>> q.dequeue()
0
>>> q._data
[3, 1, 2]
>>> q._front
1
>>> q._back
0
>>> q._dequeuing
True
>>> q.enqueue(4)
>>> q._data
[3, 1, 2]
>>> q._front
1
>>> q._back
0
>>> q._buffer
[4]
>>> q.dequeue()
1
>>> q._data
[3, 2]
>>> q._front
2
>>> q._back
1
>>> q._eol
True
>>> q.dequeue()
2
>>> q._data
[3]
>>> q.dequeue()
3
>>> q.is_empty()
False
>>> q._data
[4]
>>> q._buffer
[]
>>> q._front
0
>>> q._back
0
'''
self._data = []
self._front = 0
self._back = -1
self._buffer = []
self._dequeuing = False
self._eol = False
def enqueue(self: "Queue", x: object) -> None:
'''Place x at the back of the Queue'''
# When you enqueue before dequeuing, the _back is moved to the very end
if not self._dequeuing:
self._back = self._back + 1
self._data.append(x)
else:
# Enqueuing in the middle of dequeuing adds to the buffer
self._buffer.append(x)
def dequeue(self: "Queue") -> object:
'''Remove and return the object at the front of the Queue'''
if self.is_empty():
raise Exception ("Queue is empty.")
# Record when we begin to dequeue
self._dequeuing = True
# If we are not at the end of the list, we dequeue by swaping
if not self._eol:
# When you dequeue, we want to swap the front and the back.
self._data[self._front], self._data[-1] = self._data[-1], \
self._data[self._front]
self._back = self._front
self._front = self._front + 1
# Otherwise, we need to only pop from the end
return_buffer = self._data.pop()
# Check whether we're at the end of the list
if self._front >= len (self._data) - 1:
self._eol = True
if self.is_empty():
# When the queue is empty, we put in the buffer and reset variables
self._data = self._buffer
self._buffer = []
self._eol = False
self._dequeuing = False
self._front = 0
self._back = len(self._data) - 1
if self._back < 0:
self._back = 0
return return_buffer
def is_empty(self: "Queue") -> bool:
'''Return whether or not the Queue has no objects'''
return len(self._data) == 0
def front(self: "Queue") -> object:
'''Return the object at the front of the Queue'''
return self._data[self._front]
if __name__ == "__main__":
import doctest
doctest.testmod()
