21

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

笔记：

  • 当 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;
    }
}
4

8 回答 8

9

你真的需要计算欧几里得距离吗？如果您只是比较距离的相对大小，您可能可以使用曼哈顿距离，这将节省您两次调用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 应用程序》一书，该书深入研究了集群，不仅适用于地理数据，还适用于其他数据分析领域。

于 2009-09-16T17:40:46.333 回答
4

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

于 2009-09-16T17:12:44.903 回答
2

以下是您可以实施的一些想法，以防性能出现重大问题：

  • 减少数据的维度：您有长/纬度的 2d 数据，也许您可​​以尝试使用 多维缩放 (MDS)之类的方法将其投影到 1D ，它试图减少维数，同时保留原始空间中的距离，因此距离函数只需要处理一个特征而不是两个。另一种方法是使用主成分分析 (PCA)
  • 更快的搜索：使用KD-trees可以改进计算到每个标记的距离的步骤。

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

于 2009-09-16T18:21:35.453 回答
1

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

于 2009-09-16T17:02:43.990 回答
1

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

  • 您可以使用 for 循环遍历 $markers 而不是将它们从数组中弹出吗？数组弹出是完全不需要的——如果你同时向它们添加和删除项目，你真的应该只使用数组作为队列（你不是；你只是在处理它们然后把它们扔掉）

  • 您应该在开始时尝试计算数组的 count()，然后手动增加或减少 $count 变量。每次循环重新计算数组的大小是浪费的。

于 2009-09-16T17:40:35.657 回答
1

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

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

于 2009-09-16T18:54:17.120 回答
1

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

于 2009-10-26T19:02:03.883 回答
1

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

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 函数并将其内联提高了近一半的性能！

于 2009-12-28T22:01:40.397 回答