k naechsten punkte zu einem referenzpunkt



  • hi,

    ich moechte folgenden algo optimieren:
    gegeben sind n punkte in 2d mit (xi, yi)

    ich moechte die k naechsten punkte finden, welche die kuerzeste distanz zu einem referenzpunkt (x,y) haben.

    ich hab einen vector sortiert in n log n...gehts noch schneller?

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    #include <limits>
    #include <ctime>
    using namespace std;
    
    class coord {
    public:
    	int x;
    	int y;
    	coord(int x_, int y_): x(x_), y(y_) {}
    };
    
    class distIndex {
    public:
    	float dist;
    	int index;
    	distIndex(float dist_, int index_): dist(dist_), index(index_) {}
    };
    
    class Compare {
    public:
    	bool operator()(const distIndex &lhs, const distIndex &rhs) {
    		return lhs.dist < rhs.dist;
    	}
    };
    
    vector<coord> find_k_nearest_points(vector<coord> points, coord ref, int k) {
    	vector<distIndex> vec;
    	vector<coord> k_nearest;
    
    	for (int i = 0; i < points.size(); i++) {
    		int x = abs(points[i].x - ref.x);
    		int y = abs(points[i].y - ref.y);
    		float dist = sqrt(x * x + y * y);
    		vec.push_back(distIndex(dist, i));
    	}
    
    	sort(vec.begin(), vec.end(), Compare());
    
    	for (int i = 0; i < k; i++) {
    		int index = vec[i].index;
    		k_nearest.push_back(points[index]);
    	}
    
    	return k_nearest;
    }
    
    int main() {
    
    	vector<coord> vec = { { 1, 1 }, { 10, 2 }, { 8, 1 }, { 2, 2 }, { 5, 5 }, { 6, 2 }, { 3, 3 } };
    
    	vector<coord> points = find_k_nearest_points(vec, coord(2, 3), 3);
    	for_each(points.begin(), points.end(), [](coord p) { cout << "x: " << p.x << ", y: " << p.y << endl; });
    
    	return 0;
    }
    

  • Mod

    http://www.cplusplus.com/reference/algorithm/partial_sort/

    Alternative: Merk dir doch nur die k kleinsten Werte, anstatt alle Werte.

    Ansonsten zum Algorithmus: Kommt drauf an ­čÖé . Wenn das eine einmalige Aktion ist, geht's kaum besser (au├čer mit den oben vorgeschlagenen Detailverbesserungen). Wenn du ├Âfters die Funktion auf den gleichen Datensatz los l├Ąsst, dann kann man da was machen, indem man die Daten vorbehandelt.



  • Die Wurzel kannst du weglassen, da du die Distanzen nur vergleichst -> einen Funktionsaufruf pro Wert gespart.

    Ansonsten w├╝rde ich vector<coord> points als const& ├╝bergeben dann sparst du dir die Kopie. ­čÖé

    EDIT:
    Das abs kannst du auch weglassen, da du x und y ja mit sich selbst multiplizierst. Dadurch sind die dann schon positiv -> wieder zwei Funktionsaufrufe pro Wert gespart.

    Au├čerdem w├╝rde ich f├╝r die Vektoren vec und k_nearest schonmal Speicher reservieren, dann sparst du dir den Overhead durch das neu-allokieren:

    vector<distIndex> vec;
    vector<coord> k_nearest;
    
    // vec ist immer genau so gro├č wie points. Alternativ halt k wenn du SeppJs Tipp umsetzt
    vec.reserve(points.size()); 
    
    // k_nearest ist entweder genau k lang, oder so gro├č wie points.size() wenn k gr├Â├čer als dieses ist
    // Damit hast du dann immer die perfekte Speichergr├Â├če reserviert:
    k_nearest.reserve(std::min(k, points.size()));
    

Log in to reply