Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

When you say that something is O(N) or O(N^2) or whatever, you are saying that as N changes then the resource in question (time or memory normally) changes with that relation to it. So if something is O(N) and N doubles, then the time taken doubles. What this ignores is that the time taken is actually c*N or k*1, and that for different algorithms the constants will be different.

So, the if/elsif/elsif/elsif/else chain actually takes c*N seconds, and the hash lookup and subroutine dispatch takes k*1 seconds. I'm not at all surprised that for small N then cN is smaller than k because it involves very few calculations so its constant term is a *lot* less than that for the hash lookup.

I shall now proceed to pull some random numbers out of my arse.

Calculating a hash takes of the order of a few hundreds of machine cycles (let's say a thousand). Finding the right place in the if/elsif/elsif/else chain will take more like a few tens of cycles. In fact, if the compiler optimises really well, checking and ignoring each condition will take just two machine cycles. Let's call it ten because this is perl, not C.

If we also assume that on average it has to check N/2 conditions then the hash would only win for N > 200. That's ignoring, of course, any extra overhead from setting up both cases in the first place.


In reply to Re: elsif chain vs. dispatch by DrHyde
in thread elsif chain vs. dispatch by sflitman

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!
  • 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, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (7)
    As of 2014-07-10 03:29 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (198 votes), past polls