실행 시간 제한에 도달 한 PHP 코드

Question

지도의 점을 포함하는 배열을 거쳐서 서로의 거리를 확인해야합니다. 얼마나 많은 노드가 각각 200m와 50m 안에 있는지 계산할 필요가 있습니다. 더 작은 양의 값에 대해서는 정상적으로 작동합니다. 그러나 그것을 통해 더 많은 값 (확장 성 테스트를 위해 약 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는 각 노드의 경도를 포함 포함 포함한다.

첫 번째 루프 안의 두 번째 for 루프에서 오류가 발생합니다. 이 루프는 선택된 맵 노드를 다른 노드와 비교하는 루프입니다. 나는 또한 Haversine 공식을 사용하고있다.

Answer 1

우선 O (데이터^2) 인 을 실행 중입니다. 지옥처럼 느려질 수 있으며 실제로는 가능한 두 가지 해결책이 있습니다. 더 나은 시간에 동일한 문제를 해결하는 입증 된 알고리즘을 찾으십시오. 또는, 당신이 할 수있는 일을 종종 당신이 할 수있는 무언가에 대한 간단한 루프 내부 루프를 변환 할 수 있다면 당신은 어림도없는 루프에서 물건을 이동 시작하고 수학적으로 증명할 수 있습니다.

몇 가지 다시 작성한 후 몇 가지 가능성이 있습니다. $ 데이터가 FAR보다 나은 액세스 시간을 갖는 SPLFixedArray가 아닌 경우 확인하십시오. 여러 번 (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); $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 

for($i = 0; $i <= count($data) - 1; $i++)이와 동일 내가 생각하고 읽으면 더 좋을 것이다. $ _i에 대한 주석 처리 된 행을 nge하면 더 빠를 것입니다.