# Control of Priority Queue Order? And size limits on queues?

Discussion in 'Ruby' started by Mason Kelsey, Sep 30, 2009.

1. ### Mason KelseyGuest

[Note: parts of this message were removed to make it a legal post.]

I've successfully used the Priority Queue to sort ascending items for
solving the 8-puzzle problem. I noticed that the Priority Queue method had
a unique way of sorting items with matching keys. It puts the newest items
furtherest from the top. The older a matching item is, the further it is
towards the top. That is OK by me as it essentially added a negative g(n)
node value to the h(n) heuristic value that aided in the A* best-first
have slowed the program down by going down fruitless paths and
probably would create a less optimal path to the results.

The code I used was: open_queue = PQueue.new(proc{|x,y| x[0]<y[0]}), where I
was sorting on the first element of each item.

But for future use, is there a way to force the Priority Queue to always add
the newest matching item in front of the older matching items? Please be
aware I am not asking for a descending sort, which I know how to do.

Also, related to unsolvable problems, is there a limit to the size of the
Priority Queue? Or, perhaps a better way to ask is what would limit the
size of the Priority Queue. I would have to guess that the same limits
would apply to any type of queue. I've noticed that searching the Priority
Queue for a matching value item is very slow in Ruby. I had over 1300 items
in my Priority Queue by the time I killed the run as it had run all night to
just get to that size. Yes, I realize this is an interpreted language. I'm
just trying to push Ruby to its limits to see if it breaks.

Does anyone know?

No Sam

Mason Kelsey, Sep 30, 2009

2. ### Christopher DicelyGuest

Wouldn't that stop being a priority queue and be a priority stack?
A Priority Queue is not an ideal structure for searching, its designed
for the use where you are going to be pulling stuff off in order of
priority and, within priorities, order received.

If you want something that is optimized for searching for matches, you
need a different structure; if you just need equality matching on the
value (or part of a composite value), you can probably use a Ruby
Hash, otherwise, you may need something special.

Christopher Dicely, Oct 2, 2009

3. ### Mason KelseyGuest

[Note: parts of this message were removed to make it a legal post.]

No, it would still be a priority queue if I could control the order of
MATCHING key values. I still want the unmatched key values to be sorted
automatically in order ascending or descending as I push new entries onto
the queue.

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.

I experimented with popping off the oldest matching entry and pushing it
right back on to put it BEHIND the other matching entries, but it was so
slow that it was a bad idea. Pushes onto Priority Queues is the slowest
part of my code because of the automated sort.

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.

Reviewing the Enumeraable Class (mixed in with the Array Class) I noticed
there is a sort_by method that I might be able to use to have a major sort
on the heuristic_value (key) and minor sort on the node_level. I'll play
with it. It could be expensive with time.

Does this make sense to you?

You are right about Priority Queues not being ideal for matching searches.
It is painfully slow. Fortunately I only need a queue that is a few hundred
entries at the most, although a queue with more than 100 entries can start
to drag. I will explore other options in a future version of my first
significant Ruby program that solves the 8-puzzle.

Regardless, I turned in my program today for the Advanced
Artificial Intelligence class I'm taking and got credit for it.

Thanks for trying.

No Sam

Mason Kelsey, Oct 2, 2009
4. ### Josh CheekGuest

[Note: parts of this message were removed to make it a legal post.]

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.

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
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_(data_structure)

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.

Josh Cheek, Oct 2, 2009
5. ### Walton HoopsGuest

Your focusing on the definition of Priority, and ignoring the Queue part
A queue is defined as a First-in-First-out (FiFo) data structure. In other
words if I add 'B' to the Queue, then 'A', when I read from the Queue I
get 'B'
then 'A'.

A priority queue changes this behavior, in that items with the higher
priority
go first. Thus assuming 'B1' and 'B2' are considered equal priority, if I
'B1' to the Queue, then 'B2', when I read the Queue I MUST first get 'B1'
then
'B2' or it ceases to be a Queue.

A Stack on the other hand in a First-in-Last-out (FiLo) data structure. So
if I
add 'B1' then 'B2' and read the Stack, I get out 'B2' then 'B1' in that
order.

Thus, what you are looking for is a Priority Stack, not a Priority Queue.

To answer your question, I don't know of a pre-built Priority Stack for
Ruby,
but that doesn't mean it doesn't exist.

Hope this clears things up!

Walton Hoops, Oct 2, 2009
6. ### John W HigginsGuest

[Note: parts of this message were removed to make it a legal post.]

Mason,

You will need to change the matching process to be smart enough to handle
what you want - fortunately it's fairly easy to do with a couple of changes.
You can do something along either of the following (gist here for easier

In essence we just create a class to hold your items that is aware of how
you want to sort - you can either subclass
an array if you want to keep that concept or dump the array and move your
records to their own class.

require 'pqueue'

pq = PQueue.new proc{|x, y| x.compare(y)}

#Do either the Array monkey_patch or Record concept

class Array
def compare(other_record)
#We want to return TRUE if this record should take
#priority over the other record in the queue
if self[0] == other_record[0]
insert_time > other_record.insert_time
else
self[0] < other_record[0]
end
end

def queue(pq)
@insert_time = Time.now()
pq.push(self)
end
end

x = [1, 2, 3, 4]
x.queue(pq)
sleep 1
y = [1, 2, 3, 4]
y.queue(pq)

until pq.empty?
itm = pq.pop
p itm
p itm.insert_time
end

class Record
attr_accessor :f1, :f2, :f3, :f4

def initialize(f1, f2, f3, f4)
@f1, @f2, @f3, @f4 = f1, f2, f3, f4
end

def compare(other_record)
#We want to return TRUE if this record should take
#priority over the other record in the queue
if f1 == other_record.f1
insert_time > other_record.insert_time
else
f1 < other_record.f1
end
end

def queue(pq)
@insert_time = Time.now()
pq.push(self)
end
end

x = Record.new(1, 2, 3, 4)
x.queue(pq)
sleep 1
y = Record.new(1, 5, 6, 7)
y.queue(pq)

until pq.empty?
p pq.pop
end

John

John W Higgins, Oct 2, 2009