Оптимизация поиска C ++ Palindrome

Question

Я писал искатель палиндрома на C ++, и мне удалось написать тот, который .... базовый, если не сказать больше.

Я просто стремлюсь увеличить скорость выполнения программы, вернотеперь требуется около 1m 5s, чтобы запустить тест для палиндромов / палиндромов из 2 слов в списке из 1500 слов с использованием имеющихся у меня функций.Я хотел бы попробовать запустить его на гораздо большем файле, но не вижу, где я могу оптимизировать дальше?

Любая помощь будет признательна: PS Это не для школы, просто для отдыха.

#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

bool isPal(string);

int main() {

vector<string> sVec;
vector<string> sWords;
vector<string> sTwoWords1;
vector<string> sTwoWords2;
char myfile[256]="/home/Damien/Test.txt";
ifstream fin;
string str;
fin.open(myfile);
    if(!fin){ 
        cout << "fin failed";
        return 0;
    }
while(fin){

    fin >> str;
    sWords.push_back(str);
    if(!fin){
        break;
    }
    if(isPal(str)){
      sVec.push_back(str);
    }
    else{
        getline(fin, str);
    }
}
    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){
        cout << sVec[i] << " is a Palindrome " <<endl;
    }

    // Test 2
    for(int i=0; i<sWords.size(); i++){
        for(int j=(i+1); j<sWords.size(); j++){
            str = sWords[i]+sWords[j]; 
            if(isPal(str)){
                sTwoWords1.push_back(sWords[i]);
                sTwoWords2.push_back(sWords[j]);
            }
        }
    }
fin.close();
for(int i=0; i<sTwoWords1.size(); i++){
    cout << sTwoWords1[i] << " and " << sTwoWords2[i] << " are palindromic. \n";
}
return 0;
}


bool isPal(string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

Answer 1

Вы делаете много ненужной работы, чтобы проверить, является ли это палиндромом.Просто используйте std::equal:

#include <algorithm>

bool isPal(const string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

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

Редактировать: я узнал об этом от Кубби в еще один вопрос о палиндромах .

Answer 2

Итак, я провел некоторое тестирование. В вашем подходе Test2 занимает много времени.

Данные: 2000 случайных строк из 20 символов.

Ваше решение: 2500 мс. Сет Карнеги: 500 мс.

Хотя я считаю, что вы должны умножить их на 2, потому что s + v может быть палиндромом, а v + s - нет.

Идея: предположим, у нас есть слово ABCD. Другими словами тогда могут быть палиндромы с этим: только cba и dcba. Давайте проверим, есть ли у нас те, кто присутствует.

...    
#include <set>
using namespace std;

bool isPal(const string&);

int main() {
    ...
    set<string> rWords;
    ...
    while(fin){

        fin >> str;

        sWords.push_back(str);

        if(!fin){
            break;
        }
        reverse(str.begin(), str.end());//add reversed str to rWords
        rWords.insert(str);
        reverse(str.begin(), str.end());

        ...
    }

    ...

    // Test 2
    for(int i = 0; i<sWords.size(); ++i)
        for(int l = 0; l<sWords[i].length(); ++l)
            if(isPal(sWords[i].substr(sWords[i].length()-l)))
            {
                string s = sWords[i].substr(0,sWords[i].length()-l);
                set<string>::iterator it = rWords.find(sWords[i].substr(0,sWords[i].length()-l));
                if(it != rWords.end())
                {
                    string s = *it;
                    reverse(s.begin(), s.end());
                    if(s == sWords[i])//isPoly to itself
                        continue;
                    sTwoWords1.push_back(sWords[i]);
                    sTwoWords2.push_back(s);
                }
            }
    ...
    return 0;
}

bool isPal(const string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

время: 15мс