Cpp效率远不如C吗？

发表于   |   分类于   |  

起因是在oj上刷题的时候遇到了奇怪的问题。。。

题目

最长回文

大概意思就是求一个字符串的最长回文子串。一开始想到的就是brute force，从左到右扫一遍所有子串，依次检查是否是回文串。大概复杂度应该是O(n3)。

在网上找到两种算法，一种是动态规划，大概思想就是维护一个二维bool数组，然后(i, j)为true等价于i与j间构成的子串为回文串。

std::tuple<Long, Long, Long> max_str(const string &s)
{
    Long length = s.size();
    vector<bool> temp(length, false);
    vector<vector<bool>> tr(length, temp);
    std::tuple<Long, Long, Long> res;
    Long maxLen = 0;
    for (Long i = 0; i < length; ++i)
    {
        for(Long j = i; j != static_cast<Long>(-1); --j)
        {
            if (s[i] == s[j] && (i - j < 2 || tr[i - 1][j + 1]))
            {
                tr[i][j] = true;
                if (maxLen < i - j + 1)
                {
                    maxLen = i - j + 1;
                    res = make_tuple(maxLen, j, i);
                }
            }
        }
    }
    return res;
}

然后就是Manacher算法。网上随手一搜都有讲解很详细，我就不贴了。我就讲讲我遇到的奇怪的问题。这算法中有一步就是在字符串头尾和中间的空隙中加入原串中不会出现的字符，不改变原串回文性质，并将原串改为奇数长度方便计算。我的实现如下:

string temp = "*#";
for(auto c : s)
    temp = temp + c + "#";

然后交了发现TLE了。一开始并未意识到是这里问题。改了其他地方，检查算法有没写错等等，折腾了半天(好气哦)。后来发现只要把这里改一下就可以了成功AC，效率差了不止5倍。。。

string temp = "*#";
for(auto c : s)
{
    temp += c; 
    temp += '#';
}

乍一看没什么差别。实际上差别大了。在/usr/local/include/c++/6.1.0/bits/basic_string.h中有

template<typename _CharT, typename _Traits, typename _Alloc>
    inline basic_string<_CharT, _Traits, _Alloc>
    operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
    {
      typedef basic_string<_CharT, _Traits, _Alloc>    __string_type;
      typedef typename __string_type::size_type        __size_type;
      __string_type __str(__lhs);
      __str.append(__size_type(1), __rhs);
      return __str;
    }

可以看到，由于重载”+”运算符返回的是右值，每次加都得调用basic_string的拷贝构造函数(由于我传进去的temp是左值)，然后再把右边的字符补到新构造的对象后。

basic_string&
      operator+=(_CharT __c)
      {
    this->push_back(__c);
    return *this;
      }

然而重载”+=”运算符返回的就是左值，每次调用只需要把右边的字符串补到原串后，并不需要调用拷贝构造函数构造新串。两种写法孰优孰劣一目了然。

顺便补充一下，为什么看起来重载”+”运算符时候是两个参数，而重载”+=”运算符时候只是一个参数，难道不都是二元运算符么？其实两个都是两个参数。原因是重载”+”运算符时候，通常把其声明为友元，而重载”+=”运算符时候通常把其声明为成员函数，会把this传进去作为参数。为什么这样，你想一下”+”的时候不仅有可能string + char*, 也有可能char* + string，如果作为成员函数，就内定了必须是string + char*。而”+=”时候显然string是在左边，所以就是成员函数，毕竟总不会搞一个char* += string吧。

关于输入输出

这个问题是EulerLee提出来的，他发现大量输入输出时候用cin、cout会TLE，而用scanf, printf就可以AC。这下又被他这个C++黑找到了把柄(逃。其实他后来查了下发现是C++的输入输出流会与C的输入输出流同步，如果调用std::ios::sync_with_stdio(false);把同步关掉，就非常稳了。

总结

C++设计出来的使命之一就是要不牺牲可以同C相比拟的性能。

– Herb Sutter (并不是沃兹基硕德)

因此在Cpp程序效率出问题时候，多想想底层实现，看是不是因为自己打开方式不对，而不是想当然把锅赖在Cpp头上。