1

マップ内のポイントを含む配列を調べて、それらの距離を確認する必要があります。それぞれのノードから 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 には各ノードの経度が含まれます。

エラーは、最初のループ内の 2 番目の for ループで発生します。このループは、選択したマップ ノードを他のノードと比較するループです。私もハーバーシンフォーミュラを使っています。

4

3 に答える 3

0

これを試して：

$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 のコメントアウトされた行を変更すると、まったく速くなります:)

于 2013-07-12T10:48:55.247 に答える
0

現在、すべてのポイントを他のすべてのポイントに対してチェックしていますが、実際には現在のポイントを残りのすべてのポイントに対してチェックするだけで済みます。A から B までの距離は、B から A までの距離と同じなのに、なぜ 2 回計算するのですか?

おそらく、互いに範囲内にあるノードの数をカウントする隣接配列を作成し、2 つのノードが互いに範囲内にあることを計算した後、その配列内のエントリのペアをインクリメントします。

おそらく、実際の距離を計算する前に、できるだけ多くのノードを無視するために使用できる距離の非常に高速な概算を考え出す必要があります (超高速になることはありません)。

一般的に言えば、アルゴリズムの最適化を超えて、最適化の基本的なルールは次のとおりです。

  • 必要のない処理は行わないでください: $distance に 1000 を掛けないようにします。テストする値を 20 と 50 からそれぞれ 0.02 と 0.05 に変更するだけです。

  • 必要以上に関数を呼び出さないでください: count($data) を呼び出す必要があるのは、処理を開始する前に 1 回だけです。

  • 定数値を複数回計算しないでください:PI()/180たとえば。

  • 可能なすべての処理をループの外に移動します。つまり、可能な限り事前に計算します。

コードを少し読みやすくするもう 1 つのマイナーなポイント:

for( $i = 0; $i <= count( $data ) - 1; $i++ )以下と同じです:

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

于 2013-07-12T10:10:38.797 に答える