时间戳

首页 > 解决方案 > 通过引用传递给比较器函数 (C++11)

c++ - 通过引用传递给比较器函数 (C++11)

问题描述

我正在尝试加快我的代码（下面是最小的、可重现的示例），并且有人告诉我，通过引用传递对于我的比较器函数来说是一种更有效的方法。那是我第一次听说这个短语，所以我查了一下，找到了一些有例子的网站，但我不明白何时以及如何使用它。在这种情况下我将如何使用它？

#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;
}

谢谢您的帮助。

标签： c++sortingc++11optimizationpass-by-reference

解决方案

对于非常小的类型，通过引用传递没有帮助；复制构造一个由单个组成的类int与获取现有实例的地址的成本基本相同，复制构造意味着比较器不需要取消引用指针来查找值，它已经在本地堆栈上。

对于具有昂贵复制构造的较大类型，您可以更改（原始代码减去不必要的括号）：

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

至：

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

并收获有意义的加速，但对于一个简单的int包装类，你什么也得不到。

无论问题的大小如何，都会产生影响的是用class仿函数（或 lambda，它们是仿函数的语法糖）替换原始函数。std::sort将模板专门用于比较器的类型，并且函数本身不是类型；它们实际上是共享相同原型的一组函数的实例。因此，如果您同时实现两者：

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

并在程序中的不同点std::sort同时调用，它只对 for 进行一种特化，并且该单一特化实际上必须传递并通过指针调用提供的函数；调用函数的成本明显高于执行比较本身的微不足道的成本，通过指针调用通常更昂贵。comparecompareReversestd::sortbool (*)(const arrMember&, const arrMember&)

相比之下，仿函数（和 lambda）是独特的类型，因此std::sort可以完全专门化它们，包括内联比较，因此不会调用比较器函数；比较器逻辑直接内联到std::sort. 所以而不是：

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

你可以这样做：

struct compare {
    bool operator()(const arrMember& x, const arrMember& y) const {
        return x.var < y.var;
    }
};
std::sort(..., compare());

或将整个内容内联为 C++11 lambda：

std::sort(..., [](const arrMember& x, const arrMember& y) { return x.var < y.var; });

无论哪种方式，代码都会运行得更快；Godbolt 表明，任何一种函数指针方法都几乎相同，而使用函子方法，相对于函数指针方法，您将运行时间减少了大约三分之一（在这种情况下节省了更多的值传递，但几乎不值得麻烦大多数时候想一想；我默认通过const引用传递，并且仅在分析表明它很慢时才考虑切换，并且类型足够简单以至于按值传递可能会有所帮助）。

模板和函子的这种好处是 C++在适当使用时std::sort可靠地击败 C 的原因。qsortC 缺少模板，因此它根本无法专门化qsort，并且必须始终通过函数指针调用比较器。如果std::sort与函数一起使用，qsort它并没有对std::sort. qsort您可以通过复制粘贴实现的代码、摆脱比较器并自己内联比较来在 C 中获得相同的好处，但这很多维护费用；C++ 模板为您完成了 99% 的工作，您只需要记住在回调中使用仿函数/lambda，而不是原始函数。

推荐阅读