PriorityQueue implementation is quadratic for our purposes - __contains__ does linear search about aima-python HOT 3 OPEN

the Queue.PriorityQueue class is appropriate when you have to handle parallel 
access to the queue (in multi-threads programs). For our purpose, I think the 
heapq module is preferable.

I've written a fix to make the function PriorityQueue.__contains__() run in 
constant time, rather than being linear in the number of items on the queue.  
It simply adds a hash table for membership testing.   I've pushed it to a 
branch on github:

 https://github.com/nealmcb/aima-python/tree/fasterPriorityQueue

It sped up my solution for the second problem in ai-class.org unit 22 "Optional 
NLP Programming" by a huge factor.

Note that __getitem__() and __delitem__() are still linear time, but could 
easily be improved also if necessary.  But in my current usage they aren't 
hotspots.

I didn't switch to use the standard hashq or Queue.PriorityQueue modules since 
they don't provide a constant-time membership test, but it still would seem 
better to use one of them.

My fix also includes another commit which improves the doctests a bit.  They 
now test membership after pops.

A patch is attached.

Looking up the hash of a key is incorrect because different keys may have the 
same hash, right? I think this could be fixed to store the actual keys, though.