草庐IT

C++ 回文查找器优化

coder 2024-02-13 原文

我一直在用 C++ 编写一个回文查找器，并且我已经成功地编写了一个……至少可以说是基本的。

我只是想提高程序的运行速度，现在使用我拥有的功能在 1500 词的单词表上运行回文/2 词回文测试大约需要 1 分钟 5 秒。我想尝试在更大的文件上运行它，但看不到我可以进一步优化的地方？

任何帮助将不胜感激: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());
}

最佳答案

您正在做很多不必要的工作来测试它是否是回文。只需使用 std::equal:

#include <algorithm>

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

这将从字符串的开头迭代到中间，从字符串的结尾迭代到中间，并比较字符。我不记得是谁给我看的，但我没想到。

编辑:我在 another question about palindromes 中从 Cubbi 那里学到了它.

关于C++ 回文查找器优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8511620/

回文amplttestingc++function

有关C++ 回文查找器优化的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  3. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

  7. ruby - 查找重叠的正则表达式匹配项 - 2

    我想找到给定字符串中的所有匹配项，包括重叠匹配项。我怎样才能实现它？#Example"a-b-c-d".???(/\w-\w/)#=>["a-b","b-c","c-d"]expected#Solutionwithoutoverlappedresults"a-b-c-d".scan(/\w-\w/)#=>["a-b","c-d"],but"b-c"ismissing 最佳答案 在积极的前瞻中使用捕获:"a-b-c-d".scan(/(?=(\w-\w))/).flatten#=>["a-b","b-c","c-d"]参见Rubyde

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. ruby - 在 Ruby 中查找多个正则表达式匹配的模式和位置 - 2

    这应该是一个简单的问题，但我找不到任何相关信息。给定一个Ruby中的正则表达式，对于每个匹配项，我需要检索匹配的模式$1、$2，但我还需要匹配位置。我知道=~运算符为我提供了第一个匹配项的位置，而string.scan(/regex/)为我提供了所有匹配模式。如果可能，我需要在同一步骤中获得两个结果。 最佳答案 MatchDatastring.scan(regex)do$1#Patternatfirstposition$2#Patternatsecondposition$~.offset(1)#Startingandendingpo

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐