Re^4: Sorting out troubles with advanced-ish sort

By the way, what about when you get an address like 10.10.10.14 as the source? That'll sort before 10.10.10.5, so perhaps you should convert the IPs into 4-byte sequences.

When packed, the strings will be shorter and we could use the default { $a cmp $b } compare function. That makes the packed version much faster, and it would require less memory. Note the ingenious use of 0 or 1 to in lieu of $src.

print map  { substr($_, 13) }
      sort
      map  { my ($src, $dst) = (split)[0, 2];
             $src = pack('C4n', split(/[.:]/, $src));
             $dst = pack('C4n', split(/[.:]/, $dst));
             $src lt $dst ? "$src${dst}0$_"
                          : "$dst${src}1$_"           }
      <DATA>;
[download]

Actually, adding $_ is redundant, since we can reconstruct it. The following would cut the memory usage in half:

print map  { my @f = unpack('C4nC4na', $_);
             my $src = "$f[0].$f[1].$f[2].$f[3]:$f[4]";
             my $dst = "$f[5].$f[6].$f[7].$f[8]:$f[9]";
             ($src, $dst) = ($dst, $src) if $f[10];
             "$src -> $dst\n"                          }
      sort
      map  { my ($src, $dst) = (split)[0, 2];
             $src = pack('C4n', split(/[.:]/, $src));
             $dst = pack('C4n', split(/[.:]/, $dst));
             $src lt $dst ? "$src${dst}0"
                          : "$dst${src}1"             }
      <DATA>;
[download]

Both of the above have been tested. They only work if the addresses are IPv4 addresses in dotted form.

By the way, if you have memory problems, you could use an external sort tool as follows:

{
   open(local *TEMP, '>', $sort_input);

   while (<DATA>) {
      my ($src, $dst) = (split)[0, 2];
      $src = pack('C4n', split(/[.:]/, $src));
      $dst = pack('C4n', split(/[.:]/, $dst));
      my $data = $src lt $dst ? "$src${dst}0" : "$dst${src}1";
      print TEMP (unpack('H*', $data), "\n");
   }
}

...[ call external sort tool ]...

{
   open(local *TEMP, '<', $sort_output);

   while (<TEMP>) {
      chomp;
      my @f = unpack('C4nC4na', pack('H*', $_));
      my $src = "$f[0].$f[1].$f[2].$f[3]:$f[4]";
      my $dst = "$f[5].$f[6].$f[7].$f[8]:$f[9]";
      ($src, $dst) = ($dst, $src) if $f[10];
      print("$src -> $dst\n");
   }
}
[download]

The convertion to hex is to avoid having newlines in your data.

Comment on Re^4: Sorting out troubles with advanced-ish sort Select or Download Code

Replies are listed 'Best First'.
Re^5: Sorting out troubles with advanced-ish sort by chargrill (Parson) on May 08, 2006 at 17:22 UTC
All very good suggestions, but I will add the following points: I don't much care the particular order of the IP conversations - 10.10.10.5, 10.10.10.50, 10.10.10.14 can come in any order, so long as each combination of source and port are together, and the 'bar' server replies follow the 'foo' server requests. If only the data I needed was what I wrote in my example - I have the rest of the packet information that I care about - I'm specifically looking for conversations from server 'foo' that don't end with a FIN (an issue known to cause server 'bar' issues (the 'bar' server blocks on trying to read the port) so that no other server 'foo' can be serviced by the single server 'bar'). As such, my data structure (after passing through the file once) roughly looks like this: `# $type consisting of one of ( fin, syn, rst, ack ) #my @packetlog = ( # { # '$source:$port' => [ $type, $seq, $length ], # 'packet' => [ $frame, $src, $dest, $deltaT, $abs, $rel, $cumu +, $byt ], # } # );` [download] Therefore, the (working version of the) last map is quite a bit different than my simplified (working version for my) example: `map { my( $v, $k ) = keys %$_; my $val = $v =~ /pack/ ? $k : $v; my( $src, $srcP, $dst, $dstP ) = split /:/, $val; my( $low, $high ) = sort { $a cmp $b } ( "$src:$srcP", "$dst:$ds +tP" ); my $key = $high . '-' . $low; [ $key, $srcP, $_ ] }` [download] And I can certainly clean things up to more closely match the suggestions by ikegami and japhy, but it's not (for me, anyhow) a simple conversion :) Thankfully, the above suits my purposes, as the code was able to identify my test case (in this instance, someone telneted to the 'bar' server's service port and didn't send anything which triggered the 'bar' server to block on that port and stop servicing requests from any other server). Packing the IPs according to ikegami's post will probably eliminate some cycles, but I don't think I can eliminate `$_` from the anonymous array at the end of the map, because it contains a lot more information :) As written above, it processes roughly 371,000 lines in about 76 seconds on my box. This includes the initial parsing of the file to create the above structure. Also, i don't really want to print all ~371,000 lines, but I would like to capture anything matching my criteria. From suggestions from ikegami and johngg, moving the print outside the loop (therefore dispensing with the `for`) seems to make sense, but since I don't know I've found an offender until the end of the conversation, my real code keeps track of the last N packets, discarding them if they don't appear to end in an anomalous manner. --chargrill `$,=42;for(34,0,-3,9,-11,11,-17,7,-5){$.=pack'c'=>$,+=$_}for(reverse s +plit//=>$ ){$%++?$ %%2?push@C,$_,$":push@c,$_,$":(push@C,$_,$")&&push@c,$"}$C[$# +C]=$/;($#C >$#c)?($ c=\@C)&&($ C=\@c):($ c=\@c)&&($C=\@C);$%=$\|;for(@$c){print$_^ +$$C[$%++]}` [download]	[reply] [d/l] [select]
Re^6: Sorting out troubles with advanced-ish sort by ikegami (Patriarch) on May 08, 2006 at 17:53 UTC
salva made the good that you're not looking to sort, so much as group. You don't need `sort` to do that. `my %conversations; while (<DATA>) { my ($src, $dst) = (split)[0, 2]; $src = pack('C4n', split(/[.:]/, $src)); $dst = pack('C4n', split(/[.:]/, $dst)); my $key = $src lt $dst ? "$src$dst" : "$dst$src"; push(@{$conversations{$key}}, $_); } foreach (values %conversations) { print(@$_); }` [download] outputs 10.10.10.5:1001 -> 10.10.10.10:8000 10.10.10.5:1001 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.5:1001 10.10.10.6:1001 -> 10.10.10.10:8000 10.10.10.6:1001 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.6:1001 10.10.10.5:1000 -> 10.10.10.10:8000 10.10.10.5:1000 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.10:8000 -> 10.10.10.5:1000 10.10.10.6:1000 -> 10.10.10.10:8000 10.10.10.6:1000 -> 10.10.10.10:8000 10.10.10.10:8000 -> 10.10.10.6:1000 10.10.10.7:1000 -> 10.10.10.10:8000 [download] Packing the date might now be overkill. The following should be fine: `while (<DATA>) { my ($src, $dst) = (split)[0, 2]; my $key = $src lt $dst ? "$src $dst" : "$dst $src"; push(@{$conversations{$key}}, $_); }` [download]	[reply] [d/l] [select]