2

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

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

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;}
}

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

谢谢。

4

4 回答 4

4

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

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

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

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

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

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

然后遍历并从这些字符串中去除多余的字符（' ' 和 ')'）。然后对这些数组进行排序，只比较key字段。然后使用std::set_intersection来查找常见的项目。

通过复制和排序键，您将能够利用排序而不影响数据的（重要）现有顺序。通过预先去除多余的字符，您将只对每个键进行一次剥离。通过使用set::intersection，您可以获得具有线性复杂度而不是二次复杂度的常见项目。

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

于 2012-08-04T07:21:29.453 回答
3

1) 如果没有 a) 看到更多您的实际代码，并且 b) 了解您的数据集，我们无法确定任何事情。

2）看起来你没有“添加”任何东西，或者“增长”任何结构。

......但是（这只是一个猜测）......

3) 假设两个数组都已排序：array1 = {1, 2, 3, ... 999}; 数组2 = {1, 3, 4, ... 1001}。

在您的早期迭代中，您将很快遇到“中断”。例如，array1[0] 将在您循环一次之前匹配 array2[0]。

但是，在您以后的迭代中，您必须执行内部循环 100 次或更多次才能找到您要查找的项目。

也许整个问题是 a) 迭代地执行 b) 线性搜索 c) 有序数据集。

再次 - 只是一个猜测。

恕我直言...

于 2012-08-04T05:56:25.047 回答
0

此处速度变慢的唯一原因可能是以数据为中心，如果您的新集合很大，并且包含许多旧集合中不存在的新项目，在这种情况下，将搜索整个新集合以查找旧集合中的每个字符串.

请遵循 Jerry Coffin 的建议，使用清理后的字符串复制您的集合，根据 对它们进行排序string::compare，然后以线性方式遍历它们中的两个，就像std::merge这样做：

1  2  4 5   8  10 11 12 14 17 20 24  ...
1  2  4  6  8  10             20       50 ...

由于您需要更新旧集合中的原始项目，因此在其每个项目的副本中添加另一个字段，携带指向正在复制的原始项目的指针，并在找到重复项时更新它。然后丢弃两个副本。

你的两个系列的尺寸是多少？

于 2012-08-04T08:53:55.517 回答
-1

你是如何衡量表现的？实际上，这种行为可能有很多原因（算法问题、cpu 缓存、编译器设置），但是如果不查看代码使用的源代码和实际字符串数据，就很难回答你的问题......你能展示你的字符串比较算法的实现？

于 2012-08-04T05:50:45.817 回答