字符串逆转内存消耗差异

假设我实现以下两个字符串反转算法：字符串逆转内存消耗差异

void reverse(string &s) { 
    if(s.size() == 1) return; 
    string restOfS = s.substr(1); 
    reverse(restOfS); 
    s = restOfS + s.at(0); 
} 

string reverseString(string s) { 
    if(s.size() == 1) return s; 
    return reverseString(s.substr(1)) + s.at(0); 
} 

int main() { 
    string name = "Dominic Farolino"; 
    reverse(name); 
    cout << name << endl; 
    name = reverseString(name); 
    cout << name << endl; 
    return 0; 
}

其中一个明显的改变给它的字符串，并返回一个新的字符串。由于第一个修改了给定的字符串并且使用了一个引用参数作为它与下一个递归栈帧的通信模式，所以我首先认为这样会更有效率，因为使用引用参数可能会帮助我们不在内存中复制内容，但我不相信是这样。很明显，我们必须在这个void函数中使用参考参数，但似乎我们正在使用参考参数来取消任何内存效率，因为我们只是每次都在栈上声明一个新变量。

总之，似乎第一个在每次调用时复制引用，第二个复制每个调用的值并仅返回结果，使它们具有相同的内存消耗。

为了使第一种更高效的内存我觉得你不得不做这样的事情：

void reverse(string &s) { 
    if(s.size() == 1) return; 
    reverse(s.substr(1)); 
    s = s.substr(1) + s.at(0); 
}

但是编译器不会让我：

error: invalid initialization of non-const reference of type 'std::string& {aka std::basic_string<char>&}' from an rvalue of type 'std::basic_string<char>' 6:6: note: in passing argument 1 of 'void reverse(std::string&)'

这个分析是否正确？

来源

2016-03-06 Dominic Farolino

这不是C.请删除标签。 –

'substr'返回一个副本 - 每种方法都有相同的内存需求。 –

@OliverCharlesworth好的谢谢，这意味着第一个最后一行不可能是（'s = s.substr（1）+ s.at（0）;'），因为原来的's'保持不变？ –

substr()返回一个新的字符串每一次，完成与所有的内存使用。因此，如果您打算拨打substr()N-1，那就是O(N^2)您无缘无故使用的额外内存。

尽管std::string可以修改它，只需通过简单的for循环迭代它即可。或者只是使用std::reverse：

void reverseString(string &s) { 
    std::reverse(s.begin(), s.end()); 
}

无论哪种方式（for循环或算法）需要O(1)额外的内存，而不是 - 它实际上是只是一系列的swap S，所以你只需要一个额外的char作为暂时的。好多了。

来源

2016-03-06 21:19:41 Barry

谢谢，是的，你可以得到的最好的解决方案是一个迭代交换必要的字符，我是只是对理论上的递归实现的确切内存消耗感兴趣，我猜 –

@DomFarolino同样的方法，你会迭代地做...交换一对'char's，然后调用更紧的边界。 – Barry

字符串逆转内存消耗差异

回答

相关问题