Category: Text Processing
Author/Contact Info Jeff japhy Pinyan
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,
  @_;
}
Replies are listed 'Best First'.
RE: IP Address sorting
by japhy (Canon) on Oct 24, 2000 at 03:26 UTC
    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
));

    [download]


    $_="goto+F.print+chop;\n=yhpaj";F1:eval
[reply]
[d/l]
Re: IP Address sorting
by tadman (Prior) on Feb 13, 2001 at 08:13 UTC
    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($_),
    @_;
  }

    [download]
    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) ...

    [download]
    BTW, I tested both with 100_000 random IP addresses by 10 runs (approx 86 to 150s per test).
[reply]
[d/l]
[select]
[reply]

Back to Code Catacombs