in reply to getting the highest value in a simpler way

For finding the highest value of mutual, you aren't going to get much better than what you have now. You need to go through, element by element, either by using a perl module or by what you have done here. If you can keep track of mutual's calculated, you can save yourself a little time. i.e. 
for( a bunch of values )
{
  mutual = complexCalculation();
  max = mutual if( max < mutual or max = 0 );
}

[download]
If you don't have such a loop, don't worry too much. The module suggested or what you are doing is fast enough. After all, searching for max or min in an unsorted list takes O(n) time. Oh, and btw, dont' think of sorting before hand unless you want it sorted for other reasons, as that is in the realm of O(n lg n) time.

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

Replies are listed 'Best First'.
Re^2: getting the highest value in a simpler way
by davido (Cardinal) on Nov 10, 2004 at 18:17 UTC

    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

[reply]
      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.

[reply]

        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

[reply]

In Section Seekers of Perl Wisdom