Sort two dimensional array with multiple keys

Discussion in 'Perl Misc' started by Milkweed, Oct 29, 2003.

  1. Milkweed

    Milkweed Guest

    I am trying sort an multi-dimensional array with three elements in
    each "row".

    Here's a look at a small section of input data:

    207.28.198.86 10.36.1.121 0310291642
    207.28.198.86 10.36.1.121 0310291753
    207.28.201.113 10.77.2.241 0310291642
    207.28.200.113 10.75.2.87 0310291642
    207.28.199.86 10.76.1.80 0310291642
    207.28.198.104 10.1.3.153 0310291642
    207.28.198.86 10.36.1.121 0310291324
    207.28.199.104 10.2.2.77 0310291642
    207.28.195.33 10.2.4.111 0310291642

    These are timestamped NAT translations from a firewall.
    What I want to do is sort this data by element 0 (global IP) as the
    primary key and element 2 (timestamp) as the secondary key so I can
    keep a historical record of NAT translations for a given global IP.

    I can't seem to get the sort to work. Here is a copy of what I have
    tried so far:

    #!/usr/bin/perl
    use strict;
    use warnings;
    use Net::Telnet::Cisco;
    use Data::Sorting qw( :basics :arrays );

    ....

    foreach (@xlate) { # @xlate is populated by a SNMP call to the
    firewall
    next unless /^Global/;
    my ($global, $local) = (split /\s/)[1,3];
    push @entries, [$global,$local,$timestamp];
    # each row of @entries now looks like the sample data above
    }

    #Sort entries by IP (primary key) and date (secondary key) and print
    output
    my @ordered = sorted_array( @entries,
    { engine=> 'packed', sortkey=>$_[0][0] },
    sortkey=>$_[0][2] );
    #my $i = 0;
    #keys my %h = @history;
    #@h{ sort map pack('C4 A x N' => $->[0] =~
    /(\d+)\.(\d+)\.(\d+)\.(\d+)/,
    # $_->[2], $i++) => @history } = @history;
    #my @ordered = @h{ sort keys %h };
    open NEW, ">xlate-ordered"
    or die "Could not open xlate-ordered for writing: $!\n";
    for my $row (@ordered) {
    print NEW "@$row\n";
    }

    As you can see I have tried using the "indexed sort" method from "A
    Fresh Look at Efficient Perl Sorting" as well as the Data::Sorting
    module with no success. Help with either option would be much
    appreciated!

    Thanks,
    Chris
    Milkweed, Oct 29, 2003
    #1
    1. Advertising

  2. Milkweed

    Ben Morrow Guest

    (Milkweed) wrote:
    > I am trying sort an multi-dimensional array with three elements in
    > each "row".
    >
    > Here's a look at a small section of input data:
    >
    > 207.28.198.86 10.36.1.121 0310291642
    > 207.28.198.86 10.36.1.121 0310291753
    > 207.28.201.113 10.77.2.241 0310291642
    > 207.28.200.113 10.75.2.87 0310291642
    > 207.28.199.86 10.76.1.80 0310291642
    > 207.28.198.104 10.1.3.153 0310291642
    > 207.28.198.86 10.36.1.121 0310291324
    > 207.28.199.104 10.2.2.77 0310291642
    > 207.28.195.33 10.2.4.111 0310291642
    >
    > These are timestamped NAT translations from a firewall.
    > What I want to do is sort this data by element 0 (global IP) as the
    > primary key and element 2 (timestamp) as the secondary key so I can
    > keep a historical record of NAT translations for a given global IP.
    >
    > I can't seem to get the sort to work. Here is a copy of what I have
    > tried so far:
    >
    > #!/usr/bin/perl
    > use strict;
    > use warnings;
    > use Net::Telnet::Cisco;
    > use Data::Sorting qw( :basics :arrays );
    >
    > ...
    >
    > foreach (@xlate) { # @xlate is populated by a SNMP call to the
    > firewall
    > next unless /^Global/;
    > my ($global, $local) = (split /\s/)[1,3];
    > push @entries, [$global,$local,$timestamp];
    > # each row of @entries now looks like the sample data above
    > }


    Try this (the technique is known as the Schwartzian Transform after
    Randal Schwartz):

    my @sorted = map { $_->[0] }
    sort { $b->[1] cmp $a->[1] }
    map { [ $_, $_->[0].$_->[2] ] }
    @entries;

    This will sort in ASCIIbetical order, first of global IP and then of
    timestamp. If you want the IPs in a better order you could use
    map { [ $_, inet_aton($_->[0]).$_->[2] ] }
    for the first map instead (after using Socket, obviously).

    I found out about this from http://perl.plover.com/: a very useful
    resource.

    Ben

    --
    "The Earth is degenerating these days. Bribery and corruption abound.
    Children no longer mind their parents, every man wants to write a book,
    and it is evident that the end of the world is fast approaching."
    -Assyrian stone tablet, c.2800 BC
    Ben Morrow, Oct 29, 2003
    #2
    1. Advertising

  3. Milkweed

    Anno Siegel Guest

    Milkweed <> wrote in comp.lang.perl.misc:
    > I am trying sort an multi-dimensional array with three elements in
    > each "row".
    >
    > Here's a look at a small section of input data:
    >
    > 207.28.198.86 10.36.1.121 0310291642
    > 207.28.198.86 10.36.1.121 0310291753
    > 207.28.201.113 10.77.2.241 0310291642
    > 207.28.200.113 10.75.2.87 0310291642
    > 207.28.199.86 10.76.1.80 0310291642
    > 207.28.198.104 10.1.3.153 0310291642
    > 207.28.198.86 10.36.1.121 0310291324
    > 207.28.199.104 10.2.2.77 0310291642
    > 207.28.195.33 10.2.4.111 0310291642
    >
    > These are timestamped NAT translations from a firewall.
    > What I want to do is sort this data by element 0 (global IP) as the
    > primary key and element 2 (timestamp) as the secondary key so I can
    > keep a historical record of NAT translations for a given global IP.
    >
    > I can't seem to get the sort to work. Here is a copy of what I have
    > tried so far:
    >
    > #!/usr/bin/perl
    > use strict;
    > use warnings;
    > use Net::Telnet::Cisco;
    > use Data::Sorting qw( :basics :arrays );


    I'm not acquainted with that module, but your sort problem is so
    straight-forward, I'd first try a direct solution.

    >
    > ...
    >
    > foreach (@xlate) { # @xlate is populated by a SNMP call to the
    > firewall
    > next unless /^Global/;
    > my ($global, $local) = (split /\s/)[1,3];
    > push @entries, [$global,$local,$timestamp];
    > # each row of @entries now looks like the sample data above


    Unlikely. The variable $timestamp isn't assigned a value.

    > }
    >
    > #Sort entries by IP (primary key) and date (secondary key) and print
    > output
    > my @ordered = sorted_array( @entries,
    > { engine=> 'packed', sortkey=>$_[0][0] },
    > sortkey=>$_[0][2] );
    > #my $i = 0;
    > #keys my %h = @history;
    > #@h{ sort map pack('C4 A x N' => $->[0] =~
    > /(\d+)\.(\d+)\.(\d+)\.(\d+)/,
    > # $_->[2], $i++) => @history } = @history;
    > #my @ordered = @h{ sort keys %h };
    > open NEW, ">xlate-ordered"
    > or die "Could not open xlate-ordered for writing: $!\n";
    > for my $row (@ordered) {
    > print NEW "@$row\n";
    > }
    >
    > As you can see I have tried using the "indexed sort" method from "A
    > Fresh Look at Efficient Perl Sorting" as well as the Data::Sorting
    > module with no success. Help with either option would be much
    > appreciated!


    As noted, you don't *need* any special methods for this sort. You
    may be able to speed things up a bit, but the first step should be
    to get it right.

    Assume your data is given like this (what it should be, but isn't, after
    the loop over @xlate):

    my @entries = (
    [ qw( 207.28.198.86 10.36.1.121 0310291642)],
    [ qw( 207.28.198.86 10.36.1.121 0310291753)],
    [ qw( 207.28.201.113 10.77.2.241 0310291642)],
    [ qw( 207.28.200.113 10.75.2.87 0310291642)],
    [ qw( 207.28.199.86 10.76.1.80 0310291642)],
    [ qw( 207.28.198.104 10.1.3.153 0310291642)],
    [ qw( 207.28.198.86 10.36.1.121 0310291324)],
    [ qw( 207.28.199.104 10.2.2.77 0310291642)],
    [ qw( 207.28.195.33 10.2.4.111 0310291642)],
    );

    For sorting, compare any two IPs as strings. If they are equal,
    compare the timestamps as numbers. The result is your sorted list:

    my @sorted = sort
    { $a->[ 0] cmp $b->[ 0] or $a->[ 2] <=> $b->[ 2] }
    @entries;

    print "@$_\n" for @sorted;

    Anno
    Anno Siegel, Oct 30, 2003
    #3
  4. Milkweed

    Milkweed Guest

    > Unlikely. The variable $timestamp isn't assigned a value.

    I forgot to mention the $timestamp variable is assigned using the
    localtime function further up in the code. Sorry for not explaining
    this in my previous post.


    > Assume your data is given like this (what it should be, but isn't, after
    > the loop over @xlate):


    This is what is looks like.

    > my @entries = (
    > [ qw( 207.28.198.86 10.36.1.121 0310291642)],
    > [ qw( 207.28.198.86 10.36.1.121 0310291753)],
    > [ qw( 207.28.201.113 10.77.2.241 0310291642)],
    > [ qw( 207.28.200.113 10.75.2.87 0310291642)],
    > [ qw( 207.28.199.86 10.76.1.80 0310291642)],
    > [ qw( 207.28.198.104 10.1.3.153 0310291642)],
    > [ qw( 207.28.198.86 10.36.1.121 0310291324)],
    > [ qw( 207.28.199.104 10.2.2.77 0310291642)],
    > [ qw( 207.28.195.33 10.2.4.111 0310291642)],
    > );
    >
    > For sorting, compare any two IPs as strings. If they are equal,
    > compare the timestamps as numbers. The result is your sorted list:
    >
    > my @sorted = sort
    > { $a->[ 0] cmp $b->[ 0] or $a->[ 2] <=> $b->[ 2] }
    > @entries;
    >
    > print "@$_\n" for @sorted;
    >
    > Anno


    The above code works. Thanks! I'm worried about how fast the two
    subsorts will perform. I could potentially have hundreds of thousands
    of entries, which is why I was trying to do something with an indexed
    search in the first place. Thanks again for your help.

    Chris
    Milkweed, Oct 30, 2003
    #4
  5. Milkweed

    Milkweed Guest

    > Try this (the technique is known as the Schwartzian Transform after
    > Randal Schwartz):
    >
    > my @sorted = map { $_->[0] }
    > sort { $b->[1] cmp $a->[1] }
    > map { [ $_, $_->[0].$_->[2] ] }
    > @entries;
    >
    > This will sort in ASCIIbetical order, first of global IP and then of
    > timestamp. If you want the IPs in a better order you could use
    > map { [ $_, inet_aton($_->[0]).$_->[2] ] }
    > for the first map instead (after using Socket, obviously).


    When I try this:
    my @sorted =
    map { $_->[0] }
    sort { $b->[1] cmp $a->[1] }
    map { $_, inet_aton($_->[0]).$_->[2] }
    @entries;

    I get the following error:

    Can't use string ("ÏÄÈ0310301117") as an ARRAY ref while "strict refs"
    in use at ./NAT.pl line 73.

    Any idea how to get past this?

    Thanks,
    Chris
    Milkweed, Oct 30, 2003
    #5
  6. Milkweed

    Greg Bacon Guest

    In article <>,
    Milkweed <> wrote:

    : When I try this:
    : my @sorted =
    : map { $_->[0] }
    : sort { $b->[1] cmp $a->[1] }
    : map { $_, inet_aton($_->[0]).$_->[2] }
    : @entries;
    :
    : I get the following error:
    :
    : Can't use string ("ÏÄÈ0310301117") as an ARRAY ref while "strict refs"
    : in use at ./NAT.pl line 73.

    Your first map should produce a list of array references:

    ...
    map { [ $_, inet_aton($_->[0]) . $_->[2] ] }
    @entries;

    Greg
    --
    I am sorry, but I just cannot accept that as a proper definition of
    patriotism. Blind allegiance is the mother of tyranny, not patriotism.
    -- R. Lee Wrights
    Greg Bacon, Oct 30, 2003
    #6
  7. Milkweed

    Milkweed Guest

    > Try this (the technique is known as the Schwartzian Transform after
    > Randal Schwartz):
    >
    > my @sorted = map { $_->[0] }
    > sort { $b->[1] cmp $a->[1] }
    > map { [ $_, $_->[0].$_->[2] ] }
    > @entries;
    >
    > This will sort in ASCIIbetical order, first of global IP and then of
    > timestamp. If you want the IPs in a better order you could use
    > map { [ $_, inet_aton($_->[0]).$_->[2] ] }
    > for the first map instead (after using Socket, obviously).
    >
    > I found out about this from http://perl.plover.com/: a very useful
    > resource.
    >
    > Ben


    Forget my last reply. I'm a dork. I forgot to put the outside [ ] in
    the first map statement. Once I put those in it worked perfectly.
    Thanks for your help!

    Chris
    Milkweed, Oct 30, 2003
    #7
    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. Alf P. Steinbach
    Replies:
    0
    Views:
    435
    Alf P. Steinbach
    Aug 18, 2003
  2. John Harrison
    Replies:
    4
    Views:
    6,923
    Default User
    Aug 19, 2003
  3. Icosahedron
    Replies:
    8
    Views:
    652
    Vivek
    Aug 21, 2003
  4. Venkat
    Replies:
    4
    Views:
    972
    Venkat
    Dec 5, 2003
  5. Robert Somerville

    how to sort two dimensional array ??

    Robert Somerville, Jan 19, 2010, in forum: Python
    Replies:
    1
    Views:
    296
    bignum
    Jan 20, 2010
Loading...

Share This Page