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

sorting a hash

by Ben Win Lue (Friar)
on Mar 26, 2005 at 09:03 UTC ( #442459=perlquestion: print w/replies, xml ) Need Help??
Ben Win Lue has asked for the wisdom of the Perl Monks concerning the following question:

O wise ones,
I have a hash pointers to records as values. I need to iterate the records in a specific order that can't be obtained by sorting the keys. My first idea was:
-get the values of the hash
-store them in a list
-sort the list
-foreach the records

Since the record-hash might become quite large, I would like to know if there is a way to sort the records in place or other ways to minimize copying-operations.

Replies are listed 'Best First'.
Re: sorting a hash
by jbrugger (Parson) on Mar 26, 2005 at 09:34 UTC
    Not sure about what your hash looks like, but sorting a hash is as easy as:
    by value:
    $yourHashName{$b} <=> $yourHashName{$a};

    or by the key of your hash:
    foreach $key (sort (keys(%yourHashName))) { print "\t\t$key \t $yourHashName{$key}\n"; }

    "We all agree on the necessity of compromise. We just can't agree on when it's necessary to compromise." - Larry Wall.
Re: sorting a hash
by tlm (Prior) on Mar 26, 2005 at 14:36 UTC

    You don't need to make a list of the records. Just sort the keys according to the corresponding record values, like this:

    my @sorted_keys = sort { extract( $hash{ $a } ) <=> extract( $hash{ $b } ) } keys %has +h; for my $key ( @sorted_keys ) { # whatever }
    where extract is some function defined by you and that you apply to record values to get whatever you want the sorting to reflect. If extract returns strings that you want sorted alphabetically instead of numerically, then use cmp instead of <=>. And if you just want the sorting for the records to be plain ol' alphabetical sorting, then make that
    my @sorted_keys = sort { $hash{ $a } cmp $hash{ $b } } keys %hash; for my $key ( @sorted_keys ) { # whatever }
    Or you can optimize things further by using the Schwartzian Transform:
    my @sorted_keys = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [ $_, extract( $hash{ $_ } ) ] } keys %hash;
    or any other sort optimization technique.

    The important thing is that you are sorting the keys, even if the criterion for this sort is based on the associated values.

    More generally, it is very common to want to sort a collection of items ($z, $y, $x, $w, ...) based on the values (f($z), f($y), f($x), f($w), ...) of some function f applied to those items. For example, if you want to sort strings without regard for their case, that function f could be uc (or equivalently lc). Then you just do

    my @sorted = sort { f($a) cmp f($b) } @unsorted;
    my @sorted = sort { f($a) <=> f($b) } @unsorted;
    The important point is that what ends up in the @sorted arrays is not the f($z), f($y), f($x)... but the original $z, $y, $x,... (except that now they are sorted).

    And the second important point is that "dereferencing a hash key" is in this case conceptually no different from applying some function to the keys. I.e. f for this case could be defined as

    sub f { my $key = shift; return $hash{ $key }; }
    Of course, a function f like the one above that does nothing to the hash value is usually not very useful, since we may as well just use $hash{ $key } directly.

    the lowliest monk

      You don't need to make a list of the records. Just sort the keys ...

      You cannot "just sort the keys", without making a list of them!

      Since the record-hash might become quite large ...

      There is not a

      way to sort the records in place or other ways to minimize copying- operations.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      Lingua non convalesco, consenesco et abolesco.
      Rule 1 has a caveat! -- Who broke the cabal?

        My interpretation of the OP's question was that the records were much larger than the keys, and making a separate sorted list of the records would require copying a lot of bytes. Sorting the keys still requires "making a list of them", i.e. copying, the number of bytes copied would be much smaller.

        Did I miss something?

        the lowliest monk

Re: sorting a hash
by sh1tn (Priest) on Mar 26, 2005 at 11:17 UTC
    You may want to see
    perldoc -q sort
    perldoc -f sort
    from the command line.

Re: sorting a hash
by gube (Parson) on Mar 26, 2005 at 12:08 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://442459]
Approved by Corion
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (2)
As of 2018-05-22 01:16 GMT
Find Nodes?
    Voting Booth?