At some point I required a simple data structure that would server as a first-in-first-out queue. I could use the usual
queue.Queue, but I didn’t need the threading locks it has. Not to mention that they decrease the performance quite significantly.
My best bet was
collections module. It does what I want and it’s presumably much faster than
queue.Queue. There are some problems though, for me, at least; that made me write my own class.
Getting used to it.
I am used to
put() methods on queues and
pop() on stacks. Here, I want to use
deque as a FIFO queue, but it uses
popleft() for the purposes I need. Not very intuitive, I may forget about it during intensive programming.
Overriding the names
Maybe I will not need that in practice, but since I want it to be a FIFO queue, I want getting from the left of the data structure to be more intuitive than getting from the right. So I started off by overriding the method names.
Now, getting the leftmost element is just
pop(), which is convenient; and if I ever need to get an element from the right (which I won’t since I use it as a queue; but simply for the sake of leaving the original
pop() intact), I can do it via
I could do the same to assign
get() as well. But I’ve decided to make it a bit move verbose and expanded, because I needed to solve yet another problem.
queue module conveniently provides a
queue.Empty exception, which is raised when you try to
get() from a non-blocking
Queue which has no elements in it. What does
deque do in this situation? It raises
IndexError! Neither intuitive nor verbose, to me. So I added my own to the class. For the sake of simplicity, my queue is non-blocking and always raises the exception when it is empty.
Simple enough. I could make it raise
queue.Empty, but I felt like making my own exception specific to this very class.
Ok. One final problem.
Careful, don’t lose data!
maxsize argument that allows you to specify the maximum size of the queue, obviously; and if you add a message when the queue is full, the
queue.Full exception will be raised.
deque behaves differently. It was
maxlen, but when you add messages to a full queue, it does not raise any exceptions; it drops messages from the opposite side silently instead! This could be dangerous, because it can be easily forgotten during your workflow. We’ll do two things to circumvent that:
maxlenentirely and show a warning if we provide it.
- provide a
max_lengthinstead that will make the queue raise an exception when it is full.
So here’s the final code.
I can access queue size simply using the built-in
len() function; I can check the overflow this way. Again, I made my own
The class is not complex at all. But let’s see how fast it can go. Let’s create two benchmark functions: one for our class, another for
queue.Queue. All they do is put a million integers into queue and then get them all.
6.7 s ± 408 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
827 ms ± 106 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Eight times faster! Guess it was worth it. I didn’t try other types of data, but even being able to do it with elementary types is pretty cool already, if you ask me.
It was just a simple recipe for a FIFO queue that you can tweak to your own needs. Python is a flexible language, it’s fun to customize stuff.
Thanks for tuning in! I’ll see you eventually.