C++ Palindrome finderの最適化

Question

私はC++でpalindrome finderを書いていますが、私はこれを書くのに成功しました。

私は単にプログラムのrunspeedを増やしていますが、今は私が持っている機能を使って1,500ワードの単語リストにpalindromes/2 word palindromesのテストを実行するのに約1m 5秒かかっています。私ははるかに大きなファイルで実行しようとするが、私はさらに最適化することができないのを見逃したいのですが？

ご了承ください。これは学校のためだけではなく、レジャーのためだけのものです。

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

これは真ん中にして、文字列の末尾から真ん中に文字列の先頭から反復処理し、それが行くように文字を比較します。私は誰が私にこれを見せたのか覚えていないが、私はそれを考えなかった。

編集：Cubbiからanother question about palindromesで学んだ。

Answer 2

私はいくつかのテストを行った。あなたのアプローチでは、Test2は長い時間がかかります。

データ：2000ランダム20文字の文字列。

解決策：2500 ms。 セスカーネギーズ：500 ms。

私はあなたが2で乗算しなければならないと信じていますが、v + s isntの間にs + vが回文になる可能性があるためです。

アイデア：単語があるとします。 abcd。他の言葉は、この場合、 cbaとdcbaだけで、palyndromesすることができます。存在するものがあるかどうか確認します。

...  
#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()); 
} 

時間：15msの