From: Mason Kelsey <masonkelsey@...>
Date: 2009-10-02T14:38:46+09:00
Subject: Re: Control of Priority Queue Order? And size limits on queues?

--0016364275f76666390474ed2d17
Content-Type: text/plain; charset=ISO-8859-1

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

On Thu, Oct 1, 2009 at 8:26 PM, Christopher Dicely <cmdicely@gmail.com>wrote:

> On Wed, Sep 30, 2009 at 1:50 PM, Mason Kelsey <masonkelsey@gmail.com>
> 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.
>
>

--0016364275f76666390474ed2d17--