in reply to Re: getting the highest value in a simpler way
in thread getting the highest value in a simpler way
The OP's node carries the title, "getting the highest value in a simpler way", but his followups seem to reveal that the primary concern is time efficiency, not necessarily simplicity. So it's a little uncertain what exactly is wanted.
But there is something else that hasn't been suggested, for keeping track of the max. That is to use a new datastructure altogether.
Your completely correct comment is "don't think of sorting beforehand .... as that is ... O(n log n) time." I agree, that as you have said, unless you want a sorted list for other reasons, don't sort just to find the max. But what if you always only want the max, or always only want the min, and don't really care about anything else? This is a job for a heap. Heaps are not all that frequently used in Perl because the built-in datatypes so conveniently handle all the more common needs, but heaps can still be helpful. The basic principle is that as you add items to the heap, the minimum item is always kept at the top of the heap where it can be retrieved in O(log n) time. Insertion is O(log n) time, which is faster than the O(n) time needed to do a linear search for a min. Though heaps are usually discussed in terms of placing the min at the top, it's easy enough to invert them and have the max at the top, so long as the decision is made up front, before the heap is generated.
There is a great module on CPAN called Heap::Simple that makes it really easy to implement a heap. Again, if all you're doing with your data is inserting values, or extracting the max, or all you're doing with your data is inserting values, or extracting the min, repeatedly, a heap is a great solution.
Dave
|
|---|
| Replies are listed 'Best First'. | |
|---|---|
|
Re^3: getting the highest value in a simpler way
by riffraff (Pilgrim) on Nov 10, 2004 at 19:07 UTC | |
by davido (Cardinal) on Nov 10, 2004 at 19:28 UTC | |
by exussum0 (Vicar) on Nov 10, 2004 at 20:35 UTC |