As author of Heap::Simple I'd like to add the following observations:

• Make sure Heap::Simple::XS is used if you care about speed for this kind of operation.
• Use the (default) scalar element type if that is good enough. It's the fastest of the available element types.
• Use the max_count option if you only want an already known last m elements. This will save a lot of compares. In this case it also saves the extract loop.

With these three getting the median of a heap of 1e6 integers is close in speed. Sort is still faster though.

You can also add the dirty option. Heap::Simple::XS will then use direct numeric compares instead of calling perl's >. This breaks overload and ties though. That way the Heap::Simple solution is about twice as fast as sort. The break-even is somewhere in the ten thousands of elements.

The resulting code looks something like this:

use List::Util qw(shuffle);
use POSIX qw(ceil);
use Heap::Simple::XS;

my @list = shuffle(0..1e6); 
my $h = Heap::Simple::XS->new(max_count => ceil(@list/2),
                              dirty => 1);
$h->insert(@list);
print $h->extract_top;
[download]

This doesn't change the fact that for even quite big lists sort is just faster for this kind of problem. Heaps are mainly for when you need to know the smallest element at many points in time while the set of elements keeps changing. Or indeed for some cases where compare is very expensive, but even then there are better ways to do it with less compares if you just want the median.

PS: Heap::Simple already uses special code to make an insert of many elements at once faster than repeatedly inserting one element. You seem to hint at an even faster algorithm but I don't see how to use Tarjan's algorithm for that. Can you give me a reference ?

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.