Реверсировать строку? более оптимальный способ - PullRequest
Новая
       17

Реверсировать строку? более оптимальный способ

2 голосов
/ 15 марта 2019 
#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;
    }

Ответы [ 2 ]

1 голос
/ 15 марта 2019

Вы можете использовать std::reverse, чтобы перевернуть строку на месте, со сложностью (последний - первый) / 2 перестановки, что в точности соответствует сложности первой функции, но чище.

У второго метода накладные расходы на дополнительное распределение, которое, вероятно, будет медленным.

0 голосов
/ 15 марта 2019

Я протестировал два варианта с довольно большими файлами.

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());

...