Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^2: sorting a complex multidimensional hash

by revdiablo (Prior)
on Jul 22, 2004 at 06:12 UTC ( [id://376477]=note: print w/replies, xml ) Need Help??


in reply to Re: sorting a complex multidimensional hash
in thread sorting a complex multidimensional hash

I forgot all about the Schwartzian Transform. You'd probably be better off using it

I wouldn't jump to that conclusion without testing it first. The ST is a great optimization, but I have a feeling it is slightly overused. It's not very difficult to use, which is probably why it's used so often, but I rarely see anyone justify its use. If anything, a quick test or two would be in order before triumphantly declaring "You'd probably be better off using it."

Replies are listed 'Best First'.
Re^3: sorting a complex multidimensional hash
by hv (Prior) on Jul 22, 2004 at 10:43 UTC

    The Schwartzian Transform is useful primarily because of its scalability - when sorting, the number of calls to the comparator is somewhere between O(nlogn) and O(n2) [0], so if some of the effort can be offloaded to an O(n) comparison you would normally except it to be a win at some point as the array to be sorted grows.

    (Note though that this is not guaranteed, since the cost of the extra memory used by the ST does not grow linearly.)

    The GRT [1] has the added benefit that we end up using one of perl's built-in sort comparators (the simple $a cmp $b or $a <=> $b), which means that the entire sort is run directly in C code without resorting to the perl interpreter for each comparison.

    To my mind, there are only three reasons why you might not want to use one of these transforms on any sort in your program: if you are sorting a list of (small and) bounded size; if you are likely to be in a limited memory situation such that the transforms might cause you either to run out of memory or start swapping; or (and I think this is the most common case) if the added code complexity outweighs the likely speed advantages - never forget the high resource cost of code maintenance.

    Hugo

    [0] see An informal introduction to O(N) notation

    [1] see Resorting to Sorting for a tutorial on these and other sorting techniques

Re^3: sorting a complex multidimensional hash
by The Mad Hatter (Priest) on Jul 22, 2004 at 13:28 UTC
    That's why I included the "probably" in there; maybe I wasn't clear enough. I'm not usually one to jump on a bandwagon, and I'm aware that it's quite possible the ST wouldn't be better, but I decided to leave the benchmarks up to the OP (basically a lack of desire to do them myself).

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (5)
As of 2024-03-28 14:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found