c++ - 寻找更好的数据排序方法

Question

我有一个算法可以跨 6 个不同的变量参数处理一个文件。该算法在每个参数集上为文件生成真/假结果。我在一组文件中运行这个算法，在一个 vector 中得到结果的真/假(以及一些额外的、不相关的数据)。

该算法运行后，我想计算每个参数集的真实结果数，以及处理的文件数。我现在这样做的方式如下:

while(!results.isEmpty()){ //results being a vector of the individual file results
  for (long i = 0; i < params.size(); i++){ //params being a vector of the parameters
    if (results.first().params... == params[i].params...){
       params[i].numFiles++;
       if (results.first().result){
         params[i].numTrue++;
       }
       results.pop_front();
       break;
    }
  }
}

这完成了工作，但现在我已经优化了我的算法，这是我代码中的最后一个瓶颈，我正在寻找加快速度的方法。快速排序这些数据的最佳方法是什么？如果这是相关的，目前我正在使用 Qt，我的 vector 目前是 QVector。

Answer 1

您的算法复杂度为 O(NxM)，其中 N 是结果的大小，M 是参数的大小。

如果你在这里比较什么:

if (results.first().params... == params[i].params...){

支持 less 运算符，您可以在第一个循环之前对参数进行排序。而不是遍历其所有元素，只需进行二进制搜索。复杂度将是 O(Nxlog(M))。