C++ 中的执行时间差异（通过引用传递和通过值传递的函数之间）是否显着？

Question

对于 Leetcode 问题 1312，我实现了按值传递解决方案，我的测试用例执行时间超过 120 毫秒，对于相同的测试用例，执行时间大幅减少到大约 8 毫秒，如何？以下是两种解决方案：

120ms + 解决方案/不接受：

 class Solution {
public:
    vector< vector<int> > dp;
    int insert(string s,int l,int r)
    {

        if(dp[l][r]!=-1)
            return dp[l][r];
        else if(l>=r)
            return 0;

        if(s[l]==s[r])
            dp[l][r] = insert(s,l+1,r-1)  ;
        else 
            dp[l][r] = 1 + min(  insert(s,l+1,r), insert(s,l,r-1) ) ;

        return dp[l][r];
    }

    int minInsertions(string s) {
        dp.resize(s.length()+1, vector<int> (s.length()+1,-1) );
        return insert(s,0,s.length()-1);
    }
};

~8ms 解决方案：

   class Solution {
public:
    vector< vector<int> > dp;
    int insert(string& s,int l,int r)
    {

        if(dp[l][r]!=-1)
            return dp[l][r];
        else if(l>=r)
            return 0;

        if(s[l]==s[r])
            dp[l][r] = insert(s,l+1,r-1)  ;
        else 
            dp[l][r] = 1 + min(  insert(s,l+1,r), insert(s,l,r-1) ) ;

        return dp[l][r];
    }

    int minInsertions(string& s) {
        dp.resize(s.length()+1, vector<int> (s.length()+1,-1) );
        return insert(s,0,s.length()-1);
    }
};

我有一些问题：

• 为什么差异如此显着？
• 它是否只发生在字符串上，我的意思是原始/内置数据类型的行为是否相同？
• 通过指针传递会导致与通过引用传递相同的执行吗？
• 另外，根据我对引用变量的理解，它指向同一个地址，只是它有另一个名字，这是正确的吗？

谢谢你。

Answer 1

C++ 中的执行时间差异（通过引用传递和通过值传递的函数之间）是否显着？

它可以是重要的，也可以是微不足道的。这取决于。

我实现了一个按值传递的解决方案，我的一个测试用例的执行时间超过了 120 毫秒，对于一个通过引用传递的相同测试用例，执行时间大大减少到大约 8 毫秒

这个实验的结果非常清楚地证明了时间差异似乎很重要的情况——尽管没有关于测量方差的信息，我们不能确定结果在统计上是显着的。

为什么差异如此显着？

您可以使用探查器找出答案。鉴于将参数更改为引用似乎显着提高了速度，可以合理猜测大部分时间都花在创建参数的多个副本上。

是否只发生在字符串上

它不仅仅发生在字符串上。您会发现还有其他类型的复制速度也很慢。

我的意思是原始/内置数据类型的行为方式相同吗？

可能不是。

复制一个整数需要多长时间？整数通常是 1-8 个字节。它需要一个关于单个指令。

复制一个字符串需要多长时间？一根弦到底有多大？Evensizeof(std::string)不仅仅是系统上最大的整数类型。然后是动态数组，它的大小可能是千兆字节。复制 1 GB 比复制 8 字节需要更多时间。即使字符串不是那么大，它的副本也可能涉及动态分配。动态分配比简单地复制整数慢得多。

通过指针传递会导致与通过引用传递相同的执行吗？

你可以通过测量来了解。但我可以告诉你，是的。