c++中的dfs funciton定义

问题来自今日力扣

偶然发现使用std::function定义dfs函数比原生函数或auto定义慢很多，使用斐波那契简单计算一下时间，代码放在最后。

结果如下，可以看到auto和普通定义的递归函数时间开销差不多，而function定义的递归函数慢了快5倍(当然随着计算量增大，倍数会逐渐减小，但还是很慢就是了)。

check fibo(30)
<dfs_ori > ret: 1346269 done!  6425ms
<dfs_func> ret: 1346269 done!  41189ms
<dfs_auto> ret: 1346269 done!  6492ms

gpt给出的解释如下，以后还是投入auto怀抱了~

在C++中，当你使用std::function来包装一个lambda表达式或函数时，可能会发生拷贝构造的情况。这是因为std::function是一个类型安全的函数包装器，可以包含任何可调用对象（函数指针、成员函数指针、函数对象等），因此在构造std::function对象时，会涉及到对象的拷贝构造或移动构造。

在你的情况中，当使用function<int(int,int,int)> dfs = [&](int a, int b, int c)定义dfs时，lambda表达式会被复制到dfs对象中，这可能导致拷贝构造的开销。

而当你使用auto dfs = [&](auto&& dfs, int a, int b, int c)时，使用auto关键字推断函数对象类型，不会引起多余的拷贝构造。这是因为auto将推断出lambda表达式的真实类型，而不是通过std::function进行类型擦除和包装。

因此，如果遇到性能问题，尤其是在递归调用时，使用auto推断类型可能会更有效，因为它可以避免不必要的拷贝构造，提高性能。

code

#include <bits/stdc++.h>
#include <functional>
#include <chrono>
using namespace std;
using namespace chrono;

int dfs_ori(int n){
    if(n <= 1)
        return 1;
    return dfs_ori(n-1) + dfs_ori(n-2);
}

int main(){

    cout << "check fibo(30)" << endl;
    int n = 30;

    // dfs ori
    auto start = steady_clock::now();

    int ret = dfs_ori(n);
    cout << "<dfs_ori > ret: " << ret << " done!  ";

    auto end = steady_clock::now();

    auto last = duration_cast<microseconds>(end - start);

    cout <<  last.count() << "ms" << endl;

    // dfs function
    function<int(int)> dfs_func = [&](int n){
        if(n <= 1)
            return 1;
        return dfs_func(n-1) + dfs_func(n-2);   
    };

    start = steady_clock::now();

    ret = dfs_func(n);
    cout << "<dfs_func> ret: " << ret << " done!  ";

    end = steady_clock::now();

    last = duration_cast<microseconds>(end - start);

    cout <<  last.count() << "ms" << endl;

    // dfs auto
    auto dfs_auto = [&](auto&& dfs_auto, int n) -> int {
        if(n <= 1)
            return 1;
        return dfs_auto(dfs_auto, n-1) + dfs_auto(dfs_auto, n-2);   
    };

    start = steady_clock::now();

    ret = dfs_auto(dfs_auto, n);
    cout << "<dfs_auto> ret: " << ret << " done!  ";

    end = steady_clock::now();

    last = duration_cast<microseconds>(end - start);

    cout <<  last.count() << "ms";

    return 0;
}