Как я могу оптимизировать этот С++?

Я пытаюсь практиковать С++, решая некоторые старые задачи 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.

Итак, в качестве эталона я создал решение на питоне.

#!/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++ pypy optimization g++
person luke    schedule 02.07.2013    source источник
comment
Вы действительно не должны использовать _ в качестве имени переменной, если не что иное, как стиль, но начало переменных с _ или __ часто имеет особое значение для некоторых компиляторов.   -  person PherricOxide    schedule 03.07.2013
comment
@PherricOxide Идентификаторы, начинающиеся со знака подчеркивания, за которым следует заглавная буква, и идентификаторы, содержащие двойные знаки подчеркивания, зарезервированы для реализации. Это относится ко всем компиляторам.   -  person Captain Obvlious    schedule 03.07.2013
comment
Спасибо, что сказал мне. Я думаю, что я использовал его изначально, потому что я не думал, что он мне нужен, и я думаю, что это просто привычка кодирования на python, где, если есть переменная, которая вам не нужна в цикле for, я обнаружил, что чаще всего просто называю ее _. В любом случае изменение его, похоже, не имеет большого значения для времени.   -  person luke    schedule 03.07.2013
comment
если вы хотите действительно хорошую производительность, отбросьте C++ io и строки...   -  person Karoly Horvath    schedule 03.07.2013
comment
Но разве проблема не требует io-материалов и не связана с манипулированием строками. Как я мог решить это без?   -  person luke    schedule 03.07.2013
comment
старый добрый C, char*, malloc...   -  person Karoly Horvath    schedule 03.07.2013
comment
pypy написан на C++ - Скажите, что? Это не так. Есть несколько кусков C, но в остальном он написан на RPython.   -  person    schedule 03.07.2013

Ответы (3)


arrow_upward
1
arrow_downward

Одним из простых не копирующих/не выделяющих токенизаторов является отвратительный std::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++

person Cubbi    schedule 03.07.2013
comment
ВОТ ЭТО ДА! 1.2 секунд. Это быстро! Я не знал о std::strtok, но он определенно хорошо подходит для этого. Спасибо. Кроме того, я думал, что мой код на C++ и Python делает то же самое, чем они отличаются? - person luke; 03.07.2013
comment
@luke python не печатает дополнительный пробел в конце каждой строки - person Cubbi; 03.07.2013

arrow_upward
1
arrow_downward

Я думаю, что ваш код 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;
}
person Jonesinator    schedule 02.07.2013
comment
При компиляции под g++ -O3 это на самом деле кажется медленнее при запуске time ./reverse < in > /dev/null, так как это занимает около 4,5 секунд. - person luke; 03.07.2013

arrow_upward
-2
arrow_downward

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

#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;
}
person Kevin    schedule 02.07.2013
comment
При попытке скомпилировать ваш код я получаю: `ошибка: ‘ss’ не был объявлен в этой области. - person luke; 03.07.2013
comment
#include ‹sstream› извините за это - person Kevin; 03.07.2013