Перевернуть строку? более оптимальный способ
#include<iostream>
#include<string.h>
using namespace std;
int main ()
{
char str[50], temp;
int i, j;
cout << "Enter a string : ";
gets(str);
j = strlen(str) - 1;
for (i = 0; i < j; i++,j--)
{
temp = str[i];
str[i] = str[j];
str[j] = temp;
}
cout << "\nReverse string : " << str;
return 0;
}
Есть ли более оптимальный способ без использования этой функции перевернуть строку? Функция начнет с последней позиции S и продолжит копирование строки в обратном порядке. Вместо использования переменной tmp.
string reverse(string s)
{
string reversed ;
for(int is.length();int i >0;--)
{
reversed +=s[i];
}
return reversed;
}
Я думаю, что в вашем фрагменте не хватает пары символов, но нет, это не лучший метод. Во-первых, вы создаете новую строку, а не переворачиваете ее на месте, так что это больше памяти. Во-вторых, вы добавляете к std::string символы, что (потенциально) означает постоянное изменение размера его внутреннего буфера. В-третьих, количество итераций в первой строке составляет всего половину размера строки, тогда как ваш второй алгоритм должен выполнить ее полностью.
Так что первый эффективнее
почему бы не использовать std::reverse?
эффективность зависит от архитектуры, поэтому однозначного ответа на этот вопрос нет. А на современных системах реверсирование с помощью SIMD, наверное, самый быстрый способ. Но может быть даже быстрее изменить процедуру, которая получает вашу перевернутую строку, чтобы просто перебирать строку в обратном порядке с помощью std::string::rbegin().
Вы в курсе, что strlen тоже O(n) ? Использование класса string (который отслеживает длину в переменной) может дать некоторую эффективность в этом отношении.
Ответы 2
Вы можете использовать std::reverse, чтобы перевернуть строку на месте, со сложностью обмена (последний - первый)/2, что в точности равно сложности первой функции, но чище.
Второй метод имеет накладные расходы на дополнительное распределение, которое, вероятно, в конечном итоге будет медленнее.
Я протестировал два варианта с довольно большими файлами.
std::reverse(ss.begin(), ss.end()); соответствует первому варианту (без копии)ss_r = new std::string(ss.rbegin(), ss.rend()); соответствует второму варианту (копия)
#include <iostream>
#include <fstream>
#include <chrono>
#include <string>
#include <algorithm>
//Just for reading the file
std::string read_file(char * file_name)
{
std::ifstream file(file_name);
std::string ss;
file.seekg(0, std::ios::end);
std::cout << file.tellg() <<std::endl;
ss.resize(file.tellg());
file.seekg(0, std::ios::beg);
file.read(&ss[0], ss.size());
file.close();
return ss;
}
//The real test
int main(int arg, char ** args)
{
std::string ss = read_file(args[1]);
std::string * ss_r=NULL;
std::chrono::time_point<std::chrono::high_resolution_clock> start, end;
start = std::chrono::high_resolution_clock::now();
if (args[2]==std::string("copy"))
{
//Second option
ss_r = new std::string(ss.rbegin(), ss.rend());
}
else
{
//First option
std::reverse(ss.begin(), ss.end());
}
end = std::chrono::high_resolution_clock::now();
int elapsed_nano_seconds = std::chrono::duration_cast<std::chrono::nanoseconds>
(end-start).count();
if (ss_r!=NULL)
{
std::cout<<*ss_r<<std::endl;
}
else
{
std::cout<<ss<<std::endl;
}
std::cout << elapsed_nano_seconds<<std::endl;
}
Тестирование с помощью icpc test.cpp -O3 --std=c++11
a.out Test_file no_copy выполняется за 160 микросекунд
Копия a.out Test_file выполняется за 320 микросекунд
С другой стороны, с первым вариантом вы потеряли исходную строку...
Таким образом, если вы не заботитесь о потере исходной строки, используйте std::reverse, если вы хотите сохранить ее, используйте std::string(ss.rbegin(), ss.rend());
Исходный метод перебирает половину строки и меняет местами каждый символ с символом на другой стороне. Ваш копирует всю строку, поэтому, если предположить, что копирование одного символа вдвое дешевле, чем выполнение свопа, результат будет таким же. Но тогда мы еще не учли все накладные расходы в вашем новом методе, которые происходят за кулисами, такие как выделение новой строки, удаление старой строки и многократное изменение ее размера (хотя это амортизируется O (n)). Оба метода работают за O(n), но второй вряд ли будет быстрее. Но почему бы просто не засечь время и не убедиться в этом самим?