Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"

Lookahead algorithm for IP subroutine

by hok_si_la (Curate)
on May 10, 2005 at 18:23 UTC ( #455705=perlquestion: print w/replies, xml ) Need Help??
hok_si_la has asked for the wisdom of the Perl Monks concerning the following question:

Greetings monks

I need to come up with an algorithm to find $j sequential IP addresses within a single $vlan if. It is possible that there is not $j sequential address within the table. In that case $j addresses will be selected by the lowest value of difference between the highest octet4 and lowest octet4.

The code below selects $j IPs from $vlan according to their location within the table. I should also add that although there are many things that may need be changed regarding syntax, I really only have 30 mins to get this cranking.
Any ideas? Is there a quick way to do this?

Each $vlan contains about 250 or so address & $j <= 5

############################################################ sub getips ############################################################ { my $j = shift; my $vlan= shift; my $name = "ips" . $j; my ($sth, $dbh, %ips, $i, @iparray); $dbh=DBI->connect('DBI:ODBC:Servers', { RaiseError => 1, AutoCommit => + 0 }); $sth = $dbh->prepare( "SELECT IPs.* FROM IPs LEFT OUTER JOIN StaticIP +s ON IPs.Octet1 = StaticIPs.octet1 AND IPs.Octet2 = StaticIPs.octet2 +AND IPs.Octet3 = StaticIPs.octet3 AND IPs.Octet4 = StaticIPs.octet4 W +HERE (StaticIPs.octet1 IS NULL) AND (IPs.VLAN = '$vlan')" ); $sth->execute; $sth->bind_columns( \( @ips{ @{$sth->{NAME_lc} } } )); #----Saves spe +ed by binding columns to their values. See netTools_help.doc. $sth->{'ChopBlanks'} =1; #----Removes extra spaces from fixed char +fields. See netTools_help.doc. $i=0; while ($sth->fetch) { if ($ips{'octet1'}) { $iparray[$i]=join(".", "$ips{'octet1'}", "$ips{'octet2'}", "$ips{' +octet3'}", "$ips{'octet4'}"); } ++$i; } $j--; print scrolling_list(-class=>'df', -name=>'$name', -values=>[@iparray] +, -size=>'1', -default=>$iparray[$j]); $sth->finish(); $dbh->disconnect(); #----Needed to free up system resources. }

Thanks in advance,

Replies are listed 'Best First'.
Re: Lookahead algorithm for IP subroutine
by dragonchild (Archbishop) on May 10, 2005 at 18:34 UTC
    This is just rewriting your code with a basic few improvements, just to make it easier to work with. Note - your SQL statement is still borked.
    sub getips { my ( $j, $vlan ) = @_; my $name = "ips" . $j; my ($sth, $dbh, %ips, $i, @iparray); my $dbh = DBI->connect('DBI:ODBC:Servers', { RaiseError => 1, Auto +Commit => 0 }); my $sth = $dbh->prepare( <<__END_SQL__ ); SELECT IPs.octet1 ,IPs.octet2 ,IPs.octet3 ,IPs.octet4 FROM IPs LEFT OUTER JOIN StaticIPs ON IPs.Octet1 = StaticIPs.octet1 AND IPs.Octet2 = StaticIPs.octet2 AND IPs.Octet3 = StaticIPs.octet3 AND IPs.Octet4 = StaticIPs.octet4 WHERE StaticIPs.octet1 IS NULL AND IPs.VLAN = ? __END_SQL__ $sth->execute( $vlan ); my @ips; $sth->bind_columns( \( $ips[0], $ips[1], $ips[2], $ips[3] ) ); $sth->{'ChopBlanks'} = 1; my @iparray; while ($sth->fetch) { next unless $ips[0]; push @iparray, join '.', @ips; } $sth->finish(); $dbh->disconnect(); print scrolling_list( -class => 'df', -name => $name, -size => 1, -values => [@iparray], -default => $iparray[-1] ); }

    • In general, if you think something isn't in Perl, try it out, because it usually is. :-)
    • "What is the sound of Perl? Is it not the sound of a wall that people have stopped banging their heads against?"
Re: Lookahead algorithm for IP subroutine
by demerphq (Chancellor) on May 11, 2005 at 16:07 UTC

    To the best of my understanding from the CB you can factor a lot of stuff out of your current approach. Here is what i came up with based on your scratchpad.

    use strict; use warnings; sub find_seq { my ($num,$array)=@_; # assert that @$array is sorted numerically increasing return unless $num<=@$array; # illegal $num--; # num is one based, we need a 0 based value my $min_pos=$num; my $min=$array->[$min_pos] - $array->[0]; for my $i ($num..$#$array) { if ($array->[$i] - $array->[$i-$num] == $num) { return ($i-$num,$i); } elsif ($min > $array->[$i]-$array->[$i-$num]) { $min=$array->[$i] - $array->[$i-$num]; $min_pos=$i; } } return ($min_pos-$num,$min_pos); } my @array=sort { $a <=>$b } qw( 1 3 4 5 6 8 15 31 61 62 63 64 65 66 67 70 71 72 73 ); for my $num (2..@array-5) { if (my ($s,$f)=find_seq($num,\@array)) { print "seq($num) == \@array[$s..$f]=(", join(",",@array[$s..$f]),")\n"; } else { print "No sequence for $num\n"; } } __END__ seq(2) == @array[1..2]=(3,4) seq(3) == @array[1..3]=(3,4,5) seq(4) == @array[1..4]=(3,4,5,6) seq(5) == @array[8..12]=(61,62,63,64,65) seq(6) == @array[8..13]=(61,62,63,64,65,66) seq(7) == @array[8..14]=(61,62,63,64,65,66,67) seq(8) == @array[8..15]=(61,62,63,64,65,66,67,70) seq(9) == @array[8..16]=(61,62,63,64,65,66,67,70,71) seq(10) == @array[8..17]=(61,62,63,64,65,66,67,70,71,72) seq(11) == @array[8..18]=(61,62,63,64,65,66,67,70,71,72,73) seq(12) == @array[7..18]=(31,61,62,63,64,65,66,67,70,71,72,73) seq(13) == @array[6..18]=(15,31,61,62,63,64,65,66,67,70,71,72,73) seq(14) == @array[1..14]=(3,4,5,6,8,15,31,61,62,63,64,65,66,67)

    It expects a length and an array of increasing ordered numbers. It finds the start index and end index of the array such that, the sequence is the lowest contiguous sequence of the required size, or failing that a sequence where the difference between the highest and lowest value is the least.

    The trick with this is that you can tell if a sequence is contiguous by subtracting the beginnig from the end, likewise we can get the sequence with the least difference between begin and end by the same approach. We can remember the "best" sequence we've seen by storing its endpoint, and we can simply exit when we have encountered the first contiguous sequence (which will be the lowest since we start low and iterate up). Anyway, the idea here is to take something like this and adapt it to your exact requirements, the way you formatted the code and stuff made it fairly hard to read and work out. Alway use whitespace in your queries to make them readable, SQL is an ugly language to begin with so making it readable is really important.


    The text in this node was added sometime after it was posted in an attempt to clarify the code for hok.

    Later Update: Heres a cleaner and annotated version of the code, same idea, but simplified further. Note the early termination when it finds a contiguous sequence which allows this to be worst case O(N) and best case lower.

    sub find_seq { my ($num,$array)=@_; # assert that @$array is sorted numerically increasing return if $num > @$array; # ensure array is big enough $num--; # num is one based, we need a 0 based value # the default return will be the first N values, # if we find better then we will overwrite these my $min_start = 0; my $min_end = $num; my $min = $array->[$num] - $array->[0]; # start at num as below that nothing can match for my $end ( $num .. $#$array) { my $start = $end - $num; my $diff = $array->[$end] - $array->[$start]; if ( $min > $diff ) { # we have found a better sequence, # so remember where it is $min = $diff; $min_end = $end; $min_start = $start; } # if the sequence is contiguous we can finish last if $diff == $num; } return ( $min_start, $min_end ); }

Re: Lookahead algorithm for IP subroutine
by jeffa (Bishop) on May 11, 2005 at 16:31 UTC

    This was originally on my scratchpad, it is posted here simply for TIMTOWTDI. My idea is to read through the entire array and place consecutive integers into their own "buckets." Keep pushing the integers if the next integer is consecutive into another array (which is stored in an outer array), and start a new array when no longer consecutive. Then, (and this was inspired by some of dragonchild's code) simply sort that 2-d array based on the size if the array's it contains. The first array (element) contains the largest amount of consecutive integers.

    use strict; use warnings; use Data::Dumper; my @proximity = (1..5, 8..10, 15..30, 35..40); my @bucket; my $j = 0; for my $k (0 .. $#array) { if ($proximity[$k] == $proximity[$k+1] - 1) { push @{ $bucket[$j] }, $proximity[$k]; } else { $j++; } } my @ip = (sort { $#$b <=> $#$a } @bucket)[0]; print Dumper \@ip;
    Your Milleage Will Vary, naturally ... but this is a fairly easy to understand solution, if not a bit memory intensive.


    (the triplet paradiddle with high-hat)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://455705]
Approved by moot
[Discipulus]: Mr haukex from Germany! thanks a lot to the other parteciapant our dear Mr afoken.. ;=)
[Discipulus]: no, seriously thanks both, i missed 'scientist' and 'floating point' and the resarche was imposible..
Discipulus go to his cell to bookmark this
[haukex]: Well to be honest I just did a super search for "every should know floating" ;-)
[Discipulus]: floating was the keyword and.. to use supersearch is plus sign not a (plus) sin

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (10)
As of 2017-06-26 20:54 GMT
Find Nodes?
    Voting Booth?
    How many monitors do you use while coding?

    Results (594 votes). Check out past polls.