1

对于 Leetcode 问题 1312，我实现了 pass by value 解决方案，我的测试用例的执行时间在 120ms 以上，对于通过引用传递的相同测试用例，执行时间大幅减少到大约 8ms，如何？以下是两种解决方案：

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

我有一些问题：

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

谢谢你。

4

1 回答 1

6

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

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

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

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

为什么差异如此显着？

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

它只发生在字符串上吗

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

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

可能不是。

复制一个整数需要多少时间？整数通常是 1-8 个字节。它需要大约一条指令。

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

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

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

于 2020-04-09T01:56:26.770 回答