获取空闲IP地址的算法

Question

我用yii2。我需要通过getFreeIPAddress方法找到未使用(不在数据库中)的IP。我有这样的课：

class Radreply extends ActiveRecord {

   const ATTRIBUTE_DEFAULT_IP_ADDRESS = 'Framed-IP-Address';

   const IP_ADDRESS_MAX = '10.255.255.255';  // max value for IP 
   const IP_ADDRESS_MIN = '10.0.0.11';       // min value for IP

   public function getIntegerIP(){  // converts IP from string to integer format
       return ip2long($this->value);
   }

   public static function getFreeIPAddress(){
        $records = self::findAll(['attribute'=>self::ATTRIBUTE_DEFAULT_IP_ADDRESS]); // get all record which contain IP address
        $existIPs = ArrayHelper::getColumn($records,'integerIP'); // get array of IP which is converted to integer by method getIntegerIP

        for ($integerIP = ip2long(self::IP_ADDRESS_MIN); $integerIP<=ip2long(self::IP_ADDRESS_MAX); $integerIP++){
        // increasing one by one IP address in integer format from value IP_ADDRESS_MIN to value IP_ADDRESS_MAX

            if (!in_array($integerIP, $existIPs)){
                $stringIP = long2ip($integerIP);
                $arrayDigits = explode('.', $stringIP);
                $lastDigit = array_pop($arrayDigits);

                if ($lastDigit!='0'){ // check if last digit of IP is not 0
                    return $stringIP;
                }

            }

        }
        return '';
    }
}

方法getFreeIPAddress工作查找，但在数据库中有大量的IP记录，并逐个增加IP，检查数据库中是否存在此IP是很长的路。我怎样才能优化这个算法？是否有更快的方法获得未使用的IP？

Answer 1

我想，我已经找到了更好的解决方案，没有额外的表在数据库中

class Radreply extends ActiveRecord {

  const ATTRIBUTE_DEFAULT_IP_ADDRESS = 'Framed-IP-Address';

  const IP_ADDRESS_MAX = '10.255.255.255';  // max value for IP 
  const IP_ADDRESS_MIN = '10.0.0.11';       // min value for IP

  public function getIntegerIP(){  // converts IP from string to integer format
      return ip2long($this->value);
  }

    public static function getFreeIPAddress(){
        $records = self::findAll(['attribute'=>self::ATTRIBUTE_DEFAULT_IP_ADDRESS]); // gets all record which contain IP address
        $existIPs = ArrayHelper::getColumn($records,'integerIP'); // gets array of IP which is converted to integer by method getIntegerIP

        $intIpAddressMin = ip2long(self::IP_ADDRESS_MIN);     // gets min IP in integer format
        $endRange = empty($existIPs) ? $intIpAddressMin : max($existIPs);  // checks if at least one IP is used
        $availableIPs = range( $intIpAddressMin, $endRange + 2);   // generates array with available IP addresses (+2 because next address can be with last digit 0)
        $missingIPs = array_diff($availableIPs,$existIPs);  // removes all used IP

        foreach ($missingIPs as $value){
            $lastDigit = $value % 256;
            if ($lastDigit != 0){
                return long2ip($value);
            }
        }
        return '';
    }
}

Answer 2

bool in_array (混合$needle，数组$haystack，bool $strict = FALSE )

在我看来，你可以设定严格的真理。

我的带有的php代码

<?php                                                                                                                                                            

 $y="1800";
 $x = array();
 for($j=0;$j<50000;$j++){
        $x[]= "{$j}";
 }

 for($i=0;$i<30000;$i++){
    if(in_array($y,$x)){
            continue; 
     }
  }

time php test.php

real    0m4.418s
user    0m4.404s
 sys    0m0.012s

当严格时为真

for($i=0;$i<30000;$i++){
    if(in_array($y,$x ,true)){
              continue;
       }
 }

time php test.php

 real   0m1.548s
 user   0m1.540s
 sys    0m0.004s

更重要的是，如果你能得到使用的ip与升序。您可以得到o(m+n)时间复杂度，其中m是您应该尝试的所有ip的长度，n是使用合并算法的db中所有ip的长度。

如果您可以获得具有升序的已使用ip，则为

伪码 .

tmpIp = minIp;
while(temIp <= maxIp){
         if( dbIsEmpty){
             break;
         }
            dbIp =getNextFromDb();

        while(temIp < dbIp){
         printf temIp ;
         temIp ++;
        }
        temIp ++;
 }
while(temIp <= maxIp){
    printf temIp ;
    temIp++;
}

下面是我的php代码，在这里，我通过$count++；回显ip，在这个演示中，大约有80000个ip具有长的类型。

<?php                                                                                                                                                                                        
  function  mergeSort( $result){
    $minIp =  ip2long('10.0.0.11') ;
    $maxIp = ip2long('10.255.255.255');



    $count =0;
    $tmpIp = $minIp;
    while($temIp <= $maxIp){
         if( empty($result)){
        break ;
     }
     $tmp = array_pop($result);
     $dbIp =$tmp['ip'];

        while($temIp < $dbIp){
        // echo temIp ;
         // i repalce  it by count ++  , i don't want it 
        //full my teminal .
        $count ++;
         $temIp ++;
        }
        $temIp ++;   


    }
    while($temIp <= $maxIp){
        //echo  $temIp ; replace by $count++
        $count ++;
        $temIp++;
    }
    return $count -1;

}

$servername = "localhost";
$username = "root";
$password = "aaaaa";
$dbname = "IP";

$conn =  new PDO('mysql:host=' . $servername . ';dbname=' . $dbname , $username, $password);
$conn->setAttribute(PDO::ATTR_AUTOCOMMIT , true);
$stmt = $conn->prepare("select * from  ipTable  order by ip desc");
   $stmt->execute();
   $result = $stmt->fetchAll();
   $count  = mergeSort($result);
   echo $count ;
     ?>

它大约需要10s；time php test.php 184460881真实的0m10.626s用户0m10.416ssys 0m0.16s