簡析Python中的四種隊列

最新 05-23

隊列是一種只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。

在Python文檔中搜索隊列（queue）會發現，Python標準庫中包含了四種隊列，分別是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。

—

collections.deque

deque是雙端隊列（double-ended queue）的縮寫，由於兩端都能編輯，deque既可以用來實現棧（stack）也可以用來實現隊列（queue）。

deque支持豐富的操作方法，主要方法如圖：

相比於list實現的隊列，deque實現擁有更低的時間和空間複雜度。list實現在出隊（pop）和插入（insert）時的空間複雜度大約為O(n)，deque在出隊（pop）和入隊（append）時的時間複雜度是O(1)。

deque也支持in操作符，可以使用如下寫法：

deque還封裝了順逆時針的旋轉的方法：rotate。

線程安全方面，通過查看collections.deque中的append()、pop()等方法的源碼可以知道，他們都是原子操作，所以是GIL保護下的線程安全方法。

通過dis方法可以看到，append是原子操作（一行位元組碼）。

綜上，collections.deque是一個可以方便實現隊列的數據結構，具有線程安全的特性，並且有很高的性能。

—

queue.Queue & asyncio.Queue

queue.Queue和asyncio.Queue都是支持多生產者、多消費者的隊列，基於collections.deque，他們都提供了Queue（FIFO隊列）、PriorityQueue（優先順序隊列）、LifoQueue（LIFO隊列），介面方面也相同。

區別在於queue.Queue適用於多線程的場景，asyncio.Queue適用於協程場景下的通信，由於asyncio的加成，queue.Queue下的阻塞介面在asyncio.Queue中則是以返回協程對象的方式執行，具體差異如下表：

—

multiprocessing.Queue

multiprocessing提供了三種隊列，分別是Queue、SimpleQueue、JoinableQueue。

multiprocessing.Queue既是線程安全也是進程安全的，相當於queue.Queue的多進程克隆版。和threading.Queue很像，multiprocessing.Queue支持put和get操作，底層結構是multiprocessing.Pipe。

multiprocessing.Queue底層是基於Pipe構建的，但是數據傳遞時並不是直接寫入Pipe，而是寫入進程本地buffer，通過一個feeder線程寫入底層Pipe，這樣做是為了實現超時控制和非阻塞put/get，所以Queue提供了join_thread、cancel_join_thread、close函數來控制feeder的行為，close函數用來關閉feeder線程、join_thread用來join feeder線程，cancel_join_thread用來在控制在進程退出時，不自動join feeder線程，使用cancel_join_thread有可能導致部分數據沒有被feeder寫入Pipe而導致的數據丟失。

和threading.Queue不同的是，multiprocessing.Queue默認不支持join()和task_done操作，這兩個支持需要使用mp.JoinableQueue對象。

SimpleQueue是一個簡化的隊列，去掉了Queue中的buffer，沒有了使用Queue可能出現的問題，但是put和get方法都是阻塞的並且沒有超時控制。

—

總結

通過對比可以發現，上述四種結構都實現了隊列，但是用處卻各有偏重，collections.deque在數據結構層面實現了隊列，但是並沒有應用場景方面的支持，可以看做是一個基礎的數據結構。queue模塊實現了面向多生產線程、多消費線程的隊列，asyncio.queue模塊則實現了面向多生產協程、多消費協程的隊列，而multiprocessing.queue模塊實現了面向多成產進程、多消費進程的隊列。

—

參考

https://docs.python.org/3/library/collections.html#collections.deque

https://docs.python.org/3/library/queue.html

https://docs.python.org/3/library/asyncio-queue.html

https://docs.python.org/3/library/multiprocessing.html#multiprocessing.Queue

https://bugs.python.org/issue15329

http://blog.ftofficer.com/2009/12/python-multiprocessing-3-about-queue/

http://cyrusin.github.io/2016/04/27/python-gil-implementaion/

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！