一、什么是deque?
deque是Python标准库collections中的一个模块,是双向队列(double-ended queue)的缩写。双向队列是一种具有队列和栈的性质的数据结构,可以在两端进行元素的插入和删除操作。deque比Python中内置的list容器在两端插入和删除元素有更好的性能表现。
from collections import deque d = deque() d.appendleft(1) # 在队列左边插入元素1 d.appendleft(2) # 在队列左边插入元素2 d.append(3) # 在队列右边插入元素3 d.append(4) # 在队列右边插入元素4 print(d) # deque([2, 1, 3, 4]) print(d.pop()) # 弹出队列右边的元素4 print(d.popleft()) # 弹出队列左边的元素2 print(d) # deque([1, 3])
二、优势在哪里?
deque的内部采用了双向链表(doubly-linked list)的数据结构,支持O(1)时间复杂度的元素插入和删除操作。相比之下,Python内置的list的内部结构是数组(array),在其左边插入或删除元素需要对整个数组进行移动,时间复杂度是O(n)。因此,在要求频繁的在list的头部或尾部进行插入和删除操作时,deque比list的性能会更好。
三、实例演示:deque加速程序运行
下面我们来看一个例子,比较使用deque和list插入和删除元素的时间差异:
import timeit from collections import deque def insert_list(): l = [] for i in range(10000): l.insert(0, i) def insert_deque(): d = deque() for i in range(10000): d.appendleft(i) print('list插入操作:', timeit.timeit('insert_list()', 'from __main__ import insert_list', number=100)) print('deque插入操作:', timeit.timeit('insert_deque()', 'from __main__ import insert_deque', number=100)) def delete_list(): l = list(range(10000)) for i in range(10000): l.pop(0) def delete_deque(): d = deque(range(10000)) for i in range(10000): d.popleft() print('list删除操作:', timeit.timeit('delete_list()', 'from __main__ import delete_list', number=100)) print('deque删除操作:', timeit.timeit('delete_deque()', 'from __main__ import delete_deque', number=100))
结果显示,deque相比list要快得多。在插入操作上,deque的效率是list的132倍;在删除操作上,deque的效率是list的15倍。
四、使用deque进行多线程编程
在多线程编程中,线程的同步和互斥非常重要。deque可以作为线程安全的队列使用,支持线程安全的消费者生产者模式,实现同步和互斥。两个线程可以在同一个deque中生产和消费数据。使用锁可以确保多个线程没有冲突,访问队列的顺序是线程安全的,不会发生数据竞争。
from collections import deque import threading import time cond = threading.Condition() deque_list = deque() class Producer(threading.Thread): def run(self): nums = range(5) global deque_list with cond: for num in nums: deque_list.append(num) print('Produced:', num) time.sleep(1) cond.notify() class Consumer(threading.Thread): def run(self): global deque_list with cond: while True: if not deque_list: print('Waiting for elements...') cond.wait() print('Notified for elements...') num = deque_list.popleft() print('Consumed:', num) time.sleep(1) Producer().start() Consumer().start()
上述代码中,我们定义了一个条件锁cond和一个空deque列表deque_list。生产者和消费者各自占用一个线程,在生产数据时使用条件锁进行同步,检查deque_list是否为空,为空的话就调用wait()函数进行等待。在消费数据时也使用条件锁进行同步,当生产者把数据加到deque_list中后调用notify()函数进行通知,消费者能够继续取出数据进行消费。
五、结语
deque是Python标准库中一个强大的数据容器,在需要高效率地进行队列操作时,使用deque可以让程序快速运行。同时,deque作为线程安全的数据容器,可以帮助在多线程编程中实现同步和互斥,有效提高程序运行效率。