题

我当前的代码非常快，但我需要使其更快，以便我们可以容纳更多标记。有什么建议么？

笔记：

  • 当 SQL 语句按标记名称排序时，代码运行速度最快 - 它本身完成了对标记进行聚类的部分工作（同一位置的标记名称通常很相似，但并不总是相似）。
  • 我无法对标记进行预聚类，因为可以动态搜索和过滤它们。
  • 我尝试过基于网格的聚类 - 但结果通常不是很好。
  • 我知道这些星团在墨卡托投影上略有倾斜。
  • 我对商业集群服务不感兴趣。

代码：

$singleMarkers = array();
$clusterMarkers = array();

while (count($markers)) {
    $marker  = array_pop($markers);
    $cluster = array();

    // Compare marker against all remaining markers.
    foreach ($markers as $key => $compareMarker) {
        // This function returns the distance between two markers, at a defined zoom level.
        $pixels = pixelDistance($marker['lat'], $marker['lng'], $compareMarker['lat'], $compareMarker['lng'], $zoomLevel);
        // If two markers are closer than defined distance, remove compareMarker from array and add to cluster.
        if ($pixels < $distance) {
            unset($markers[$key]);
            $cluster[] = $compareMarker;
        }
    }

    // If a marker was added to cluster, also add the marker we were comparing to.
    if (count($cluster) > 0) {
        $cluster[] = $marker;
        $clusterMarkers[] = $cluster;
    } else {
        $singleMarkers[] = $marker;
    }
}

function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) {
    $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels.
    $y1 = $lat1*10000000;
    $x2 = $lon2*10000000;
    $y2 = $lat2*10000000;

    return sqrt(pow(($x1-$x2),2) + pow(($y1-$y2),2)) >> (21 - $zoom); //21 is the max zoom level
}

更新

这是当前的代码：

$singleMarkers = array();
$clusterMarkers = array();

// Minimum distance between markers to be included in a cluster, at diff. zoom levels
$DISTANCE = (10000000 >> $ZOOM) / 100000;

// Loop until all markers have been compared.
while (count($markers)) {
    $marker  = array_pop($markers);
    $cluster = array();

    // Compare against all markers which are left.
    foreach ($markers as $key => $target) {
        $pixels = abs($marker['lat']-$target['lat']) + abs($marker['lng']-$target['lng']);

        // If the two markers are closer than given distance remove target marker from array and add it to cluster.
        if ($pixels < $DISTANCE) {
            unset($markers[$key]);
            $cluster[] = $target;
        }
    }

    // If a marker has been added to cluster, add also the one we were comparing to.
    if (count($cluster) > 0) {
        $cluster[] = $marker;
        $clusterMarkers[] = $cluster;
    } else {
        $singleMarkers[] = $marker;
    }
}
有帮助吗？

解决方案

您实际上需要计算 欧氏距离？如果您只是比较距离的相对大小，您可能可以使用 曼哈顿距离, ，这将为您节省两次调用 pow() 和一到 sqrt(): 

function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) {
    $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels.
    $y1 = $lat1*10000000;
    $x2 = $lon2*10000000;
    $y2 = $lat2*10000000;

    return ($x1-$x2) + ($y1-$y2) >> (21 - $zoom);
}

不确定您是否需要 >> (21 - $zoom) 有点适合你的计算，所以我把它留下了。但是，除非您实际上需要在其他地方使用计算出的距离值，否则您可能可以直接使用纬度/经度（无需乘以任何值）并采用曼哈顿距离（假设您预先计算） $distance 来适应该测量，这在计算方面比强制所有距离适应单位和大小要便宜得多 $distance.

编辑：当我去年研究这个问题时，我在维基百科上发现了一些有用的东西 - 是的，它可能会发生;-)

我也强烈推荐这本书 集体智慧编程：构建智能 Web 2.0 应用程序 它深入探讨了聚类，不仅应用于地理数据，还应用于数据分析的其他领域。

其他提示

扩展约翰所说的内容，我认为你应该尝试内联该函数。PHP 中的函数调用非常慢，因此您应该从中获得相当大的加速。

这就是我所做的 - 我使用以下函数向标记（点）表添加了两列额外的列，其中包含经度和纬度的墨卡托转换值：

public static $offset = 268435456;
public static $radius = 85445659.44705395; /* $offset / pi(); */

function LonToX($lon)
{
    return round(self::$offset + self::$radius * $lon * pi() / 180);        
}

function LatToY($lat)
{
    return round(self::$offset - self::$radius * log((1 + sin($lat * pi() / 180)) / (1 - sin($lat * pi() / 180))) / 2);
}

这样我就可以得到准确放置的簇。我仍在尝试找出如何避免使用 array_pop 并每次循环。到目前为止，它对于 1000 个以下的标记相当有效。稍后我将发布 +5K 和 +10K 标记的结果。

避免使用 PixelDistance 函数并将其内联，性能几乎提高了一半！

看起来加速 PixelDistance() 函数可能是您的解决方案的一部分，因为它在循环内运行。这是一个首先查看的好地方，但您没有包含该代码，所以我不能确定。

我在这里还可以看到另外两个可能的改进：

  • 您可以在$循环中循环循环循环，而不是将它们从数组中弹出吗？数组弹出是完全不需要的 - 如果您同时向数组添加和删除项目，那么您实际上应该只将数组用作队列（您不是；你只是处理它们然后扔掉它们）

  • 您应该尝试在开始时计算数组的计数（），然后手动增加或减少$计数变量。重新计算每个循环的阵列的大小都是浪费的。

如果性能存在重大问题，您可以实施以下一些想法：

  • 降低数据的维度: ：您有长/lat的2D数据，也许您可​​以尝试使用类似的内容将其投影到1D多维标度 (MDS) 在保留原始空间中距离的同时，它试图减少尺寸的数量，因此距离函数只需要处理一个功能而不是两个功能。另一种方法是使用 主成分分析（PCA）
  • 更快的搜索: ：可以使用计算每个标记距离的步骤可以使用 KD树.

这两种技术都是在离线环境中应用的，因此它们通常只计算一次，然后多次使用。

一个简单的优化是利用当且仅当 x < y 时 sqrt(x) < sqrt(y) 为 true 的优势，因此您可以省略 PixelDistance 中的 sqrt 并在循环外计算 $distance 平方。您还可以在循环外计算 21 - $zoomLevel，如果要比较平方值，则必须将其乘以 2。另一个小的优化是在缩放 10000000 之前通过执行 $x1-$x2 来节省 2 次乘法。再多说一点，将 delta 存储在 var 中并与其自身相乘可能比 pow 函数更快。对于更多内容，您可以内联像素距离函数。这种优化只会产生恒定因子的加速。

为了获得更大的加速，您将需要某种加速数据结构。一种简单的方法是将标记放入距离大小的方块中。然后，您可以遍历这些垃圾箱，查找仅在同一个垃圾箱中聚集的标记，并根据标记落在垃圾箱中心的哪一侧来选择其他 3 个标记。这将导致线性时间聚类，它将击败二次算法的任何优化以获得更大的结果集。

如果可以的话，在初始搜索时按经度对标记进行排序；那么一旦一个标记大于排序列表中下一个标记的标记宽度，您肯定知道其余标记不会重叠，因此您可以中断 foreach 循环并节省大量处理时间。我已经在自己的网站上实现了这个，并且工作非常有效。

我有一些Python源代码 这里.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top