C++ Palindrome Finder優化

Question

我一直在用C++編寫一個迴文搜索器，並且我成功地編寫了一個....至少可以說是基本的。

我正在尋找簡單地增加程序的運行速度，現在需要大約1分5秒的時間，使用我擁有的功能在1500字單詞列表上運行palindromes/2詞迴文測試。我想嘗試在更大的文件上運行它，但未能看到我可以進一步優化的位置？

任何幫助將不勝感激：P.S.這不適用於學校，只是爲了休閒。

#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毫秒。 Seth Carnegie's：500毫秒。

雖然我相信你必須乘以2，因爲s + v可以是迴文，而v + s不是。

想法：假設我們有一個詞 abcd。其他的話可以是與這一個parchndromes是只有 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()); 
} 

時間：15ms的