c++循环在每次迭代时变慢

Question

在 C++ 中，我使用嵌套的 for 循环来匹配具有相同名称的对象对。我预计该程序需要很长时间才能运行(比较数千个字符串)但是随着它的进行，程序运行得越来越慢。它会在几分钟内比较前 20% 的字符串，但一旦完成大约 30%，就需要将近 60 秒来检查一个字符串与其他字符串。

我的“新数据”包含字段“feas”、“eff”和“numIdeas”的正确值，而我的旧数据与其匹配的"new"合作伙伴共享“数据”字段。新数据和旧数据的顺序不同，我无法对它们进行排序，因为它们当前的顺序很有意义。我认为最好的方法就是“蛮力”通过它。就像我说的，它们没有特定的顺序，所以循环迭代的极度减慢让我感到困惑。据我所知，速度应该保持不变。

for(int i=0; i< newDO.getNumItems(); i++)
{
    Item newItem = newDO.getItem(i);

    for(int k=0; k < oldDO.getNumItems(); k++)
    {
        Item oldItem = oldDO.getItem(k);
        if(oldItem.getType()==1)
        {
            bool same = testStrings(oldItem.getData(), newItem.getData());

            if(same)
            {
               oldItem.setFeas(newItem.getFeas());
               oldItem.setEff(newItem.getEff());
               oldItem.setNumIdeas(newItem.getNumIdeas());
               break;
            }
        }
    }
}

我没有编写此 testStrings 函数，但我没有发现它有任何实际问题。此函数获取字符串(大约 5-20 个字符)并去除所有空格和“(”。

(据我所知，我之前的人导入了数千个文件，然后才意识到解析它们的函数没有从某些数据中正确删除“(”，所以他对此的解决方法是忽略它们在检查字符串是否相等时)。

bool testStrings(string s1, string s2)
{
    string s1def ="";
    for(int i=0; i<s1.length(); i++)
    {
        if(s1[i]!=' ' || s1[i]!=')'){s1def+=s1[i];}
    }
    string s2def = "";
    for(int i=0; i<s2.length(); i++)
    {
        if(s2[i]!=' ' || s2[i]!=')'){s2def+=s2[i];}
    }
    if(s1def == s2def){return true;}
    else{return false;}
}

任何见解都会非常有帮助。

谢谢。

Answer 1

这段代码几乎可以用来演示如何做错所有事情。

正如@jahhaj 已经提到的，您似乎在使用二次算法。

您通过在比较函数中去除额外的字符来复合它，因为这意味着您每次进行比较时都会去除额外的字符，而不是预先一次。

如果我这样做，我会先创建一个结构，例如:

struct index { 
   std::string key;
   size_t subscript;
}

您将通过将要比较的字符串复制到 key 并将该项目的下标复制到 subscript 来初始化它。

然后遍历并从这些字符串中删除多余的字符(' ' 和 ')')。然后对这些数组进行排序，只比较 key 字段。然后使用 std::set_intersection 查找公共(public)项。

通过复制和排序键，您将能够在不影响数据(重要的)现有顺序的情况下利用排序。通过预先去除多余的字符，您只需去除每个键一次。通过使用 set::intersection，您可以得到具有线性复杂度而不是二次复杂度的常见项。

明显的缺点是复制字符串显然会增加您必须存储的数据量。但是，如果项目的数量足够大，足以产生很大差异，那么您也有足够的能力从二次复杂度到线性复杂度将代表巨大时间节省。复制数据是合理的，即使这意味着您必须临时将其他数据写入磁盘。