During this week's lab, after seeing the inefficiency of the queue class functions I wrote in comparison to the stack class functions, I couldn't help but do some further research. From my research I was able to find the primary factor contributing to the inefficiency of the queue class; with each and every dequeue, every element after the first in the queue list must be shifted in order to maintain the list. As a result, I witnessed a linear correlation between the time taken for a fixed number of items to be queued and dequeued and the number of items in the queue. With lists alone, I was unable to come up with a solution for this problem during the lab, however during my own time I came across a plausible solution: the deque (pronounced "deck").
The deque (short for double-ended queue) supports memory efficient appends and pops from either side of the deque with no substantial difference in performance regardless of direction. Previously, using Python's built-in list to create the queue class resulted with the program struggling when it had to dequeue an item from a large queue. But by using a deque, the dequeue function bypasses the struggle as it does not have to shift every item in the list to maintain it after the first element is popped. Personally I found the deque to be quite intriguing but my discovery of it also got me wondering as to why it shouldn't just replace the traditional built in list entirely. If you share my interest you can find more info on the deque and its methods here.
No comments:
Post a Comment