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

実際にユークリッド距離を計算する必要がありますか? 距離の相対的な大きさを比較するだけの場合は、マンハッタン距離を使用して回避できる可能性があります。これにより、 を 2 回呼び出し、pow()を 1回呼び出す必要がなくなり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ます。

編集: 昨年この問題を調査していたとき、ウィキペディアでいくつかの有用なものを見つけました-はい、それは起こる可能性があります;-)

地理的データだけでなく、データ分析の他の分野にも適用されるように、クラスター化について深く掘り下げた本『 Programming Collective Intelligence: Building Smart Web 2.0 Applications』を強くお勧めします。

于 2009-09-16T17:40:46.333 に答える
4

ジョンが言ったことを拡張して、その関数をインライン化してみるべきだと思います。PHPでの関数呼び出しは非常に遅いので、そこからかなりのスピードアップが得られるはずです。

于 2009-09-16T17:12:44.903 に答える
2

パフォーマンスに大きな問題がある場合に実装できるいくつかのアイデアを次に示します。

  • データの次元を減らします: 長さ/緯度の 2 次元データがあります。おそらく 、元の空間の距離を維持しながら次元数を減らそうとする多次元スケーリング (MDS)などを使用して、1 次元に投影することができます。したがって、距離関数は 2 つではなく 1 つのフィーチャのみを処理する必要があります。別の方法は、主成分分析 (PCA)を使用することです。
  • 検索の高速化: 各マーカーまでの距離を計算するステップは、 KD-treesを使用して改善できます。

これらの手法はどちらもオフライン設定で適用されるため、通常は 1 回計算され、その後何度も使用されます。

于 2009-09-16T18:21:35.453 に答える
1

これが私がしたことです-次の関数を使用して、緯度と経度のメルカトル変換値を使用して、markers（point）テーブルに2つの列を追加しました。

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 に答える
1

ここで、さらに 2 つの改善点を確認できます。

  • $markers を配列からポップするのではなく、for ループでループすることはできますか? 配列のポップは完全に不要です。配列にアイテムを同時に追加および削除する場合は、実際には配列をキューとしてのみ使用する必要があります (そうではありません。それらを処理してから捨てるだけです)。

  • 最初に配列の count() を計算してから、$count 変数を手動で増減する必要があります。ループごとに配列のサイズを再計算するのは無駄です。

于 2009-09-16T17:40:35.657 に答える
1

簡単な最適化は、sqrt(x) < sqrt(y) が x < y の場合に true であることを利用することです。そのため、pixelDistance で sqrt を省略し、ループの外で $distance 二乗を計算できます。ループ外で 21 - $zoomLevel を計算することもできます。二乗値を比較する場合は、2 を掛ける必要があります。もう 1 つの小さな最適化は、10000000 でスケーリングする前に $x1-$x2 を実行して 2 つの乗算を節約することです。さらに、デルタを var に格納してそれ自体で乗算する方が、おそらく pow 関数よりも高速です。さらに、pixeldistance 関数をインライン化することもできます。この種の最適化では、定数倍の速度向上しか得られません。

より大きなスピードアップを実現するには、ある種のアクセラレーション データ構造が必要です。簡単な方法は、マーカーを距離サイズの正方形にビン化することです。次に、ビンを調べて、マーカーがビンの中心のどちら側にあるかに応じて、同じビンと他の 3 つのビンのみにクラスター化するマーカーを探すことができます。これにより、より大きな結果セットの二次アルゴリズムへの最適化を打ち負かす線形時間クラスタリングが得られます。

于 2009-09-16T18:54:17.120 に答える
1

ループ内で実行されるため、 pixelDistance() 関数の高速化がソリューションの一部になる可能性があるようです。これは最初に確認するのに適した場所ですが、そのコードが含まれていないため、確信が持てません。

于 2009-09-16T17:02:43.990 に答える
1

可能であれば、最初の検索でマーカーを経度で並べ替えます。次に、マーカーが並べ替えられたリストの次のマーカーからマーカー幅を超えるとすぐに、残りのマーカーが重複しないことが確実にわかるため、foreach ループを中断して処理時間を大幅に節約できます。私はこれを自分のサイトに実装しましたが、非常に効率的に機能します。

于 2009-10-26T19:02:03.883 に答える