在Python中如果你需要一个队列的话,初学者可能会这样做:

Q = []

# 入队
Q.append(1)
Q.append(2)
Q.append(3)

# 出队
print(Q.pop(0))
print(Q.pop(0))
print(Q.pop(0))

这么做是不对的,因为Q.pop(0)的复杂度是O(n),它需要将整个队列中的数据都向前移动,效率非常低。

正确的做法是使用指针来实现队列,Python中提供了两个现成的队列库,一个是collections.deque,另一个是queue.Queue,它们都可以实现高效的队列服务:

from collections import deque

Q = deque()

# 入队
Q.append(1)
Q.append(2)
Q.append(3)

# 出队
print(Q.popleft())
print(Q.popleft())
print(Q.popleft())
import queue

Q = queue.Queue()

# 入队
Q.put(1)
Q.put(2)
Q.put(3)

# 出队
print(Q.get())
print(Q.get())
print(Q.get())

那么这两个库有什么区别呢?根据queue-queue-vs-collections-deque上的解释,queue.Queue支持多线程,而collections.deque仅仅作为一个队列数据结构。

下面来对比一下这三种方式的耗时:

import time
import queue
from collections import deque
N = 500000

t1 = time.time()
Q1 = deque()
for i in range(N):
    Q1.append(i)
    
for i in range(N):
    Q1.popleft()
print(time.time()-t1)


t2 = time.time()
Q2 = queue.Queue()
for i in range(N):
    Q2.put(i)

for i in range(N):
    Q2.get()
print(time.time()-t2)


t3 = time.time()
Q3 = []
for i in range(N):
    Q3.append(i)

for i in range(N):
    Q3.pop(0)
print(time.time()-t3)
0.13461041450500488
2.5977509021759033
40.273903131484985
posted @ 2019-02-23 09:10:29
评论加载中...

发表评论