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

  • Comment on Re^2: getting the highest value in a simpler way

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
    Am I correct in saying that insertion is O(log n) for each insertion? Therefore, if you have 500 insertions, it would be something like (sum)O(log n) (for n=1->500)??

    That is no longer O(log n), but something higher than that, I believe. I don't know what would dominate, though, the O(log n), or the (1->500) sum, but I suspect the latter.

      Insertion of each element individually is O(log n), for a plain heap. A Fibonacci heap does inserts in O(1), and get/delete-min's in O(log n) amortized time, but at the cost of being pretty tricky to implement correctly, though there are modules to help with that.

      But to your point, yes, each insert is O(log n).


      Dave

        We chatted.. if each insert costs log n, and you are doing it n times.. you get n log n, no? If you heapify an existing array, you get n... which isn't much better anyway. At least TCRC likes to claim that max and min ops are done in n time, which seems right, no?

        ----
        Then B.I. said, "Hov' remind yourself nobody built like you, you designed yourself"