IP Address sorting

[japhy]

Category:

Text Processing

Description:

Sorts N IP addresses in O(Nk) time, each and every time. Uses the technique called radix sorting.

use Socket qw( inet_aton inet_ntoa );

sub IP_radix_sort {
  for (my $i = 3; $i >= 0; $i--) {
    my @table;
    for (@_) {
      push @{ $table[unpack "\@$i C", $_] }, $_;
    }
    @_ = map @$_, @table;
  }
  return @_;
}

sub IPsort {
  map inet_ntoa,
  IP_radix_sort
  map inet_aton,
  @_;
}

[japhy]

jcwren (whose nick I CONTINUALLY mistype as 'jcrewn') suggested I define the limits of this function. It takes domain names, dotted IP addresses, and large decimal numbers. It RETURNS dotted IP addresses though.

require "IPsort.pl";  # assuming that's where you put it
@IPs = IPsort(qw(
  12.43.12.65 48.23.6.1 4.1.64.23 www.bergen.org 84394239
));



$_="goto+F.print+chop;\n=yhpaj";F1:eval

[tadman]

japhy's code is certainly very quick, Benchmarking about 43% better than anything I could come up with on short notice. The 'radix_sort' is obviously more efficient for this kind of application than the built in sort of Perl.

However, under Perl 5.6 + strict + '-w', the following change is required to avoid compilation errors:

  sub IPsort {
    map inet_ntoa($_),
    IP_radix_sort
    map inet_aton($_),
    @_;
  }

The alternative code which Benchmarks in at #2, but has the advantage of simplicity:

    sub byip { inet_ntoa($a) cmp inet_ntoa($b) }

    foreach (sort byip @ip_list) ...

BTW, I tested both with 100_000 random IP addresses by 10 runs (approx 86 to 150s per test).

[japhy]

"Short notice"? I posted this back in October! ;)

japhy -- Perl and Regex Hacker