Closed GoogleCodeExporter closed 8 years ago
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.
Original comment by glewe...@gmail.com
on 20 Jul 2012 at 3:40
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.
Original comment by neal...@gmail.com
on 30 Jul 2012 at 4:25
Attachments:
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.
Original comment by wit...@gmail.com
on 20 May 2013 at 11:07
Brand new implementation coming.
Original issue reported on code.google.com by
neal...@gmail.com
on 19 Jul 2012 at 5:07