获取免费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

布尔in_array（混合$针，数组$草垛[，布尔$严格= 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; 
    } 
    } 

时间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; 
     } 
} 

时间PHP test.php的

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

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

如果你能得到与升序

在伪中使用的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代码，其中i由$计数repalce回声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 ; 
    ?> 

它需要大约10秒; 时间PHP test.php的真正0m10.626s 用户0m10.416s SYS 0m0.168s