如何在Python中实现优先级队列? [英] How to implement Priority Queues in Python?

查看:179
本文介绍了如何在Python中实现优先级队列?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

很抱歉这样一个愚蠢的问题,但是Python文档令人困惑.

Sorry for such a silly question but Python docs are confusing.. .

链接1:队列实施 http://docs.python.org/library/queue.html

它说s Queue具有优先级队列的构造.但是我找不到如何实现它.

It says thats Queue has a contruct for priority queue. But I could not find how to implement it.

class Queue.PriorityQueue(maxsize=0)

链接2:堆实现 http://docs.python.org/library/heapq.html

在这里他们说我们可以使用heapq间接实现优先级队列

Here they says that we can implement priority queues indirectly using heapq

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue'

哪个是python中最有效的优先级队列实现?以及如何实施?

Which is the most efficient priority queue implementation in python? And how to implement it?

推荐答案

队列模块中的版本为

The version in the Queue module is implemented using the heapq module, so they have equal efficiency for the underlying heap operations.

也就是说, Queue 版本较慢,因为它添加了锁,封装和不错的面向对象的API.

That said, the Queue version is slower because it adds locks, encapsulation, and a nice object oriented API.

heapq文档中显示的优先级队列建议旨在显示如何向优先级队列添加其他功能(例如排序稳定性和更改先前排队任务的优先级的功能).如果您不需要这些功能,则基本的 heappush heappop 功能将为您提供最快的性能.

The priority queue suggestions shown in the heapq docs are meant to show how to add additional capabilities to a priority queue (such as sort stability and the ability to change the priority of a previously enqueued task). If you don't need those capabilities, then the basic heappush and heappop functions will give you the fastest performance.

这篇关于如何在Python中实现优先级队列?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆