Yet Another Comparison of Queue Implementations

This week we had a lab on which students had to create an implementation of queue with linked lists. As I've done this out of curiosity couple of weeks ago I decided to up the ante in lab! On this post i will compare three different implementations of queues with graphs and timers only using python code and a great plotting library for python called Matplotlib. As I mentioned the native deque class in python as a really fast way to implement queues, I decided to give it a shot! Here are my three Queue classes that I tested:

Queue using List:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Queue: def __init__(self): self._items = [] def enqueue(self, item): self._items.append(item) def dequeue(self): a = self._items[0] del self._items[0] return a def front(self): return self._items[0] def is_empty(self): return self._items == []

Queue using Linked List:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

class Node: def __init__(self, data=None): self.data = data self.next = None def __str__(self): return str(self.data) class Queue: def is_empty(self): if self.head and not self.curr: return False elif not self.curr: return True elif self.curr.next: return False else: return True def __init__(self): self.head = None self.curr = None self.tail = None def __iter__(self): return self def dequeue(self): return self.next().data def next(self): if self.head and not self.curr: self.curr = self.head return self.curr elif self.curr.next: self.curr = self.curr.next return self.curr else: raise StopIteration def enqueue(self, data): n = Node(data) if not self.head: self.head = n self.tail = n else: self.tail.next = n self.tail = self.tail.next def front(self): a = self.dequeue() self.enqueue(a) return a

Queue using Deque:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

from collections import deque class Queue: def __init__(self): self._deq = deque() def enqueue(self, item): self._deq.append(item) def dequeue(self): return self._deq.popleft() def front(self): a = self._deq.popleft() self._deq.append(a) return a def is_empty(self): try: self._deq.popleft() except IndexError: return True else: return False

Here is the code I used to time, test, compare and graph these three different implementations of Queues:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

import time import matplotlib.pyplot as plt from csc148_queue import Queue as ListQueue from csc148_queue_deque import Queue as DequeQueue from csc148_queue_linked_list import Queue as LinkedListQueue factor = 10000 def getduple(q, iternum): a = range(factor, factor * iternum, factor) b = [] for i in a: b.append(time_queue(i, q)) return a, b def enqueue_dequeue(q, howmany): """Enqueue and dequeue 'howmany' items to/from Queue 'q'. """ for i in range(howmany): q.enqueue(42) q.dequeue() def time_queue(n, q): """Return how long it takes to enqueue and dequeue 'm' items to/from a Queue with 'n' items already in it. """ for i in range(n): q.enqueue(1) start = time.time() enqueue_dequeue(q, 20000) end = time.time() return end - start if __name__ == '__main__': firstqueue = getduple(ListQueue(), 12) secondqueue = getduple(LinkedListQueue(), 12) thirdqueue = getduple(DequeQueue(), 12) p1, = plt.plot(firstqueue[0], firstqueue[1], color='r', linewidth=2.0) p2, = plt.plot(secondqueue[0], secondqueue[1], color='b', linewidth=2.0) p3, = plt.plot(thirdqueue[0], thirdqueue[1], color='g', linewidth=2.0) plt.legend( [p1, p2, p3], ["List", "LinkedList", "Deque"], loc='upper left') plt.ylabel('Time') plt.xlabel('Number of Items') plt.show()

After running the code above you get a nice little graph of the time required for these queues against the number of items that are in the queue. Here is a little screenshot with a really high factor of 10000.

Here is a bit more zoomed in version on the difference between Deque and LinkedList:

As we can see, even though the Deque class outperforms LinkedList, the difference in their times is quite small even for relatively big number of items. Their difference in timings is smaller than 0.2 seconds for numbers as large as 110000 items. That's quite impressive!