in reply to Re: Re: Re: looking for a Priority Queue
in thread looking for a Priority Queue

Actually if you RTFS a little more carefully you will see that 1) it never sorts the list (ever) 2) the only thing that gets sorted is the priorities array (which consists only of the n priority levels present) and 3) the only time it does this sort is when either a new (previously unknown) priority level is added or a priority level needs to be deleted as there are no more items of this priority present in the heap. It checks for the presence of a priority level via a hash key (rather than searching the whole priority array as a further speed hack..... 

sub add {
   # blah
   unless (exists $self->{'.queue'}->{$priority}) {
       $self->{'.queue'}->{$priority} = ();
       $self->_sort_priorities;
   }

[download]

cheers

tachyon

s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: looking for a Priority Queue
by educated_foo (Vicar) on May 07, 2002 at 08:44 UTC
    "Actually if you RTFS a little more carefully"...

    Had you PTFP, you might have realized that the link went nowhere -- at least it was a "not found" for me. You're right that I didn't read your code very carefully, but now that I have, I'm guessing it doesn't do what the original poster wanted. Or more accurately, your benchmark doesn't reflect its being used in the way he would use it, since it only uses a single priority. Try this instead: 

    use Priority;
my $q = new Priority;
my $time = time;
$q->add(1,$_) for 1..1000000;
$q->pop for 1..1000000;
print "Did a million in ",time - $time, " seconds";

    [download]
    /s
[reply]
[d/l]

      Hi you are of course correct and incorrect. The algorithm implemented by this module (now Heap::Priority on CPAN - when it gets listed) assumes that the item count >> number of priority levels.

      I have improved the priority level sort efficiency so that all that happens is that a new priority level is sorted to its correct place which is O(n) rather than the less efficient way it was done.

      As it currently stands it will add() and pop() 100,000 items into 100 different levels in 9 seconds or into 1000 levels in 40 seconds. Yes that is definitely a geometric decay as the number of priority levels go up.... 

      use Heap::Priority;
my $n = 100000;
my $start = time;
my $h = new Heap::Priority;
$h->add($_, $_%1000) for 1..$n;
$h->pop for 1..$n;
print "Did $n in ", time - $start, " seconds";
__DATA__
Did 100000 in 40 seconds

      [download]

      cheers

      tachyon

      s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print

[reply]
[d/l]
        now Heap::Priority on CPAN - when it gets listed

        This name would be very confusing. People would think either "heap" or "priority queue" in the textbook form of a heap-ordered binary tree. While your module will appear to do something similar, it doesn't have O(log(n)) performance when dealing with n items with n different priorities. At the very least, it should be stated prominently in the POD that inserting n items with different priorities is O(n^2 log n). I would prefer to see it under a different name.

        btw, here's FOLDOC's definition of a heap (sense 2).

        /s

[reply]

In Section Seekers of Perl Wisdom