Предположим, я реализую следующие два алгоритма обращения строк:
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&)'
Является ли этот анализ правильным?
substr()
возвращает новый строка каждый раз, в комплекте со всем использованием памяти, которое идет с этим. Так что если вы собираетесь делать N-1
звонки в substr()
, это O(N^2)
дополнительная память, которую вы используете без причины.
С std::string
тем не менее, вы можете изменить его на месте, просто перебрав его с помощью простого for
петля. Или просто с помощью std::reverse
:
void reverseString(string &s) {
std::reverse(s.begin(), s.end());
}
В любом случае (for
цикл или алгоритм) занимает O(1)
вместо этого дополнительная память — это всего лишь серия swap
с, так что вам просто нужно еще один char
как временный. Намного лучше.
Других решений пока нет …