Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

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. ;)


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1021475]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2018-06-23 06:58 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (125 votes). Check out past polls.