PHP代碼達到執行時間限制

Question

我需要通過包含地圖中的點的數組並檢查它們之間的距離。我需要計算每個節點在200米和50米範圍內有多少個節點。它適用於較小的數值。但是，當我試圖通過它運行更多的值（大約4000用於可伸縮性測試）時發生錯誤，說我已經達到了300秒的最大執行時間。如果可能，它需要能夠在300秒內處理至少這麼多。

我已經閱讀並發現有一種方法來禁用/更改此限制，但我想知道是否有更簡單的方式執行下面的代碼，以便運行它的時間會減少。

for($i=0;$i<=count($data)-1;$i++) 
     { 
      $amount200a=0; 
      $amount200p=0; 
      $amount50a=0; 
      $amount50p=0; 
      $distance; 
      for($_i=0;$_i<=count($data)-1;$_i++) 
      { 
       $distance=0; 
       if($data[$i][0]===$data[$_i][0]) 
       { 
       } 
       else 
       { 
        //echo "Comparing ".$data[$i][0]." and ".$data[$_i][0]." "; 
        $lat_a = $data[$i][1] * PI()/180; 
        $lat_b = $data[$_i][1] * PI()/180; 
        $long_a = $data[$i][2] * PI()/180; 
        $long_b = $data[$_i][2] * PI()/180; 
        $distance = 
          acos(
            sin($lat_a) * sin($lat_b) + 
            cos($lat_a) * cos($lat_b) * cos($long_b - $long_a) 
          ) * 6371; 
        $distance*=1000; 
        if ($distance<=50) 
        { 
         $amount50a++; 
         $amount200a++; 
        } 
        else if ($distance<=200) 
        { 
         $amount200a++; 
        } 
       } 
      } 
      $amount200p=100*number_format($amount200a/count($data),2,'.',''); 
      $amount50p=100*number_format($amount50a/count($data),2,'.',''); 
      /* 
      $dist[$i][0]=$data[$i][0]; 
      $dist[$i][1]=$amount200a; 
      $dist[$i][2]=$amount200p; 
      $dist[$i][3]=$amount50a; 
      $dist[$i][4]=$amount50p; 
      //*/ 
      $dist.=$data[$i][0]."&&".$amount200a."&&".$amount200p."&&".$amount50a."&&".$amount50p."%%"; 
     } 

索引0包含的每個節點的唯一ID，1包含每個節點的緯度和 索引2包含各節點的經度。

錯誤發生在第一個循環內部的第二個循環中。該循環是將所選映射節點與其他節點進行比較的循環。我也使用Haversine公式。

Answer 1

首先，你在大O表示法中執行：O（data^2），這樣會慢一點，實際上或者有兩種可能的解決方案。找到一個在更好的時間解決相同問題的經過驗證的算法。或者，如果你不能，開始移動的內部循環的東西，並在數學上證明，如果你可以轉換內循環爲主要簡單的計算，這是往往你可以做的事情。

經過一些重寫後，我看到一些可能性： 如果$ data不是SPLFixedArray（它具有FAR更好的訪問時間），那麼創建它。因爲您正在訪問該數據很多次（4000^2）* 2。 secound，寫入更清晰的代碼。雖然optizmier會盡其所能，但如果您不嘗試縮小代碼（這隻會使代碼更具可讀性），那麼它可能無法做到儘可能好。

並將中間結果移出循環，也就像數組大小一樣。

Answer 2

目前您正在檢查所有其他積分的積分，實際上您只需要檢查當前積分與其餘積分的積分。 A到B的距離與B到A的距離相同，爲什麼要計算兩次？

我可能會做一個相鄰的數組來計算彼此的範圍內有多少個節點，並且在計算出兩個節點在彼此的範圍內之後，增加該數組中的條目對。

在計算真實距離（永遠不會超快）之前，您應該想出一個非常快的距離近似值，可以用來忽略儘可能多的節點。

一般來說，超越算法的優化，優化的基本規則是：

• 不要你沒有任何處理要做到：不一樣乘以1000 $的距離只要改變你測試的值分別從20和50到0.02和0.05。

• 不要比任何時候更頻繁地調用任何函數：您只需在任何處理開始之前調用count（$ data）一次。例如，不要多次計算常數值：PI()/180。

• 將所有可能的處理移到循環外部。即儘可能預先計算。

另一個小點，這將使你的代碼變得更容易閱讀：

for($i = 0; $i <= count($data) - 1; $i++)是一樣的：

for($i = 0; $i < count($data); $i++)

Answer 3

試試這個：

$max = count($data); 
$CONST_PI = PI()/180; 

for($i=0;$i<$max;$i++) 
{ 
    $amount200a=0; 
    $amount50a=0; 

    $long_a = $data[$i][2] * $CONST_PI; 
    $lat_a = $data[$i][1] * $CONST_PI; 

    for($_i=0;$_i<=$max;$_i++) 
    //or use for($_i=($i+1);$_i<=$max;$_i++) if you did not need to calculate already calculated in other direction 
    { 
     $distance=0; 
     if($data[$i][0]===$data[$_i][0]) continue; 

     $lat_b = $data[$_i][1] * $CONST_PI; 
     $long_b = $data[$_i][2] * $CONST_PI; 
     $distance = 
       acos(
         sin($lat_a) * sin($lat_b) + 
         cos($lat_a) * cos($lat_b) * cos($long_b - $long_a) 
       ) * 6371; 
     if ($distance<=0.2) 
     { 
      $amount200a++; 
      if ($distance<=0.05) 
      { 
       $amount50a++; 
      } 
     } 
    } // for %_i 
    $amount200p=100*number_format($amount200a/$max,2,'.',''); 
    $amount50p=100*number_format($amount50a/$max,2,'.',''); 

    $dist.=$data[$i][0]."&&".$amount200a."&&".$amount200p."&&".$amount50a."&&".$amount50p."%%"; 
} // for $i 

閱讀我認爲，如果你查閱會更好注意$ _i的註釋行將會更快:)