什麼樣的優化會提高我的表現？

Question

我寫了一個基於排序算法（合併排序，選擇排序）的小型java程序，並顯示了排序人員對象（名稱，升序）所需的時間。

該程序的C++版本比java版本慢至少4倍。有幾個開發人員說，他們通過優化代碼來排序Java。釋放模式，/ O2，64位，...。我已經做了這些調整。

我的排序算法（特別是合併排序）有沒有效率低下？

//create a subvector 
template <typename T> std::vector<T> splitVec(std::vector<T> main, size_t from, size_t to) { 

std::vector<T>::const_iterator first = main.begin() + from; 
std::vector<T>::const_iterator last = main.begin() + to; 
std::vector<T> erg(first, last); 

return erg; 
} 

//merge sort - sorting process 
template <typename T> std::vector<T> merge(std::vector<T> m1, std::vector<T> m2) { 

unsigned int posA = 0, posB = 0; 

std::vector<T> erg; 

while (posA < m1.size() && posB < m2.size()) { 
    if (m1.at(posA).compareTo(m2.at(posB)) <= 0) { 
     erg.push_back(m1.at(posA)); 
     posA++; 
    } 
    else { 
     erg.push_back(m2.at(posB)); 
     posB++; 
    } 
} 

while (posA < m1.size()) { 
    erg.push_back(m1.at(posA)); 
    posA++; 
} 

while (posB < m2.size()) { 
    erg.push_back(m2.at(posB)); 
    posB++; 
} 

return erg; 
} 

//merge sort-split up vectors 
template <typename T> std::vector<T> mergeSort(std::vector<T> pers) { 

if (pers.size() > 1) { 

    //Split pers into two equally sized vectors 
    std::vector<T> p1(splitVec(pers, 0, pers.size()/2)); 
    std::vector<T> p2(splitVec(pers, (pers.size()/2), pers.size())); 

    return merge(mergeSort(p1), mergeSort(p2)); 
} 
else 
    return pers; 
} 

由於事先

Answer 1

通過引用傳遞載體中。這應該會顯着提高性能。

在按值傳遞載體複製每次（在每個步驟添加了O（n）的複雜性）

Answer 2

那麼你缺少一個非常大的優化它。您將按值傳遞所有矢量，而不是通過引用。這意味着每個函數調用都是複製非常低效的向量。

因爲java中的所有東西都是一個指針，所以你的java代碼不會使所有這些副本成爲C++代碼減速的主要部分。

Answer 3

通過引用傳遞源數據而不是複製源數據將是一個巨大的改進。

另外，您應該在erg的reserve空間中，否則在添加更多內容時，您會反覆重新分配和複製所有元素。

Answer 4

不要傳遞向量。不按價值，而不是參考。通過迭代器：

template <class Iter> 
void sort(Iter first, Iter last) { 
    ... 
} 

sort(my_vector.begin(), my_vector.end(); 

要分割的範圍，只是計算的中間值：

template <class Iter> 
Iter mid(Iter first, Iter last) { 
    return first + (last - first)/2; 
} 

這假設代碼仍然排序在某種容器中存放的值（原代碼， std::vector），所以迭代器是隨機訪問迭代器。

Answer 5

使用push_back代替索引很慢。對工作數組或向量進行一次性分配，並對該數組進行索引可以避免執行所有這些遞歸分配。使用一對相互遞歸的函數消除了在合併後不得不復制數據。

自底向上合併排序會稍微快一點，而自底向上合併排序通常是大多數庫使用的（如std :: stable_sort），自上而下的合併排序似乎是在教室中教導的內容。

適用於數組或向量的向上合併排序的示例模板（將向量作爲指向第一個元素的指針傳遞）。

template <typename T> 
void TopDownSplitMergeAtoA(T a[], T b[], size_t ll, size_t ee); 
template <typename T> 
void TopDownSplitMergeAtoB(T a[], T b[], size_t ll, size_t ee); 
template <typename T> 
void TopDownMerge(T a[], T b[], size_t ll, size_t rr, size_t ee); 

template <typename T> 
void MergeSort(T a[], size_t n)    // entry function 
{ 
    if(n < 2)        // if size < 2 return 
     return; 
    T *b = new T[n]; 
    TopDownSplitMergeAtoA(a, b, 0, n); 
    delete[] b; 
} 

template <typename T> 
void TopDownSplitMergeAtoA(T a[], T b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1)     // if size == 1 return 
     return; 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoB(a, b, ll, rr); 
    TopDownSplitMergeAtoB(a, b, rr, ee); 
    TopDownMerge(b, a, ll, rr, ee);  // merge b to a 
} 

template <typename T> 
void TopDownSplitMergeAtoB(T a[], T b[], size_t ll, size_t ee) 
{ 
    if((ee - ll) == 1){     // if size == 1 copy a to b 
     b[ll] = a[ll]; 
     return; 
    } 
    size_t rr = (ll + ee)>>1;   // midpoint, start of right half 
    TopDownSplitMergeAtoA(a, b, ll, rr); 
    TopDownSplitMergeAtoA(a, b, rr, ee); 
    TopDownMerge(a, b, ll, rr, ee);  // merge a to b 
} 

template <typename T> 
void TopDownMerge(T a[], T b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;       // b[]  index 
    size_t l = ll;       // a[] left index 
    size_t r = rr;       // a[] right index 
    while(1){        // merge data 
     if(a[l] <= a[r]){     // if a[l] <= a[r] 
      b[o++] = a[l++];    // copy a[l] 
      if(l < rr)      // if not end of left run 
       continue;     //  continue (back to while) 
      while(r < ee)     // else copy rest of right run 
       b[o++] = a[r++]; 
      break;       //  and return 
     } else {       // else a[l] > a[r] 
      b[o++] = a[r++];    // copy a[r] 
      if(r < ee)      // if not end of right run 
       continue;     //  continue (back to while) 
      while(l < rr)     // else copy rest of left run 
       b[o++] = a[l++]; 
      break;       //  and return 
     } 
    } 
}