Why my List is running faster than Queue when it should not?

Question

I am comparing enqueue and dequeue functions of following data structures in Python:

1) List

using built in python list

I implemented enqueue using .insert(0,value)

I implemented dequeue using .pop()

2) Queue

using custom class I made for Queue using from collections import deque

I implemented enqueue using .enqueue(value)

I implemented dequeue using .dequeue()

My code:

import timeit

# Working For List :

List_Code = '''

def M_N_List(M, N):

    from random import randint

    no_of_integers = N

    list = []

    for i in range(M):

        for i in range(no_of_integers):
            list.insert(0 , randint(1, 100))

        for i in range(no_of_integers):
            list.pop()            
            
M_N_List(15,20)
            
'''

print("List : ")
print ("Code Run Time = " , round(timeit.timeit(stmt = List_Code,
                     number = 10000) , 4) , "seconds")

# *****************************************************************

# Working For Queue :

Queue_Code = '''

def M_N_Queue(M,N):

    from Queue import Queue
    from random import randint

    no_of_integers = N

    queue = Queue()

    for i in range(M):

        for i in range(no_of_integers):
            queue.enqueue(randint(1,100))

        for i in range(no_of_integers):
            queue.dequeue()
 
M_N_Queue(15,20)
 
'''

print("")
print("Queue : ")
print ("Code Run Time = " , round(timeit.timeit(stmt = Queue_Code,
                     number = 10000) , 4) , "seconds")

My custom queue class:

import ctypes
from collections import deque

class Queue:

    def __init__(self):
        self.buffer = deque()

    def size(self):
        return len(self.buffer)

    def make_array(self,new_cap):
        return (new_cap * ctypes.py_object)()

    def __getitem__(self, k):
        if not 0 <= k < len(self.buffer):
            return IndexError("k is out of bounds")

        return self.buffer[k]

    def enqueue(self, val):
        self.buffer.appendleft(val)

    def dequeue(self):
        return self.buffer.pop()

    def is_empty(self):
        return len(self.buffer) == 0

Problem:

Despite knowing the fact that List is slower than Deque in python , I am getting the opposite results when I do my time analysis using timeit library.

Queue is taking greater time(in seconds) than List in my analysis when it should not because as we know big-o of List is greater than that of Queue

Kindly see my hand written analysis List Vs Queue Analysis.pdf for better understanding of my problem.

user_548562 · Answer

The slow down is caused by your wrapping Queue class, every time a method is called multiple attr lookups and further method calls are triggered and they all add up. If you use a deque directly you will get faster results than with a list

DEQUE_CODE = '''

def M_N_Deque(M,N):

    from collections import deque
    from random import randint

    no_of_integers = N

    queue = deque()

    for i in range(M):

        for i in range(no_of_integers):
            queue.appendleft(randint(1,100))

        for i in range(no_of_integers):
            queue.pop()

M_N_Deque(15,20)

'''

print("")
print("Deque : ")
print("Code Run Time = ", round(timeit.timeit(stmt=DEQUE_CODE,
                                              number=10000), 4), "seconds")

Why my List is running faster than Queue when it should not?

1 Answers