Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Re^5: Heap sorting in perl

by Anonymous Monk
on Apr 05, 2003 at 17:02 UTC ( #248317=note: print w/replies, xml ) Need Help??


in reply to Re^5: Heap sorting in perl
in thread Heap sorting in perl

I was proposing to solve the problem originally stated. I thought that my description of how to solve it using a heap was fairly clear on that point by telling you when to start removing elements while still adding them.

I agree that until N is large (causing, eg, memory problems) or the comparison function is expensive, using sort will be faster. The heap solution outlined is helpful only for large N. For an expensive comparison function, it is helpful once you start pulling off elements to keep track of the largest that you have in your set. Anything which is larger than or equal to that one should not be added. This reduces the number of comparisons significantly.

As for the sort utility, I had thought that it had an option to only return the largest N elements. But looking at it more carefully I don't see it. It must have been somewhere else that I saw that. My bad. :-(

Replies are listed 'Best First'.
Re^7: Heap sorting in perl
by adrianh (Chancellor) on Apr 05, 2003 at 20:12 UTC
    I was proposing to solve the problem originally stated. I thought that my description of how to solve it using a heap was fairly clear on that point by telling you when to start removing elements while still adding them.

    I know. Just misinterpreted it. Sorry. One of my many moments of stupidity ;-)

    I agree that until N is large (causing, eg, memory problems) or the comparison function is expensive, using sort will be faster. The heap solution outlined is helpful only for large N.

    A good XS heap implementation would still win over sort with small N. It's just a C vs Perl issue speedwise.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://248317]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (2)
As of 2018-08-17 07:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Asked to put a square peg in a round hole, I would:









    Results (174 votes). Check out past polls.

    Notices?