Оптимизация — Как я могу оптимизировать этот C ++?

Question

Оптимизация — Как я могу оптимизировать этот C ++?

Я пытаюсь попрактиковаться в C ++, выполняя некоторые старые проблемы с Google Code Jam. Я нашел относительно простой способ перевернуть слова в строке. Это можно найти здесь https://code.google.com/codejam/contest/351101/dashboard#s=p1

Пока что у меня есть:

#include<iostream>
using namespace std;

int main(){
int n = 0;
cin >> n;string rev = "";
string buf = "";

string data = "";
getline(cin, data);

for(int _ = 0; _ < n; _++){
getline(cin, data);

rev = "";
buf = "";
for(char& c : data) {
buf += c;
if(c == ' '){
rev = buf + rev;
buf = "";
}
}

cout << "Case #" << _ + 1 << ": " << buf << " " << rev << endl;
}

return 0;
}

Который, кажется, бежит довольно быстро. При беге time ./reverse < in > /dev/null с тестовым файлом около 1.2E6 случаи это занимает около 3.5 секунд при компиляции с g++ -O3,

Таким образом, в качестве ориентира я создал решение в Python

#!/usr/bin/env python
from sys import stdin, stdout
stdout.writelines(map(lambda n: "Case #%d: %s\n" % (n + 1, ' '.join(stdin.readline().split()[::-1])), xrange(int(stdin.readline()))))

Однако, когда я запускаю его под pypy с time pypy reverse.py < in > /dev/null это займет всего около 1.95 секунд.

В теории как pypy написан на C ++, не должен ли C ++ быть таким же быстрым или быстрым, и если да, то как можно оптимизировать этот код, чтобы он был быстрее?

3

c++g++optimization pypy

Решение

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

Я думаю, что ваш код C ++ делает довольно много копий памяти, когда вы объединяете строки (большинство реализаций std :: string сохраняют всю строку непрерывной в памяти.) Я думаю, что следующий код делает это без копий, но я не проверял это много , Что касается того, почему питон работает довольно хорошо, я не совсем уверен.

#include<iostream>

int main()
{
size_t numCases;
std::cin >> numCases;
std::cin.ignore();

for( size_t currentCase = 1; currentCase <= numCases; ++currentCase )
{
std::cout << "Case #" << currentCase << ": ";

std::string line;
getline(std::cin, line);
size_t wordEnd = line.length() - 1;
size_t lastSpace = std::string::npos;
for ( int pos = wordEnd - 1; pos >= 0; --pos )
{
if ( line[pos] == ' ' )
{
for ( int prt = pos + 1; prt <= wordEnd; ++prt )
std::cout << line[prt];
std::cout << ' ';
lastSpace = pos;
wordEnd = pos - 1;
--pos;
}
}
for ( int prt = 0; prt < lastSpace; ++prt )
std::cout << line[prt];

std::cout << std::endl;
}

return 0;
}

1

Вместо того, чтобы использовать два буфера и много конкатенации, вы могли бы использовать алгоритмы и библиотеки итераторов, чтобы сделать все это намного проще. Я не уверен, насколько быстрее это будет (хотя я бы предположил, но довольно), но это также гораздо более компактно.

#include<iostream>
#include<algorithm>
#include<iterator>
#include<sstream>
using namespace std;

int main(){
int n = 0;
cin >> n;
string data = "";
getline(cin, data);
for(int _ = 0; _ < n; _++){
getline(cin, data);
stringstream ss(data);
reverse(istream_iterator<string>(ss), istream_iterator<string>());
cout << "Case #" << _ + 1 << ": " << ss.str() << endl;
}
return 0;
}

-2

Источник

Accepted Answer

Один простой не копирующий / не выделяющий токенизатор — отвратительный станд :: strtok

Следующее превосходит вашу программу на Python в моих тестах

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cstring>

int main()
{
std::cout.sync_with_stdio(false); // we don't need C in the picture

std::string line;
getline(std::cin, line);
int num_cases = stoi(line);

std::vector<char*> words;
for(int n = 0; getline(std::cin, line) && n < num_cases; ++n)
{
words.clear();
char* p = std::strtok(&line[0], " ");
while (p) {
words.push_back(p);
p = std::strtok(nullptr, " ");
}
std::cout << "Case #" << n + 1 << ": ";
reverse_copy(words.begin(), words.end(),
std::ostream_iterator<char*>(std::cout, " "));
std::cout << '\n'; // never std::endl!
}
}

PS: ваши C ++ и Python выходы не совпадают точно; эта программа соответствует вашему выводу C ++

1