Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
The quick breakdown of the Schwartzian Transform is this:

A typical sort operation in perl takes on the order of N * log N operations; each operation requires comparing two values of an array to do this. In perl, the values are not known beforehand and can be instead calculated on the fly. The calculation step will be performed twice for every one of those (roughly) N*log N operations, so if you have a long calculation, you're going to have a really slow sort.

What the Schwartzian Transform does is precalculates all of those values that you want sorted, and creates an array of arrays, one element being the initial position in the array that is to be sorted, the other being the calculated value of that element. The intermediate sort sorts on the precalculated values (which is fast), which also changes those index positions around, and then the final step maps the original array into a new one, using the adjusted index positions. You will now only calculate the value of each element in the array N times (exactly), as opposed to ~2*N*log N times. This can be a huge speed up.

If this is still confusing, here's a good real world example: say you have your stack of monthly bills, which you keep in their original envelopes so they don't get lost. You want to sort the bills in either date or amount order. One way is to open the envelope, pull out the bill, note the value you want, put the bill back in the envelope, and work on sorting in this fashion. If you had more than 10 bills, this would become tiresome. Alternatively, for each bill, you can write the due date and amount due on the outside of the envelope (thus requiring you to look at each bill only once), and then you only need to look at the outside of the envelope to sort the bills. The latter will be much faster with a large pile of bills.


Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

In reply to Re: Re: Re: Re: Re: Is too little too much? Coding under the microscope... by Masem
in thread Is too little too much? Coding under the microscope... by snafu

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 rifling through the Monastery: (5)
    As of 2014-12-20 20:33 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (98 votes), past polls