From: Josh Cheek Date: 2009-10-02T15:54:26+09:00 Subject: Re: Control of Priority Queue Order? And size limits on queues? --000e0cd25002ea9c8d0474ee3be1 Content-Type: text/plain; charset=ISO-8859-1 On Fri, Oct 2, 2009 at 12:38 AM, Mason Kelsey wrote: > > The way the Priority Queue works now is that if you push several entries > into the queue, all with matching key values, say the same heuristic value > in an A* best first search, the OLDEST (the one pushed in earliest) goes to > the top and the NEWEST goes to the bottom of that group of matching key > entries, that is, inserted AFTER the first entry with the same key value. > For example, let's say you are pushing entries onto the PQueue that have > key > values lower than any other entries already on the PQueue and the PQueue is > sorted in ascending order. The several entries with matching lower key > values all get sorted to the top of the queue. What I'm wondering is if > there is a way to change the Priority Queue so the LAST of the inserted > matching entries goes in front of the others so that with the next pop you > get the newest matching entry instead of the oldest? I'm beginning to > think > that PQueue doesn't have that capability. > > Wouldn't that make it out of order? If so, then it would no longer be a priority queue. You could probably extend or wrap the code to handle this, but you should really think about whether that is what you need. Perhaps add another class which houses a priority queue and a regular queue, determines which an item to be inserted belongs to, and when it is asked for the next object, determines which to extract from. > Since there is a sort method for array, perhaps I should just try using an > ordinary array (of arrays) and sort the array after each entry is added. > That must be what the PQueue is doing anyway. > > Priority queues are usually implemented as heaps, which means insertion and extraction takes O( lg n ) time, where as pushing then sorting would take O( n lg n ), considerably worse. You could do a sorted insertion, which would take O( n ), much better, but still nowhere near as good as the heap. As a quick example, say you had 1024 elements, then inserting into a priority queue takes a maximum of lg(1024) = a10 + c steps Moving all the elements down to make room for the one you are inserting in an already sorted array takes a1024 + c steps And pushing onto the end, then resorting takes 1024 * lg(1024) = a1024 * b10 + c = ab10240 + c steps Where a, b, and c are some constant value. Not necessarily the same constant between the three different implementations, but the point is that the base number of steps grows much much slower for the heap implementation, so as the number of elements the priority queue houses grows very large, the heap will be faster, even if it's a and c are much larger. http://en.wikipedia.org/wiki/Heap_%28data_structure%29 If you are still using the code from ftp://ftp.math.kobe-u.ac.jp/pub/knot/pqueue.rb You can see that it does implement as a heap. You can view the array the items are stored in by calling .qarray on your priority queue. Also, you could possibly reduce the search time by writing your own search method, which takes into account the structure of the priority queue. Meaning you can rule out entire branches of the tree if the priority of that branch's root is less than the priority of the element you are searching for. --000e0cd25002ea9c8d0474ee3be1--