Различия в потреблении памяти при обращении строк

Предположим, я реализую следующие два алгоритма обращения строк:

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&)'

Является ли этот анализ правильным?

1

Решение

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 как временный. Намного лучше.

3

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]