Sort Keys in hash table?

Discussion in 'Perl Misc' started by Davy, Aug 16, 2006.

  1. Davy

    Davy Guest

    Hi all,

    I want to sort key in hash table.
    The hash table key format is some integer split with ";" like:
    "5;12;17;28"
    And I want to sort the key from the first integer to the last
    integer(i.e. the first integer has highest priority, and the second,
    third,... until the last):

    example:
    5;12;17;28
    5;13;15;2
    5;13;18;1

    Thanks!
    Davy
     
    Davy, Aug 16, 2006
    #1
    1. Advertising

  2. Davy

    Davy Guest

    A. Sinan Unur wrote:
    > "Davy" <> wrote in news:1155768562.219578.123460
    > @i3g2000cwc.googlegroups.com:
    >
    > > I want to sort key in hash table.
    > > The hash table key format is some integer split with ";" like:
    > > "5;12;17;28"
    > > And I want to sort the key from the first integer to the last
    > > integer(i.e. the first integer has highest priority, and the second,
    > > third,... until the last):
    > >
    > > example:
    > > 5;12;17;28
    > > 5;13;15;2
    > > 5;13;18;1

    >
    > perldoc -f sort
    >
    > perldoc -q sort
    >
    > perldoc Sort::Maker
    > http://search.cpan.org/~uri/Sort-Maker-0.05/Sort/Maker.pm

    [snip]

    Hi Sinan,

    Thank you for your help! I will try to use the Maker.pm.
    Because I want to learn Perl, I want to write routines. Anyone can
    recommend some references on this subject.

    Thanks!
    Davy

    >
    > Show us what you have tried after reading the above, tell us what is not
    > working, and we'll help.
    >
    > Sinan
    > --
    > A. Sinan Unur <>
    > (remove .invalid and reverse each component for email address)
    >
    > comp.lang.perl.misc guidelines on the WWW:
    > http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    Davy, Aug 17, 2006
    #2
    1. Advertising

  3. Davy

    Simon Taylor Guest

    Simon Taylor, Aug 17, 2006
    #3
  4. Davy

    Davy Guest

    Davy 写é“:

    > A. Sinan Unur wrote:
    > > "Davy" <> wrote in news:1155768562.219578.123460
    > > @i3g2000cwc.googlegroups.com:
    > >
    > > > I want to sort key in hash table.
    > > > The hash table key format is some integer split with ";" like:
    > > > "5;12;17;28"
    > > > And I want to sort the key from the first integer to the last
    > > > integer(i.e. the first integer has highest priority, and the second,
    > > > third,... until the last):
    > > >
    > > > example:
    > > > 5;12;17;28
    > > > 5;13;15;2
    > > > 5;13;18;1

    > >
    > > perldoc -f sort
    > >
    > > perldoc -q sort
    > >

    [snip]
    Hi,

    I have write a program based on my idea. And the program run well.

    #---code begin---
    use strict;
    use warnings;

    my $separator = ";";

    my @data_list = (
    "5;3;7",
    "1;5;11",
    "11;4;8",
    "1;3;9"
    );

    my @data_sort = sort compare (@data_list);
    print_1d_list(\@data_sort);

    # input string like "5;3;14"
    # compare the string from the first data to the last data
    # i.e. 5->3->14
    sub compare {
    my @a_list = split /$separator/, $a;
    my @b_list = split /$separator/, $b;
    my $a_list_length = (@a_list); # prevent while from dead-loop

    my $compare_result = 0; #equal
    my $index = 0;
    while ($compare_result == 0) {
    my $compare_result = ($a_list[$index] <=> $b_list[$index]);
    if ($compare_result != 0) {
    return $compare_result;
    }
    else {
    $index ++;
    }

    # prevent while from dead-loop
    if ($index > $a_list_length) {
    die("sort compare index overflow");
    }

    # Debug usage
    # print "index = $index\n";
    # print "compare_result = $compare_result\n";
    }
    }

    sub print_1d_list {
    my $list_ref = $_[0];
    my @list = @{$list_ref};
    foreach my $list_element (@list) {
    print "$list_element\n";
    }
    }

    #--- code end

    Thanks!

    Davy

    > > perldoc Sort::Maker
    > > http://search.cpan.org/~uri/Sort-Maker-0.05/Sort/Maker.pm

    > [snip]
    >
    > Hi Sinan,
    >
    > Thank you for your help! I will try to use the Maker.pm.
    > Because I want to learn Perl, I want to write routines. Anyone can
    > recommend some references on this subject.
    >
    > Thanks!
    > Davy
    >
    > >
    > > Show us what you have tried after reading the above, tell us what is not
    > > working, and we'll help.
    > >
    > > Sinan
    > > --
    > > A. Sinan Unur <>
    > > (remove .invalid and reverse each component for email address)
    > >
    > > comp.lang.perl.misc guidelines on the WWW:
    > > http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    Davy, Aug 19, 2006
    #4
  5. Davy

    Uri Guttman Guest

    >>>>> "D" == Davy <> writes:

    D> I have write a program based on my idea. And the program run well.

    D> my @data_list = (
    D> "5;3;7",
    D> "1;5;11",
    D> "11;4;8",
    D> "1;3;9"
    D> );

    D> my @data_sort = sort compare (@data_list);

    D> sub compare {
    D> my @a_list = split /$separator/, $a;
    D> my @b_list = split /$separator/, $b;
    D> my $a_list_length = (@a_list); # prevent while from dead-loop

    D> my $compare_result = 0; #equal
    D> my $index = 0;
    D> while ($compare_result == 0) {
    D> my $compare_result = ($a_list[$index] <=> $b_list[$index]);
    D> if ($compare_result != 0) {
    D> return $compare_result;
    D> }
    D> else {
    D> $index ++;
    D> }

    D> # prevent while from dead-loop
    D> if ($index > $a_list_length) {
    D> die("sort compare index overflow");
    D> }

    D> # Debug usage
    D> # print "index = $index\n";
    D> # print "compare_result = $compare_result\n";
    D> }
    D> }

    that may work but if your input list is large it will be deadly
    slow. you call that major sub for each time a pair of values is
    compared. if you care about speed as your dataset grows you should use a
    module like sort::maker or some other way to factor out all that
    redundant work. you see you do that for each $a and $b and in a typical
    sort input values will be compared more than one time so you are redoing
    work over and over. but if you only have 5 values, who cares?

    uri

    --
    Uri Guttman ------ -------- http://www.stemsystems.com
    --Perl Consulting, Stem Development, Systems Architecture, Design and Coding-
    Search or Offer Perl Jobs ---------------------------- http://jobs.perl.org
     
    Uri Guttman, Aug 19, 2006
    #5
  6. Davy

    Davy Guest

    A. Sinan Unur wrote:
    > "Davy" <> wrote in
    > news::
    >
    > >
    > > Davy 写é“:
    > >
    > >> A. Sinan Unur wrote:
    > >> > "Davy" <> wrote in news:1155768562.219578.123460
    > >> > @i3g2000cwc.googlegroups.com:
    > >> >
    > >> > > I want to sort key in hash table.
    > >> > > The hash table key format is some integer split with ";" like:
    > >> > > "5;12;17;28"
    > >> > > And I want to sort the key from the first integer to the last
    > >> > > integer(i.e. the first integer has highest priority, and the
    > >> > > second, third,... until the last):
    > >> > >
    > >> > > example:
    > >> > > 5;12;17;28
    > >> > > 5;13;15;2
    > >> > > 5;13;18;1
    > >> >
    > >> > perldoc -f sort
    > >> >
    > >> > perldoc -q sort

    >
    > ...
    >
    > > I have write a program based on my idea. And the program run well.
    > >
    > > #---code begin---
    > > use strict;
    > > use warnings;
    > >
    > > my $separator = ";";
    > >
    > > my @data_list = (
    > > "5;3;7",
    > > "1;5;11",
    > > "11;4;8",
    > > "1;3;9"
    > > );
    > >
    > > my @data_sort = sort compare (@data_list);
    > > print_1d_list(\@data_sort);

    >
    > This sub is uncessary.
    >
    > {
    > local $, = "\n"; # see perldoc perlvar
    > print @data_sort, "\n";
    > }
    >
    > will print an array in the same format.
    >
    > > sub compare {
    > > my @a_list = split /$separator/, $a;
    > > my @b_list = split /$separator/, $b;

    >
    > You should be able to gain some efficiency by compiling the regex only
    > once.
    >
    > > my $a_list_length = (@a_list); # prevent while from dead-loop
    > >
    > > my $compare_result = 0; #equal
    > > my $index = 0;
    > > while ($compare_result == 0) {
    > > my $compare_result = ($a_list[$index] <=> $b_list[$index]);
    > > if ($compare_result != 0) {
    > > return $compare_result;
    > > }
    > > else {
    > > $index ++;
    > > }
    > >
    > > # prevent while from dead-loop
    > > if ($index > $a_list_length) {
    > > die("sort compare index overflow");
    > > }

    >
    > A lot of this is somewhat cumbersome. IMHO, the fact that it does not
    > handle lists of different lengths is a shortcoming.
    >
    > So, below I including an example which generates a comparison subroutine
    > parameterized by the separator you want to use. It handles lists of
    > different lengths as well. Given two lists of length m and n with m > n,
    > if the lists are identical in the first n elements, it declares the one
    > with m elements to be greater than the shorter one.
    >
    > #!/usr/bin/perl
    >
    > use strict;
    > use warnings;
    >
    > my $separator = ";";
    >
    > my @data_list = qw(
    > 5;3;7
    > 5;3;7;9
    > 5;3;7;9;
    > 5;3;7;9;10
    > 1;5;11
    > 11;4;8
    > 1;3;9
    > 1;3;9
    > 1;39;11
    > );
    >
    > my $compare = make_comparator(';');
    > my @data_sort = sort $compare (@data_list);
    > {
    > local $, = "\n";
    > print @data_sort;
    > }
    >
    > sub make_comparator {
    > my ($separator) = shift;
    >
    > my $rx = qr/$separator/;
    >
    > return sub {
    > my @a = split $rx, $a;
    > my @b = split $rx, $b;
    >
    > while ( @a or @b ) {
    > my $ai = shift @a;
    > my $bi = shift @b;
    >
    > return 1 if defined $ai and not defined $bi;
    > return -1 if not defined $ai and defined $bi;
    >
    > return $ai <=> $bi unless $ai == $bi;
    > }
    > return 0; # same number of elements, all equal
    > };
    > }

    Hi Sinan,

    Thanks! I have used your upper code, and it run faster than my code!

    For I am not familar with map usage, can you recommend some reference
    to understand your code below.

    Best regards,
    Davy

    > __END__
    >
    > Note that the comparison can be expensive. To reduce the number of
    > comparisons, you can use "The Schwartzian Transform" (see
    > <URL: http://www.stonehenge.com/merlyn/UnixReview/col06.html>).
    >
    > #!/usr/bin/perl
    >
    > use strict;
    > use warnings;
    >
    > my $separator = ";";
    >
    > my @data_list = qw(
    > 5;3;7
    > 5;3;7;9
    > 5;3;7;9;
    > 5;3;7;9;10
    > 1;5;11
    > 11;4;8
    > 1;3;9
    > 1;3;9
    > 1;39;11
    > );
    >
    > my @data_sort = map { $_->[1] }
    > sort vector_compare
    > map { [ [ split /;/ ], $_ ] }
    > @data_list;
    > {
    > local $, = "\n";
    > print @data_sort;
    > }
    >
    > sub vector_compare {
    > my @a = @{ $a->[0] };
    > my @b = @{ $b->[0] };
    >
    > while ( @a or @b ) {
    > my $ai = shift @a;
    > my $bi = shift @b;
    >
    > return 1 if defined $ai and not defined $bi;
    > return -1 if not defined $ai and defined $bi;
    >
    > return $ai <=> $bi unless $ai == $bi;
    > }
    > return 0; # same number of elements, all equal
    > }
    >
    > __END__
    >
    > Let's take a look at that
    >
    > my @data_sort = map { $_->[1] }
    > sort vector_compare
    > map { [ [ split /;/ ], $_ ] }
    > @data_list;
    >
    > Here, for each element of @data_list
    >
    > map { [ [ split /;/ ], $_ ] } @data_list;
    >
    > creates a reference to an anonymous array with two elements. The first
    > element is a reference to another anonymous array containing the split
    > numbers. This is used by the comparison routine. The second element is
    > the original string from @data_list. This is used for reconstituting the
    > list after sorting is done.
    >
    > sort vector_compare
    >
    > sorts this list according to the vector_compare sub above
    >
    > map { $_->[1] }
    >
    > then reconstitutes the original array.
    >
    >
    > Sinan
    >
    > --
    > A. Sinan Unur <>
    > (remove .invalid and reverse each component for email address)
    >
    > comp.lang.perl.misc guidelines on the WWW:
    > http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    Davy, Aug 19, 2006
    #6
  7. Davy

    Davy Guest

    A. Sinan Unur wrote:
    > "Davy" <> wrote in news:1155768562.219578.123460
    > @i3g2000cwc.googlegroups.com:
    >
    > > I want to sort key in hash table.
    > > The hash table key format is some integer split with ";" like:
    > > "5;12;17;28"
    > > And I want to sort the key from the first integer to the last
    > > integer(i.e. the first integer has highest priority, and the second,
    > > third,... until the last):
    > >
    > > example:
    > > 5;12;17;28
    > > 5;13;15;2
    > > 5;13;18;1

    >
    > perldoc -f sort
    >
    > perldoc -q sort
    >
    > perldoc Sort::Maker
    > http://search.cpan.org/~uri/Sort-Maker-0.05/Sort/Maker.pm
    >

    [snip]
    Hi ,

    Is there any good tutorial talk about how to CPAN module document and
    use them?

    Thanks!
    Davy

    > Show us what you have tried after reading the above, tell us what is not
    > working, and we'll help.
    >
    > Sinan
    > --
    > A. Sinan Unur <>
    > (remove .invalid and reverse each component for email address)
    >
    > comp.lang.perl.misc guidelines on the WWW:
    > http://augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html
     
    Davy, Aug 20, 2006
    #7
  8. Davy

    Paul Lalli Guest

    Davy wrote:
    > A. Sinan Unur wrote:
    > > perldoc -f sort
    > >
    > > perldoc -q sort
    > >
    > > perldoc Sort::Maker
    > > http://search.cpan.org/~uri/Sort-Maker-0.05/Sort/Maker.pm
    > >

    > [snip]
    > Hi ,
    >
    > Is there any good tutorial talk about how to CPAN module document and
    > use them?


    I really don't know what you're asking for. Are you asking how to
    create modules and upload them to CPAN?

    perldoc perlmodlib

    Are you asking how to download and install modules from CPAN?

    perldoc perlmodlib

    Are you asking how to write documentation for modules?

    perldoc perlpod

    Are you asking for a listing of 'perldoc' documentation?

    perldoc perltoc

    Are you asking what modules are available on the CPAN?

    perldoc -q cpan
    (for links to relevant URLs)

    Hope this helps,
    Paul Lalli
     
    Paul Lalli, Aug 20, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tommo
    Replies:
    2
    Views:
    3,511
    Gunnar Hjalmarsson
    Dec 15, 2003
  2. rp
    Replies:
    1
    Views:
    562
    red floyd
    Nov 10, 2011
  3. Pål Bergström

    Sort hash with keys as integer

    Pål Bergström, Sep 25, 2010, in forum: Ruby
    Replies:
    3
    Views:
    161
    Robert Klemme
    Sep 26, 2010
  4. Malik Yousef

    Sort Hash o Hash accordint to two keys

    Malik Yousef, May 6, 2004, in forum: Perl Misc
    Replies:
    9
    Views:
    204
    Uri Guttman
    May 7, 2004
  5. Malik Yousef

    Sort Hash o Hash accordint to two keys

    Malik Yousef, May 6, 2004, in forum: Perl Misc
    Replies:
    0
    Views:
    114
    Malik Yousef
    May 6, 2004
Loading...

Share This Page