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 包含每个节点的经度。

错误发生在第一个循环内的第二个 for 循环中。此循环是将所选地图节点与其他节点进行比较的循环。我也在使用Haversine 公式。

4

3 回答 3

0

目前，您正在检查所有点与所有其他点，实际上您只需要检查当前点与所有剩余点。A到B的距离和B到A的距离是一样的，为什么要计算两次呢？

我可能会创建一个相邻的数组来计算有多少节点在彼此的范围内，并在我计算出两个节点在彼此的范围内之后增加该数组中的条目对。

您可能应该提出一个非常快速的距离近似值，可用于在计算实际距离之前忽略尽可能多的节点（这永远不会超快）。

一般来说，除了算法优化之外，优化的基本规则是：

  • 不要进行任何您不必做的处理：例如不要将 $distance 乘以 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++ )

于 2013-07-12T10:10:38.797 回答
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

首先，您正在使用大 O 表示法： O(data^2)，这会非常慢，实际上，有两种可能的解决方案。找到一种经过验证的算法，可以在更好的时间解决相同的问题。或者，如果您不能，开始将内容移出内部 for 循环，并在数学上证明您是否可以将内部 for 循环转换为大多数简单的计算，这通常是您可以做的。

经过一些重写，我看到了一些可能性： 如果 $data 不是 SPLFixedArray （它的访问时间更远，），那么就让它吧。因为您多次访问该数据 (4000^2)*2。其次，编写更简洁的代码。尽管 optizmier 会尽力而为，但如果您不尝试最小化代码（这只会使其更具可读性），那么它可能无法做到最好。

并将中间结果移出循环，也类似于数组的大小。

于 2013-07-12T09:51:02.663 回答