Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

intermix list of items

by tstock (Curate)
on Oct 10, 2004 at 16:56 UTC ( #398008=perlquestion: print w/ replies, xml ) Need Help??
tstock has asked for the wisdom of the Perl Monks concerning the following question:

weekend monks...

I have a list of IP addresses in dot decimal format, a class A RFC 1918 internal addresses (10.0.0.0/8). I would like to scan these IP's for a service, but instead of doing it sequentially (10.0.0.1, 10.0.0.2, ...) I would like to intermix different class C's as much as possible. What I first tried did not work:
my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); @list = sort intermix @list; sub intermix { return ( substr( $a, 0, rindex($a, '.')) eq substr( $b, 0, rindex($b, '.')) ) ? 1 : 0; }
Randomizing the list would be one way sort of around the sequential problem, but not as neat as what I was looking for. The reason behind the requirement is to avoid hitting limits and easy the load on individual routers/switches for each segment. Any nice perl idioms to solve this problem?

Tiago

Comment on intermix list of items
Download Code
Re: intermix list of items
by davido (Archbishop) on Oct 10, 2004 at 17:04 UTC

    Since you have the @list of all IP's in your hand at once, wouldn't it be adequate to just perform a Fisher-Yates Shuffle on them?

    If the goal is simply to not have sequential IP's, and if instead, random order is sufficient, the Fisher Yates shuffle might work great.


    Dave

Re: intermix list of items
by pg (Canon) on Oct 10, 2004 at 17:09 UTC

    That eq definitely does not make sense. I can guess what was in your mind, you probably thought that by using 'eq', sort will group elements for you base on how common they are. No, that is not what sort does. You have to tell sort "between each pair of two elements, how they shall be ordered".

    You are looking for something like:

    use Data::Dumper; my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); @list = sort intermix @list; print Dumper(@list); sub intermix { return ( substr( $a, 0, rindex($a, '.')) gt substr( $b, 0, rindex($b, '.')) ) ? 1 : 0; }
      'gt' refers to the size of the string, running your example solution didn't seem to help. I was going for (and failed) non-equality of the substring means they are identical in sort order by using 'eq'.
        "'gt' refers to the size of the string"

        No. In your code, gt looks at "dictionary sequence".

        If string size/length is what you wanted, say length($str) expliciltly.

        use Data::Dumper; my @foo = ("abc", "bc"); print Dumper(sort bar1 @foo); print Dumper(sort bar2 @foo); sub bar1 { return $a gt $b; } sub bar2 { return length($a) gt length($b); }
Re: intermix list of items
by pg (Canon) on Oct 10, 2004 at 17:37 UTC
    sub intermix { return ( substr( $a, 0, rindex($a, '.')) eq substr( $b, 0, rindex($b, '.')) ) ? 1 : 0; }

    The use of ?: is not necessary:

    sub intermix { return ( substr( $a, 0, rindex($a, '.')) eq substr( $b, 0, rindex($b, '.')) ); # ? 1 : 0; }
Re: intermix list of items
by ikegami (Pope) on Oct 10, 2004 at 18:13 UTC

    btw, the compare function is suppose to return -1, 0, +1, not just 0 and 1, so I expect your sort has some amount of randomness to it.

    Maybe you want something like:

    sub intermix { my $a_prime = join('.', reverse(split(/\./, $a))); my $b_prime = join('.', reverse(split(/\./, $b))); $a_prime cmp $b_prime } my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); @list = sort intermix @list; use Data::Dumper; print Dumper(@list); __END__ output ====== $VAR1 = '10.1.1.1'; $VAR2 = '10.2.2.1'; $VAR3 = '10.1.1.2'; $VAR4 = '10.2.2.2';

    Almost the same, but more efficient:

    sub intermix { my $a_prime = reverse($a); my $b_prime = reverse($b); $a_prime cmp $b_prime } my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); @list = sort intermix @list; use Data::Dumper; print Dumper(@list); __END__ output ====== $VAR1 = '10.1.1.1'; $VAR2 = '10.2.2.1'; $VAR3 = '10.1.1.2'; $VAR4 = '10.2.2.2';

    This is the same thing as the last, but probably more efficient, especially for longer lists:

    my @list = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); @list = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [ $_, ''.reverse($_) ] } @list; use Data::Dumper; print Dumper(@list); __END__ output ====== $VAR1 = '10.1.1.1'; $VAR2 = '10.2.2.1'; $VAR3 = '10.1.1.2'; $VAR4 = '10.2.2.2';

    Note: Given addresses of the form 'a.b.c.d', the above snippets only work well if there is there is a common 'd' of for every 'a.b.c' in the list.

      Here's an algorithm that doesn't suffer from the problem mentioned in the Note above:

      my @list = ('10.1.1.[1..2]', '10.2.2.[1..2]', '10.3.3.[3..6]'); my @list_prime = map { my $n = $_; $n =~ s/\[(\d+)\.\.(\d+)\]//; [ $n, $1, $2 ] } @list; my @ordered_list; my $done; do { $done = 1; foreach (@list_prime) { next unless defined($_); if ($_->[1] > $_->[2]) { undef($_); next } push(@ordered_list, $_->[0].($_->[1]++)); $done = 0; } } while (!$done); use Data::Dumper; print Dumper(@ordered_list); __END__ output ====== $VAR1 = '10.1.1.1'; # First from first. $VAR2 = '10.2.2.1'; # First from second. $VAR3 = '10.3.3.3'; # First from third. $VAR4 = '10.1.1.2'; # Second from first. $VAR5 = '10.2.2.2'; # Second from second. $VAR6 = '10.3.3.4'; # Second from third. $VAR7 = '10.3.3.5'; # Third from third. $VAR8 = '10.3.3.6'; # Fourth from third.

      It can probably be optimised.

Re: intermix list of items
by tstock (Curate) on Oct 16, 2004 at 05:11 UTC
    thanks all. I went with the following based on your feedback -
    use strict; my @targets = ('10.1.1.1', '10.1.1.2', '10.2.2.1', '10.2.2.2'); my @list = intermix( @targets ); use Data::Dumper; print Dumper \@list; sub intermix { my @list = @_; my %hash; # separating hash my @ret; # returning list # build hash structure, each similar first 3 octects as key # array reference w/ IP addresses as values for (@list) { push( @{ $hash{ substr($_,0,rindex($_,'.')) } }, $_ ); } my @keys = keys %hash; while (@keys) { push(@keys, shift(@keys)); # rotate keys # extract one element, or delete the array ref and try again my $item = shift @{$hash{ $keys[0] }} || shift @keys && next; push @ret, $item; } return @ret; } __END__ $VAR1 = [ '10.1.1.1', '10.2.2.1', '10.1.1.2', '10.2.2.2' ];
    This doesn't require a specially defined sequential list type. I'm sorry it doesn't look small and neat though.

    Tiago

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://398008]
Approved by davido
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (12)
As of 2014-12-22 11:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (116 votes), past polls