尽管具有相同的算法和数据结构，为什么另一个解决方案的效率是 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);
}

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

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

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