Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Comment on

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

All items matching ^index\. will fail to sort on any component of the token that comes after "index.". That means that there would be no way to really predict how index.b, index.a, index.c would be sorted, except that the merge sort is a "stable" sort.

Also, cmp is a relatively flawed operator (it's not just Perl; any code sorting using a comparison of ASCII values is equally flawed). You might want to invoke Unicode::Collate's cmp method instead. The cmp operator is predictable, but only sorts "ascii-betically", which nowadays is only useful in accomplishing a predictable order.

Finally, the amount of work you're doing inside of a sort routine is substantial. If you have 100 items you're sorting, your sort function will be called somewhere around 100 * log2(100) times, or approximately 660 times. If you're sorting 10000 items, it will be called approximately 133000 times. Each regular expression inside the subroutine has some non-zero level of computational complexity. split has linear complexity...and so on. All this begins to add up fast as you multiply it by how many times the subroutine is invoked in the course of sorting your list. You might wish, instead, to pre-compute and cache, using something like the Schwartzian Transform, or the Guttman-Rosler Transform, where you precompute the sort keys just one time each, and then sort based on those keys. To some degree it would require rewriting your routine. But it would be an excellent learning exercise.

Of course you should only worry about the computational complexity if you intend this solution to be used on lists large enough for it to matter. A few hundred or even a few thousand items probably isn't worth the effort. But if you find yourself initiating a sort and then having time to walk away and pop a bag of popcorn in the microwave, it's time to start exploring the transforms. Or just enjoy the break. ;)


Dave


In reply to Re: RFC: I rewrote a custom sort function, but not sure if it is the best way. by davido
in thread RFC: I rewrote a custom sort function, but not sure if it is the best way. by Lady_Aleena

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: (3)
    As of 2014-09-20 17:25 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (160 votes), past polls