Wie man die Zeit der Ausführung des Algorithmus reduziert

Question

Ich muss einen Algorithmus, der zwei nächste Punkte auf der Erde finden. Ich habe den Code unten geschrieben und es funktioniert für meine Tests, aber die Zeit der Ausführung ist zu lang. Ich habe versucht, den Code zu ändern, aber es hat nicht geholfen. Vielleicht hat jemand eine Idee, was ich tun soll?

struct Points 
{ 
    std::string key; 
    double latitude; 
    char latSign; 
    double longitude; 
    char longSign; 
}; 

typedef std::pair<std::pair<std::string, std::string>, double> myType; 

double toFraction(short deegres, short minutes) 
{ 
    return (double)deegres + (minutes/60.0); 
} 

double orthodroma(const Points &a, const Points &b) 
{ 
    double radian = M_PI/180; 
    return acos((cos((90 - a.latitude) * radian) * 
       cos((90 - b.latitude) * radian)) + 
       (sin((90 - a.latitude) * radian) * 
       sin((90 - b.latitude) * radian) * 
       cos((a.longitude - b.longitude) * radian))) * 
      (180/M_PI); 
} 

bool sortByLatitude(const Points &a, const Points &b) 
{ 
    return a.latitude > b.latitude; 
} 

myType bruteForce(const std::vector<Points> &vec, int begin, int n) 
{ 
    myType result; 
    double min = 1000000; 
    int _i, _j; 
    if(n > 300) 
    { 
    } 
    for(int i = begin; i < (n + begin) - 1; i++) 
    { 
     for(int j = i + 1; j < n + begin; j++) 
     { 
      double tmp; 
      tmp = orthodroma(vec[i], vec[j]); 
      if(tmp < min) 
      { 
       min = tmp; 
       _i = i; 
       _j = j; 
      } 
     } 
    } 
    result.first.first = vec[_i].key; 
    result.first.second = vec[_j].key; 
    result.second = min; 
    return result; 
} 

myType divideAndConquer(std::vector<Points> &vec, int begin, int n) 
{ 
    if(n <= 3) 
    { 
     return bruteForce(vec, begin, n); 
    } 
    std::sort(vec.begin(), vec.end(), sortByLatitude); 
    int middle = n/2; 
    Points point = vec[middle]; 
    myType left = divideAndConquer(vec, begin, middle); 
    myType right = divideAndConquer(vec, middle, (n - middle)); 
    bool which; 
    double minDist = std::min(left.second, right.second); 
    if(left.second < right.second) 
     which = false; 
    else 
     which = true; 
    std::vector<Points> arr; 
    for(int i = 0; i < n; i++) 
    { 
     if(abs(vec[i].latitude - point.latitude) < minDist) 
     { 
      arr.push_back(vec[i]); 
     } 
    } 
    int size = arr.size(); 
    if(size < 2) 
    { 
     if(which) 
      return right; 
     else 
      return left; 
    } 
    else 
    { 
     myType one = bruteForce(arr, 0, size); 
     if(which) 
     { 
      if(one.second < right.second) 
       return one; 
      else 
       return right; 
     } 
     else 
     { 
      if(one.second < left.second) 
       return one; 
      else 
       return left; 
     } 
    } 
} 

PS. Ich muss dividieren und erobern.

Answer 1

Einige Ideen, dass die Leistung etwas verbessern könnte:

• sortiert das Array nur einmal (vor dem ersten rekursiven Aufruf der Teile und Herrsche-Methode).

• Wenn Sie Punkte in den Vektor arr einfügen, können Sie von der mittleren Position aus beginnen, zuerst vorwärts und dann rückwärts. Der Vorteil ist, dass Sie jede dieser Schleifen brechen können, sobald ein Punkt weit genug vom Mittelpunkt entfernt ist. Da das Array nach dem Breitengrad sortiert ist, ist sichergestellt, dass der Rest der Punkte außerhalb des gewünschten Bereichs liegt.

• Sie können einen zusätzlichen Parameter an die divideAndConquer-Methode übergeben, die den bisher bekannten Mindestabstand darstellt. Dies kann zu kleineren Arrays führen, die schneller zu verarbeiten sind. Momentan kann es sein, dass wir für das linke Sub-Array einen sehr kleinen Abstand haben. Beim Lösen des richtigen Unterarrays haben die rekursiven Aufrufe jedoch derzeit keine Informationen über diese bereits gefundene kleine Entfernung.

Answer 2

auf die nächsten zwei Punkte, die Sie brauchen, um erste Überprüfung Abstand zum nächsten Punkt für jeden Punkt zu finden.

Sie sollten einen KD-Baum für Fast Nearest Neighbor Lookups verwenden. Sie können eine vergleichbare Entfernung verwenden, um eine Operation sqrt() zu speichern.

Dies ist ein großer kd tree library