c++ - 为什么尽管具有相同的算法和数据结构，但另一个解决方案的效率却提高了 10 倍？

Question

我在 leetcode 上找到了一段代码，并将其与我的解决方案进行了比较。

问题链接:https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii

Leetcode 解决方案:(16 毫秒和 10.2 MB)

string removeDuplicates1(string s, int k) {
  vector<pair<char, short>> st;
  string res;
  for (auto ch : s) {
    if (st.empty() || st.back().first != ch) st.push_back({ ch, 0 });
    if (++st.back().second == k) st.pop_back();
  }
  for (auto& p : st) res += string(p.second, p.first);
  return res;
}

我的解决方案:(32 毫秒和 132.5 MB)

string removeDuplicates2(string str, int k) {
   if(k == 1)
        return "";
    vector<pair<char, short>> S;
    for(int i=0; i<str.size(); i++) {
        if(!S.empty() && S.back().first == str[i])
            S.back().second++;
        else 
            S.push_back({str[i], 1});
        if(S.back().second == k)
            S.pop_back();
    }
    
    string result = "";
    for(auto& i : S) {
        result = result + string(i.second, i.first);
    }
    return result;
}

Leetcode执行结果:

为什么 removeDuplicates1 比 removeDuplicates2 更快且内存效率更高？

Answer 1

将@Johannes Schaub 的评论扩展为答案，问题可能出在此处:

for(auto& i : S) {
    result = result + string(i.second, i.first);
}

for 循环中的表达式表示要执行以下操作:

1. 计算赋值语句的右侧。为此，创建一个全新的字符串，该字符串通过克隆 result 并附加 string(i.second, i.first) 形成。
2. 用这种方式形成的新字符串覆盖result。

换句话说，每次执行此循环时，您都在复制到目前为止创建的整个字符串(可能很大)，然后向其添加更多字符，然后删除旧的字符串并将其替换为新字符串。这会占用大量内存并花费大量时间。

另一方面，考虑解决方案中的循环:

for (auto& p : st) {
    res += string(p.second, p.first);
}

这使用 += 运算符，表示“通过添加 string(p.second, p.first) 来扩展现有字符串 res > 到它的尽头。”这不涉及制作任何拷贝^*，因此它使用更少的内存并花费更少的时间。

一般来说，避免写 lhs = lhs + rhs 而你可以写 lhs += rhs，因为前一个语句会复制而后者不会。

^{* 在内部，字符串可能需要调整其内部缓冲区的大小以获得更多空间来容纳新字符，因此它可能需要复制内容。但是，用于执行此操作的策略会过度分配空间，因此复制所花费的总工作量与序列的最终大小成线性关系。}