Thursday 6 March 2014

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!