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

"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

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: Re: looking for a Priority Queue
by tachyon (Chancellor) on May 07, 2002 at 14:22 UTC

    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