1

マップに表示するポイントの (非常に長い) リストがあります。各ポイントからユーザーが入力したポイントまでの距離を計算し、リストを最も近いものから最も遠いものへと並べ替える必要があります。

今、私はこのようにしています：

private List<Point> sortedPointList(LatLng ll, List<Point> pointList)
    SparseArray<Double> distances = new SparseArray<Double>();
    for (Point ll : pointList){
        double distance = calcDistance(ll.getLatLng(), point);
        distances.put(ll.getId(), distance);
    }
    Collections.sort(pointList, new Comparator<Point>(){

        @Override
        public int compare(final Tramo lhs, final Tramo rhs) {
            return distances.get(lhs.getId()).compareTo(distances.get(rhs.getId()));
        }
    });
    return pointList
}


private double calcDistance(LatLng ll1, LatLng ll2){
    final double lat1 = ll1.latitude;
    final double lon1 = ll1.longitude;
    final double lat2 = ll2.latitude;
    final double lon2 = ll2.longitude;
    final double lat = lat2-lat1;
    final double lon = lon2-lon1;
    final double squareLat = lat*lat;
    final double squareLon = lon*lon;
    final double squareDistance = squareLat+squareLon;
    return squareDistance;
}

calcDistance実際には、2 点間の実際の距離の 2 乗を返します。これは、2 乗を比較すると実際の値を比較した場合と同じ結果が得られると考えたためであり、その平方根を作成する必要がなかったため、はるかに高速でした。

ただし、まだ遅い (リストが長い) ため、プロセスを加速するためのアイデアをいただければ幸いです。並べ替える前に距離を事前に計算するので、各距離を複数回計算することはありませんが、他の改善は考えられません。足りないものはありますか？

4

1 に答える 1

1

複数のスレッド間で物事を分割することができます。たとえば、4 つのスレッドを使用し、最初の 1/4 のポイントについてはスレッド 1 を使用して距離を計算し、2 番目の 1/4 のポイントについてSparseArray#putはスレッド2 を使用して距離を計算します。安全（これに使用しているライブラリはわかりません）-putメソッドをロックする必要がある場合、複数のスレッドに分割すると、プログラムの実行が実際には遅くなる可能性があります。

倍精度浮動小数点計算の代わりに単精度を使用すると、処理が少し速くなります。固定精度 (例: 精度の小数点以下 2 桁) のみを気にする場合は、代わりに固定小数点演算を使用できます。これは基本的に整数演算を使用します。

プログラムの実行内容によっては、それ以上のポイントまでの距離の計算を遅らせることができる場合があります。たとえば、一度に 25 個のポイントをユーザーに表示している場合、最も近い 100 程度のポイントを特定できます。ユーザーが 75 ～ 100 ポイントまでスクロールするまで、次の 100 ポイント程度のポイントの計算を待ちます。いずれにせよ、ユーザーは最初の 25 ポイントのみを気にする可能性があります。その場合、それ以降のポイントの距離を計算する必要はありません。これを行うには、範囲ツリーまたはkd ツリーを使用してポイントにインデックスを付ける必要がありますリスト全体を反復処理することなく、クエリ ポイントに最も近いポイントをすばやく特定できるようにします。ポイントがデータベースにある場合は、代わりに範囲クエリを実行できます。いずれの場合も、ツリー/クエリはマンハッタンの距離 (delta-lat^2 + delta-lon*2 ではなく、delta-lat + delta-lon) に従って最も近いポイントを見つけていることに注意してください。それらのデカルト距離を計算します。

于 2013-05-30T14:31:15.863 に答える