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

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

  1. Mason Kelsey

    Mason Kelsey Guest

    [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
    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
     
    Mason Kelsey, Sep 30, 2009
    #1
    1. Advertisements

  2. 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
    #2
    1. Advertisements

  3. Mason Kelsey

    Mason Kelsey Guest

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

    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
     
    Mason Kelsey, Oct 2, 2009
    #3
  4. Mason Kelsey

    Josh Cheek Guest

    [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
    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_(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
    #4
  5. Mason Kelsey

    Walton Hoops Guest

    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!
     
    Walton Hoops, Oct 2, 2009
    #5
  6. [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
    reading - http://gist.github.com/199934)

    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
     
    John W Higgins, Oct 2, 2009
    #6
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.