如何減少算法執行的時間

-1

我必須提出一個算法，它可以找到地球上最近的兩個點。我編寫了下面的代碼，它適用於我的測試，但執行時間太長。我試圖修改代碼，但它沒有幫助。也許有人會有一個想法，我該怎麼辦？如何減少算法執行的時間

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。我必須使用分治法。

來源

2017-04-01 wege

請描述你有問題，你用什麼樣的解決方案。 –

你是否在優化模式下編譯代碼？ – jpo38

問題是執行時間。該程序在輸入處獲取數據，並且必須在指定時間內（6.20秒）滿足要求，但我的執行時間約爲7.99秒，我正在尋找解決方案來改進它。 – wege

可能會提高性能一點點的幾點思考：

排序數組只有一次（第一次循環調用之前分而治之的方法）。
向arr向量添加點時，可以從中間位置開始，先向前移動，然後向後移動。好處是，只要一點離中點足夠遠，就可以打破這些循環中的每一個。由於數組按緯度排序，因此可以保證其餘點將超出所需範圍。
您可以將一個附加參數傳遞給divideAndConquer方法，表示迄今已知的最小距離。這可以導致更小的陣列，更快地處理。目前，可能會出現這樣的情況：左子陣列的距離非常短。然而，當解決正確的子數組時，遞歸調用目前沒有關於已經找到的那個小距離的信息。

來源

2017-04-01 13:07:40 qwertyman

要找到最近的兩個點，您需要首先檢查每個點最近點的距離。

您應該使用KD樹進行快速最近鄰居查找。您可以使用可比較的距離來保存sqrt（）操作。

這是一個偉大的kd tree library

來源

2017-04-01 13:29:46 AFX

如何減少算法執行的時間

回答

相關問題