C++ -嵌套的循环优化

Question

问题

我有一些代码，我需要为工作优化。给定两个数据集，我需要比较一个数据集中的每个元素和另一个数据集中的每个元素。数据集中的元素是字符串向量。如下所示：{"AB", "BB", "AB", "AA", "AB", ...}，其中有3个可能的值：AB、BB和AA。例如，一个数据集应该是这样的：

AB AA BB BB AA AB
AB AA AA AA BB AB
AA AA AB BB BB BB

而另一个数据集可能是

BB AB AB AA AB AB
AA AA BB BB BB BB

注:向量长度在数据集中和数据集之间是相同的。在这种情况下，它的长度是6。

因此，第一个数据集包含三个向量，第二个数据集包含两个，用于总共6个比较。

这个例子包含3vs2向量。我真正的问题是130万对6000

可复制示例

下面的代码将为数据集创建所需大小的向量，类似于它们在实际代码中的显示方式。主函数的第一部分只生成数据集。这部分不需要优化，因为这些部分将从文件中读取。为了这个问题，我在这里生成了它们。需要优化的部分是主函数后面的嵌套for循环。

#include <chrono>
#include <iostream>
#include <vector>

// Takes in a 2D string vector by reference, and fills it to the required size with AA, AB, or BB
void make_genotype_data(int numRows, int numCols, std::vector<std::vector<std::string>>& geno) {
  std::string vals[3] = {"AA", "AB", "BB"};
  for (int i = 0; i < numRows; i++) {
    std::vector<std::string> markers;
    for (int j = 0; j < numCols; j++) {
      int randIndex = rand() % 3;
      markers.push_back(vals[randIndex]);
    }
    geno.push_back(markers);
    markers.clear();
  }
}


int main(int argc, char **argv) {
  // Timing Calculation
  using timepoint = std::chrono::time_point<std::chrono::high_resolution_clock>;
  auto print_exec_time = [](timepoint start, timepoint stop) {
    auto duration_us = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    auto duration_ms = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
    auto duration_s = std::chrono::duration_cast<std::chrono::seconds>(stop - start);

    std::cout << duration_s.count() << " s\n";
  };




  // Create the data
  auto start = std::chrono::high_resolution_clock::now();

  int numMarkers = 100;
  std::vector<std::vector<std::string>> old_genotypes;
  std::vector<std::vector<std::string>> new_genotypes;
  make_genotype_data(50, numMarkers, old_genotypes);
  make_genotype_data(6000, numMarkers, new_genotypes);

  auto stop = std::chrono::high_resolution_clock::now();
  std::cout << "*****************" << std::endl;
  std::cout << "Total time for creating data" << std::endl;
  print_exec_time(start, stop);
  std::cout << "*****************" << std::endl;

  int nCols = old_genotypes[0].size();
  float threshold = 0.8;




  // Compare old_genotypes with new_genotypes
  start = std::chrono::high_resolution_clock::now();

  for (int i = 0; i < old_genotypes.size()-1; i++) {
    auto og = old_genotypes[i];
    for (int j = 0; j < new_genotypes.size()-1; j++) {
      auto ng = new_genotypes[j];
      int numComparisons = 0;
      int numMatches = 0;
      for (int i = 1; i < nCols; i++) {
        if (ng[i] != "--" && og[i] != "--") {
          if (ng[i] == og[i]) {
            numMatches++;
          }
          numComparisons++;
        }
      }
      float similarity = (float) numMatches / numComparisons;
      if (similarity >= threshold) {
        std::cout << i << " from old_genotypes and " << j << " from new_genotypes have high similarity: " << similarity << std::endl;
      }
    }
  }

  stop = std::chrono::high_resolution_clock::now();
  std::cout << "*****************" << std::endl;
  std::cout << "Total time for comparison" << std::endl;
  print_exec_time(start, stop);
  std::cout << "*****************" << std::endl;
}

6,000比5,000只需要4分钟。因此，对于6000人和130万人，大约需要17个小时。太慢了。我不知道我能做些什么来提高嵌套for循环的速度。我对C++有点陌生，所以我不知道太多的错综复杂之处，但我可以跟着行话。

我非常感谢一些指点(双关意:D)来帮助我优化这一点。我愿意尝试并行化，方法是将其中一个数据集分解成块，并将每个块输入一个核心，以与第二个数据集进行比较(尽管不知道如何在C++中并行化)。但是，我只想在尽可能地使用序列化版本之后探索并行化(无论如何，它将有助于并行化版本)。

Answer 1

将第一个列表中的每个元素与第二个列表中的每个元素进行比较，可以进行n^2比较。通过对两个列表进行排序(对每个列表进行n个log n比较)，可以获得更快的速度(除了退化列表)，然后在列表中遍历两个计数器，比较两个计数器的内容--如果匹配，则将计数器添加到每个列表中的第一个不同元素，并记录您刚刚找到的匹配集；如果列表1中的元素少于列表2中的元素，那么增量计数器1(因为它们是排序的，列表1中的元素必须是；如果列表1中的元素大于列表2中的元素，增量计数器2；一旦一个计数器超出了其列表的末尾，您就完成了。这样每次进行一次比较和递增一个计数器，但在必须到达列表末尾之前最多可以增加n次计数器，除了“记录刚才找到的匹配集”之外，线性时间也是如此，如果这是一组退化的列表，而这两个列表中的大多数列表是相同的，则可能是一个很大的集合。但是，即使在最坏的情况下，它也只是返回到当前算法的相同的n^2行为。