前言:
当前大家对“heappython”大约比较关心,我们都想要剖析一些“heappython”的相关文章。那么小编同时在网络上汇集了一些关于“heappython””的相关资讯,希望我们能喜欢,兄弟们快快来了解一下吧!关于我
一个有思想的程序猿,终身学习实践者,目前在一个创业团队任team lead,技术栈涉及Android、Python、Java和Go,这个也是我们团队的主要技术栈。
Github:
微信公众号:终身开发者(angrycode)
栈、队列和优先级队列都是非常基础的数据结构。Python作为一种“编码高效”的语言,对这些基础的数据结构都有比较好的实现。在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现。
0x00 栈(Stack)
栈是一种LIFO(后进先出)的数据结构,有入栈(push)、出栈(pop)两种操作,且只能操作栈顶元素。
在Python中有多种可以实现栈的数据结构。
1、list
list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作。只不过用list实现栈性能不是特别好。
因为list内部是通过一个动态扩容的数组来实现的。当增减元素时就有可能会触发扩容操作。如果在list的头部增减元素,也会移动整个列表。
如要使用list来实现一个栈的话,可以使用list的append()(入栈)、pop()(出栈)方法。
>>> s = []>>> s.append('one')>>> s.append('two')>>> s.append(3)>>> s['one', 'two', 3]>>> s.pop()3>>> s.pop()'two'>>> s.pop()'one'>>> s.pop()IndexError: pop from empty list
2、collections.deque
deque类是一种双端队列。在Python中它就是一个双向列表,可以以常用时间在两端执行添加和删除元素的操作,非常高效,所以它既可以实现栈也可以实现队列。
如果要在Python实现一个栈,那么应该优先选择deque,而不是list。
deque的入栈和出栈方法也分别是append()和pop()。
>>> from collections import deque>>> s = deque()>>> s.append('eat')>>> s.append('sleep')>>> s.append('code')>>> sdeque(['eat', 'sleep', 'code'])>>> s.pop()'code'>>> s.pop()'sleep'>>> s.pop()'eat'>>> s.pop()IndexError: pop from an empty deque
3、queue.LifoQueue
顾名思义,这个就是一个栈。不过它是线程安全的,如果要在并发的环境下使用,那么就可以选择使用LifoQueue。
它入栈和出栈操作是使用put()和get(),其中get()在LifoQueue为空时会阻塞。
>>> from queue import LifoQueue>>> s = LifoQueue()>>> s.put('eat')>>> s.put('sleep')>>> s.put('code')>>> s<queue.LifoQueue object at 0x109dcfe48>>>> s.get()'code'>>> s.get()'sleep'>>> s.get()'eat'>>> s.get()# 阻塞并一直等待直到栈不为空0x01 队列(Queue)
队列是一种FIFO(先进先出)的数据结构。它有入队(enqueue)、出队(dequeue)两种操作,而且也是常数时间的操作。
在Python中可以使用哪些数据结构来实现一个队列呢?
1、list
list可以实现一个队列,但它的入队、出队操作就不是非常高效了。因为list是一个动态列表,在队列的头部执行出队操作时,会发生整个元素的移动。
使用list来实现一个队列时,用append()执行入队操作,使用pop(0)方法在队列头部执行出队操作。由于在list的第一个元素进行操作,所以后续的元素都会向前移动一位。因此用list来实现队列是不推荐的。
>>> q = []>>> q.append('1')>>> q.append('2')>>> q.append('three')>>> q.pop(0)'1'>>> q.pop(0)'2'>>> q.pop(0)'three'>>> q.pop(0)IndexError: pop from empty list
2、collections.deque
从上文我们已经知道deque是一个双向列表,它可以在列表两端以常数时间进行添加删除操作。所以用deque来实现一个队列是非常高效的。
deque入队操作使用append()方法,出队操作使用popleft()方法。
>>> from collections import deque>>> q = deque()>>> q.append('eat')>>> q.append('sleep')>>> q.append('code')>>> qdeque(['eat', 'sleep', 'code'])# 使用popleft出队>>> q.popleft()'eat'>>> q.popleft()'sleep'>>> q.popleft()'code'>>> q.popleft()IndexError: pop from an empty deque
3、queue.Queue
同样地,如果要在并发环境下使用队列,那么选择线程安全的queue.Queue。
与LifoQueue类似,入队和出队操作分别是put()和get()方法,get()在队列为空时会一直阻塞直到有元素入队。
>>> from queue import Queue>>> q = Queue()>>> q.put('eat')>>> q.put('sleep')>>> q.put('code')>>> q<queue.Queue object at 0x110564780>>>> q.get()'eat'>>> q.get()'sleep'>>> q.get()'code'# 队列为空不要执行等待>>> q.get_nowait()_queue.Empty>>> q.put('111')>>> q.get_nowait()'111'>>> q.get()# 队列为空时,会一直阻塞直到队列不为空
4、multiprocessing.Queue
多进程版本的队列。如果要在多进程环境下使用队列,那么应该选择multiprocessing.Queue。
同样地,它的入队出队操作分别是put()和get()。get()方法在队列为空,会一直阻塞直到队列不为空。
>>> from multiprocessing import Queue>>> q = Queue()>>> q.put('eat')>>> q.put('sleep')>>> q.put('code')>>> q<multiprocessing.queues.Queue object at 0x110567ef0>>>> q.get()'eat'>>> q.get()'sleep'>>> q.get()'code'>>> q.get_nowait()_queue.Empty>>> q.get()# 队列为空时,会一直阻塞直到队列不为空0x02 优先级队列(PriorityQueue)
一个近乎排序的序列里可以使用优先级队列这种数据结构,它能高效获取最大或最小的元素。
在调度问题的场景中经常会用到优先级队列。它主要有获取最大值或最小值的操作和入队操作。
1、list
使用list可以实现一个优先级队列,但它并不高效。因为当要获取最值时需要排序,然后再获取最值。一旦有新的元素加入,再次获取最值时,又要重新排序。所以并推荐使用。
2、heapq
一般来说,优先级队列都是使用堆这种数据结构来实现。而heapq就是Python标准库中堆的实现。heapq默认情况下实现的是最小堆。
入队操作使用heappush(),出队操作使用heappop()。
>>> import heapq>>> q = []>>> heapq.heappush(q, (2, 'code'))>>> heapq.heappush(q, (1, 'eat'))>>> heapq.heappush(q, (3, 'sleep'))>>> q[(1, 'eat'), (2, 'code'), (3, 'sleep')]>>> while q: next_item = heapq.heappop(q) print(next_item)(1, 'eat')(2, 'code')(3, 'sleep')
3、queue.PriorityQueue
queue.PriorityQueue内部封装了heapq,不同的是它是线程安全的。在并发环境下应该选择使用PriorityQueue。
>>> from queue import PriorityQueue>>> q = PriorityQueue()>>> q.put((2, 'code'))>>> q.put((1, 'eat'))>>> q.put((3, 'sleep'))>>> while not q.empty(): next_item = q.get() print(next_item)(1, 'eat')(2, 'code')(3, 'sleep')0x03 总结一下
很多基础的数据结构在Python中已经实现了的,我们不应该重复造轮子,应该选择这些数据结构来实现业务需求。
collections.deque是一种双向链表,在单线程的情况下,它可以用来实现Stack和Queue。而heapq模块可以帮我们实现高效的优先级队列。
如果要在多并发的情况下使用Stack、Queue和PriorityQueue的话,那么应该选用queue模块下类:
实现Stack的queue.LifoQueue实现Queue的queue.Queue或multiprocessing.Queue实现PriorityQueue的queue.PriorityQueue以上这些类都有put()和get()方法,且get()会在栈/队列为空时阻塞。0x04 学习资料Python Tricks: A Buffet of Awesome Python Features——Dan Bader
标签: #heappython