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

Ruby
1

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
algorithm. If the newest matching item had been added at the top, it
would
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

2

On Wed, Sep 30, 2009 at 1:50 PM, Mason K. [email protected]
wrote:

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?

Wouldn’t that stop being a priority queue and be a priority stack?

I’ve noticed that searching the PriorityQueue for a matching value item is
very slow in Ruby.

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.

3

Thanks for the reply Christopher.

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

4

On Thu, 01 Oct 2009 23:38:46 -0600, Mason K. [email protected]
wrote:

Thanks for the reply Christopher.

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.

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
add
‘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!

5

On Fri, Oct 2, 2009 at 12:38 AM, Mason K. [email protected]
wrote:

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.

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.

6

Mason,

On Wed, Sep 30, 2009 at 1:50 PM, Mason K. [email protected]
wrote:

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.

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
reading - Multi-Sort pqueue record · GitHub)

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
attr_reader :insert_time
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
attr_reader :insert_time

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