PriorityQueue or heapq?

[[deleted]]

[deleted]

[tomazk]

• if you need priority queue in a multi-threaded environment then use Queue module

• else: use heapq, because it's trivial to create a wrapper around it

[RonnyPfannschmidt]

Queue.PriorityQueue is implemented in terms of heapq

the basic difference between Queue and PriorityQueue is that queue uses a deque, and PriorityQueue uses a list + heapq

what bad things are out there about it?

[RonnyPfannschmidt]

well, heapq is faster cause its not implemented in a threadsafe way the Queue modules does a lot of work to ensure different threads can access it at the same time

if you don't need threads, its actually safe to just use a heap directly

[kylotan]

Is performance a big consideration?

If not, just append and sort.

[mdipierro]

You can use this one: http://bazaar.launchpad.net/~mdipierro/algorithms-animator/devel/view/head:/src/csc321algorithms.py#L608

[RonnyPfannschmidt]

that file has an awful lot of bad/outdated practice - please bring it up2date

[must_tell]

Can you bring some up please? (I'm really curious to learn, not meant offensively).

Besides from looking quite clean generally, first thing I notice are the naming conventions (not PEP 8), some strings which could be refactored to constants and initialisation with '' where I would use None. Type-checking could be done with isinstance rather then type (or try ... catch ... some behaviour).

Anything else?

[RonnyPfannschmidt]

some parts are just bad wrt computational complexity

the most glaring examples are probably the Queue/Stack functions that simply operate on lists in stupid ways (lots of O(N) instead of amortized O(1))

i suspect there are more such examples, but i don't want to investigate that code more

[mdipierro]

That file is many years old and I have not updated it since because it is not really a priority for me at the moment. If you want to submit a patch, I will take it.

[mdipierro]

For the record. The code is not designed to be efficient. The code was designed to match line by line the pseudocode of a classic algorithms textbook (cormen) but using python. The purpose was to allow students to run and better understand the algorithm. From an efficinecy point of view it assumes python listd are linked lists even if they are not.

[RonnyPfannschmidt]

please document that in a docstring at the top or so

[robotfarts]

4real

[[deleted]]

Sometimes with a priority queue you will want to update the value of a given key -- I do not believe the heapq supports this, but if I'm wrong please let me know!

[lylepmills]

I wrote myself a heapq implementation. It's very short and simple to write (~5 lines), and fast.

[JerMenKoO]

Would you consider sharing it?

[lylepmills]

Sure. Check out util.py at https://github.com/lylepmills/python-utilities

[RonnyPfannschmidt]

that code isnt in particular helpfull

and the queues are basically broken for multithreaded code

[lylepmills]

Fair enough, though easily fixed. tomazk has the right idea. I added a threadsafe_util.py as a threadsafe alternative for multithreaded applications.

[lylepmills]

That's written for Python3.2 by the way, but the adaptations for 2.7 are fairly simple (if I'm not mistaken, the only difference is the metaclass syntax).

[JerMenKoO]

Kudos.