c++ - 什么样的优化会提高我的表现？

Question

我编写了一个小型 Java 程序，用于对排序算法(合并排序、选择排序)进行基准测试，并显示它们对人-对象(名称、升序)进行排序所需的时间。

此程序的 C++ 版本至少比 java 版本慢 4 倍。有几位开发人员表示，他们通过优化代码在排序方面击败了 Java。 Release模式，/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

不要传递 vector 。不是按值(value)，也不是按引用。通过迭代器:

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)，因此迭代器是随机访问迭代器。