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

"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

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