通过引用传递到比较器函数（C ++ 11）

Question

我正在尝试加快我的代码的速度（下面是最小的，可重现的示例），并告诉我按引用传递将是比较器函数的一种更有效的方法。那是我第一次听到这个词，所以我查了一下，找到了一些带有示例的网站，但是我不知道何时以及如何使用它。在这种情况下，我将如何使用它？

#include <array>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <random>

using namespace std;

class arrMember {
public:
    int var;
    arrMember(int var) :
        var(var) {}
    arrMember() {};
};

array<int, 1000000> arraySource;

array<arrMember, 1000000> arrayObjects;

bool compare(arrMember(x), arrMember(y)) {
    return (x.var < y.var);
}

void arrayPrint() {
    ofstream output("arrayPrint.txt");
    for (int k = 0; k != arrayObjects.size(); k++) {
        output << arrayObjects[k].var << endl;
    }

    output.close();
}

void sort() {
    int j = 0;
    for (auto i = arraySource.begin(); i != arraySource.end(); i++, j++) {
        arrayObjects[j] = arrMember(arraySource[j]);
    }

    sort(arrayObjects.begin(), arrayObjects.end(), compare);
}

int main(){
    random_device rd{};
    mt19937 engine{ rd() };
    uniform_int_distribution<int> dist{ 0, 9999 };
    for (int x = 0; x < arraySource.size(); ++x){
        arraySource[x] = dist(engine);
    }

    cout << "Executing sort...\n";
    clock_t t1 = clock();
    sort();
    clock_t t2 = clock();
    double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;

    cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";

    arrayPrint();

    return 0;
}

感谢您的帮助。

Answer 1

在您的代码中，将比较器函数定义为

bool compare(arrMember(x), arrMember(y)) {
    return (x.var < y.var);
}

该函数具有通过值传递的arrMember类型的两个参数。这意味着x和y是传递给函数的参数的副本。因此，在对数组进行排序时，每次调用比较器（O（n * logn）次）时，都会创建两个临时对象，将它们进行比较然后销毁。您可以修改函数以通过引用获取参数：

bool compare(arrMember const& x, arrMember const& y) {
    return x.var < y.var;
}

这样，该函数不使用对原始值的引用的副本。这是一个不可修改的const引用。

现在的想法是，这会将临时对象另存为副本，从而节省了运行时间。但是，最好的建议是衡量而不是争论。我对您的代码做了一些修改以同时运行两个版本。

#include <array>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <ctime>
#include <random>

using namespace std;

constexpr size_t N=1000000;

class arrMember {
public:
    int var;
    arrMember(int var) :
        var(var) {}
    arrMember() {};
};

bool compare_by_value(arrMember x, arrMember y) {
    return (x.var < y.var);
}

bool compare_by_reference(arrMember const& x, arrMember const& y) {
    return (x.var < y.var);
}


template<typename C>
void sort(array<arrMember, N>& a, C comp) {
    sort(a.begin(), a.end(), comp);
}

int main(){
    random_device rd{};
    mt19937 engine{ rd() };
    uniform_int_distribution<int> dist{ 0, 9999 };

    array<arrMember, N> a;
    std::generate(a.begin(), a.end(), [&]() {return arrMember{dist(engine)};});

    int tmp=0;
    cout << "Executing sort...\n";
    {
        array<arrMember, N> x = a;
        clock_t t1 = clock();
        sort(x, compare_by_value);
        clock_t t2 = clock();
        double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;
        cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";
        tmp += x.front().var;
    }

    {
        array<arrMember, N> x = a;
        clock_t t1 = clock();
        sort(x, compare_by_reference);
        clock_t t2 = clock();
        double timeDiff = ((double)(t2 - t1)) / CLOCKS_PER_SEC;
        cout << "Sort finished. CPU time was " << timeDiff << " seconds.\n";
        tmp += x.front().var;
    }



    return tmp;
}

Here是输出的示例：

开始

正在执行排序...排序完成。 CPU时间为0.105382秒。排序完成。 CPU时间为0.108179秒。

0

完成

似乎两个版本之间没有区别，那么发生了什么？优化的编译器会将比较器内联到排序算法代码中。为此，将排序路由中的调用替换为函数的主体，并且由于该函数不会修改参数，因此无需创建任何副本来防止修改“已通过”的值。