您的位置:

让你的队列操作更高效的方法

一、使用deque代替list

Python提供了两种结构来实现队列:list和deque。list在 Python 中实现的是一个支持动态数组大小的顺序表,而deque实现了一个双向队列,它除了实现了普通队列的所有方法外,还实现了在线性时间复杂度内在队列两端插入(也就是说在最左边插入和在最右边插入)元素的方法。

对比list,在进行任何元素的插入或者取出操作时,都会导致一些元素的“移动”,这样就会带来O(n)的复杂度,虽然对于小规模的数据并不会有很大的影响,但是当数据规模变大时就会变得不太优秀,更进一步,双向队列的实现有利于各种类型的算法。

下面是使用deque代替list的示例代码:

from collections import deque
  
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft()

二、使用队列实现广度优先搜索(BFS)

BFS(广度优先搜索)是一种在树、图等数据结构中很常见的搜索算法,广泛应用于最短路径、拓扑排序等领域。BFS基于队列先进先出的特性,使用队列可帮助我们快速且高效地实现BFS算法。

下面是使用队列实现BFS的示例代码:

from collections import deque

def bfs(graph, start_node):
    visited = []
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue += graph[node] - set(visited)

    return visited

三、使用队列实现多线程

在Python中,使用了`Threading`、`Asyncio`等包来开发多线程程序,然而这些包的底层都是使用了队列来实现多线程操作,这是因为Python中的队列拥有高并发和高吞吐率的特性,是实现多线程高效的必备利器。

下面是使用有限制的队列(queue)实现多线程程序的示例代码:

import queue
import threading
  
q = queue.Queue()

def worker(q, n):
    while True:
        item = q.get()
        if item is None:
            break
        print("任务 %s 开始处理 %s" % (n, item))
        q.task_done()
  
# 启动线程,开启多次任务并行处理
threads = []
for i in range(5):
    t = threading.Thread(target=worker, args=(q, i))
    t.start()
    threads.append(t)
  
# 入队任务
for i in range(20):
    q.put(i)
  
# 阻塞,直到所有任务完成
q.join()

# 停止线程,退出任务
for i in range(5):
    q.put(None)
for t in threads:
    t.join()