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

Re: RFC: I rewrote a custom sort function, but not sure if it is the best way.

by davido (Archbishop)
on Mar 03, 2013 at 01:24 UTC ( #1021475=note: print w/ replies, xml ) Need Help??


in reply to RFC: I rewrote a custom sort function, but not sure if it is the best way.

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


Comment on Re: RFC: I rewrote a custom sort function, but not sure if it is the best way.
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1021475]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (15)
As of 2014-07-30 12:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (231 votes), past polls