It's interesting that you're using min() to find the "max of N numbers". Pedantics aside, it's worthy of mention that the "quick way" still has to internally iterate over every element in the list you hand it, keeping track of the max. There's no way to determine the max in a list in less than O(n) time unless the list is already sorted in some fashion. And sorting a list just to grab the max one time is less efficient still. So assuming a list of arbitrary order, ascertaining the max is going to cost you O(n). The max() routine built into List::Util, at least, does this in C, so it's pretty overhead efficient, but the basic algorithm is still essentially a linear scheme with lots of internal comparisons.

The fact is that the best approach really is going to be determined by what it is you're trying to accomplish. A quick check for the max in a short list, infrequently, is best handled by List::Util max(). But more frequent searches of longer lists might benefit from a scheme to maintain order in the list in the first place. If I remember correctly, with a heap, initial heap creation consumes O(n log n) time, whereas simple linear list creation consumes O(n) time. Additional insertion consumes O(log n) time, again worse than the O(1) time required to insert an additional number in a linear list. But the benefit comes when you need to find the top element in the heap (which can be max or min depending on how you construct it to begin with). Grabbing the top element off a heap consumes O(1) time, as does simply peeking at the top element. So in some cases a heap might be preferable to a linear list, particularly if you don't care about order except to find the biggest or smallest element easily at all times, frequently, for large dynamically changing lists. On the other hand, for simple cases, ignore all this heap talk and just use List::Util max() ...or min().


Dave

In reply to Re^2: max of N numbers? by davido
in thread max of N numbers? by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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! —
  • 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:
    & &amp;
    < &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.