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

Question

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

问题link：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 循环中的表达式表示要执行以下操作：

计算赋值语句的右侧。为此，通过克隆 result 并附加 string(i.second, i.first).
用这样形成的新字符串覆盖result。

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

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

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

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

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

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

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

Why is the other solution 10 times efficient despite having the same algorithm and data structures?

c++

algorithm

data-structures

stack