Can you give some examples where it's having problems? Perhaps we can figure out what's going on. To be fair, I haven't used Heap.pm, but I did notice that it's tests are not terribly comprehensive, so I'm not surprised. I confess a desire to see what's not working and start writing tests for it :)

If you happen to have a copy of "Mastering Algorithms with Perl", by O'Reilly, they have a heap implementation in there along with an excellent discussion. Perhaps rolling your own my help?

Cheers,
Ovid

New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)

Thanks for the book tip... After skimming through the "Mastering Algorithms" section on heaps and reading through the Heap.pm source, I was able to build a small script that seems to work:

#!/usr/bin/perl -wT
use strict;
use Heap::Binary;
use Heap::Elem::Num;

my $heap = Heap::Binary->new;

for (25,33,107,5,42,29) {
  my $elem = Heap::Elem::Num->new($_);
  $heap->add( $elem );
}

my $min = $heap->extract_minimum();

print "Min: " . $min->val . "\n";   # prints 5
[download]

Unfortunately this doesn't exactly match the usage explained in the POD. It could be just a documentation bug, but it worries me a bit.

-Blake

I just attempted to download and install Heap. Its example broke for me upon attempting call add. (Not autoloaded.) Perl 5.6.1 on Linux here.

Is anyone maintaining it? Is it worthwhile to file a bug report?

I got the same error with Perl 5.8 on Linux. After a quick search turned up mixed reviews for the module, I decided to post here before making my next move. At the very least, I'll email the author of Heap with a bug report.

-Blake

The resource I am optimizing for here is memory. I have a mod_perl process that slurps up a large dataset from a database, sorts it, then displays the first N items. This happens to balloon the memory consumption of the apache process to an unacceptable level.

One approach to this, of course, is to sort the data in the database, but in this case I need the ability to define the sort function as arbritrary perl code.

Heap sorting is attractive because selecting the smallest M elements from a dataset of size N (N being much larger than M) requires storing only M elements in memory at any one time. This would be a huge win for me.

A heap is a datastructure that makes two operations very efficient: inserting a new element, and selecting (or removing) the largest element. The pseudo-code for my algorithm would look something like this:

# select the smallest $M elements;
while ($new_element = $dbh->fetchrow) {
  if ($heap->size < $M) {               # build a heap of size M
    $heap->insert($new_element);
  } elsif ($element < $heap->largest) { # maintain a heap containing
                                        # the smallest M elements 
                                        # seen so far
    $heap->remove_largest;
    $heap->insert($element);
  }
}
[download]

Therefore, I'm looking for a decent heap implementation and my first impression of Heap.pm was somewhat discouraging. I have several paths I can take from here, but before I go hacking up Heap.pm I was wondering if there might be a better place to start.

-Blake

I have a mod_perl process that slurps up a large dataset from a database, sorts it, then displays the first N items. This happens to balloon the memory consumption of the apache process to an unacceptable level.

An obvious question, perhaps, but have you ruled out getting the database to do the work for you? That'd be a no-brainer if the column you're interested in is indexed. I'm guessing it isn't. Still, having the database do the sort might still be faster than scanning the entire table, pulling the data across a process boundary a row at a time, and then filtering it in the Apache process.

Assuming you have a fairly large table, here's an ugly heuristic you might try: Probe the first 2*M rows of the table, sort, and find the M'th largest value. Then run a query that does a sort on the database side, subsetting the data before sorting by adding a WHERE clause to reject any row whose target column has a value greater than the M'th value you found the first time through. You can tune this by trying 3*M rows, 4*M rows, etc. The idea is to reduce the set that the database needs to sort.

Letting the datbase do the sort is a good approach, but I was hoping for a more general, memory efficient solution that allows for arbitrary perl comparison routines.

Its a common enough situation that I would like to create a subroutine that returns the rows I want and takes a database handle, a sorting coderef, M, and an optional offset. I'm envisioning something like:

my $sortedrows = db_heap_sort($dbh, $coderef, $M, $offset);
[download]

The question is, is there a perl heap implementation that would be suitable for implementing the above sub. Heap.pm seems like the obvious choice, but I have doubts about its current status.

I have emailed the Heap.pm author, and will follow up with any new information I find out.

-Blake

If those are rows in a database, I agree with dws, just let database do it.

If that particular column is not indexed, I suggest index it, as you need it.

"order by" is usually not too expansive, especially when it only involves indexed range scan.

Depends on your database, some database directly support syntax that allows to retrieve first N rows.

Isn't there a solution posted already with working code which solves exactly this memory problem? It could readily be sped up substantially, and needs more testing though. But consider it proof of concept...

No comments on Heap not having ever used it.

However, unless you are dynamically adding and removing items to your dataset wouldn't something like:

sub smallest_n (&\@$) {
    my ($cmp, $arrayref, $n) = @_;
    return unless $n && @$arrayref;
    $n = @$arrayref if @$arrayref < $n;
    my @results = sort $cmp @$arrayref[0..$n-1];
    local ($a, $b);
    $a = pop @results;
    for (my $i = $n; $i < @$arrayref; $i++) {
        $b = $arrayref->[$i];
        if ($cmp->() == 1) {
            @results = sort $cmp (@results, $b);
            $a = pop @results;
        };
    };
    return (@results, $a);
};

use Test::More tests => 1;
use List::Util qw(shuffle);
my @a = shuffle (1..100000);
my @b = smallest_n {$a <=> $b} @a, 5;
is_deeply [@b], [1,2,3,4,5];
[download]

be easier? The support for the heap datastructure will add a fair bit of overhead with your large dataset, so I wouldn't use one unless you need it.

Update: totally misready what blakem was proposing. D'oh.

The reason that someone with a large dataset might want a heap is that they don't want to have very much of the dataset in memory at once. With a Heap you can add an element at a time until you have your limit, and from there on you can add one and remove the biggest each time.

When you are done you can then just extract off all of the elements in the heap, and you have the smallest N of them from largest to smallest. Without excessive memory usage.

Erm. No :-)

You have to add all the items from the dataset to the heap before you can remove the N lowest (or highest, depending on the direction your grow your tree).

Yes, you could have the heap as an out-of-memory structure. However, if the dataset is on disk you can just read it in element by element and use the algorithm I proposed. It's still going to be less expensive in time and space than creating a heap.

Unless you are goin to be adding and removing entries from the data set and need to keep it ordered a heap is overkill for the problem as stated.

Your algorithm runs in Omega (N k log k), where N is the size of the set, and you are interested in the k smallest elements. Which is pretty lousy. With k for instance N / 100, your algorithm is worse than doing a bubble sort of the entire set, and getting the k smallest from the sorted set.

Abigail

Note that I used the quicksort rather than heapsort because I assumed that the issue is memory usage, and quicksort is easier to do.

1. First take N elements from the begining of the unsorted array, and form a new array.
2. Sort the new array, which would be much fast, assuming N is much smaller than the original array size.
3. Go thru the rest array element in the original array, insert a element into the sorted array, if it is smaller than the largest element of the new array, and does not exist in the new array, and also get rid of the largest element in the new array.
4. This algorithm goes thru the entire original array, but only for comparing, and most of the time, no extra effort (inserting) other than comparing is needed.

A heap is a specialized datastructure that can be thought of as an "automatically sorted array" given a somewhat scaled down definition of "sorted". Sorted in this case means that the largest element is always easy to find and remove, and inserting new elements is also easy.

Given that, our steps to find the smallest M elements would be:

1. Build a heap from our first M items
2. Compare next item to largest element in heap
3. Replace largest with new if new < largest
4. Repeat steps 2 and 3 for all remaining items

As you can see, this is very similar to the strategy you proposed. In fact, you could view heaps as a datastructure designed specifically to implement this algorithm efficiently.

-Blake

In step 3, instead of going thru the entire original array, you can chop the original array into pieces, say each piece contains 10 * N element (tweak with this 10, it could be 5, could be 50...). Sort each piece (we are sorting some smaller arrays), then only take the first N elements of the soted piece, and go thru them.

How is this an improvement (he asks curiously ;-) I don't see how creating a sorting several subsets of the data can be cheaper in time or space than a single pass through everything.

adrianh is obviously right about this.

#!/usr/bin/perl
    
use strict;
use warnings;
     
my @heap;

sub heapify;
sub heapify {
    my $idx = shift;

    my $min = $idx;
    for my $try (2 * $idx + 1, 2 * $idx + 2) {
        $min = $try if $try < @heap && $heap [$try] < $heap [$min]
    }
    return if $min == $idx;
        
    @heap [$idx, $min] = @heap [$min, $idx];
    heapify $min;
}
 
sub extract_min {
    return unless @heap;
    my $min = $heap [0];
    my $tmp = pop @heap;
    if (@heap) {
        $heap [0] = $tmp;
        heapify 0;
    }
    return $min;
}
     
#
# First argument the number of smallest elements to be returned.
# Then the list to find the elements in.
#
sub smallest {
    my $k = shift;
    @heap = @_;
    for (my $i = int (@heap / 2); $i --;) {
        heapify $i;
    }
    my @result;
    push @result => extract_min while @heap && $k --;
    @result;
}

__END__
[download]

The running time of this is O (N + k log N), where N is the size of the set, and k the number of elements to be returned.

Abigail

Doesn't this require the whole list to be in memory? And doesn't that create a problem with the "from a very large dataset"?

The original question didn't specify how the data would be available, so I'm just going to assume it fits in memory. Note that a heapsort only requires a constant amount of memory additional to the data to be sorted.

If the data doesn't fit in memory, then that's a different problem. One can always tie the used array to whatever solution will keep the data to be worked on out of memory.

Abigail