2

我正在尝试比较 2 个大向量（整数），即在每个条目中，查看两个向量是否具有相同的元素。我尝试了一些事情，使用迭代器进行比较和简单的 for 循环。两者都有效，但我需要一些可以加快速度的东西，因为我必须比较很多向量。在 C++ 中做到这一点的最佳方法是什么？提前谢谢了！

typedef vector<int> fingerprint;

double aakernel(fingerprint a,fingerprint b, double h){

    double diff = 0;
    vector<int>::iterator dd = a.begin();
    vector<int>::iterator ee = b.begin();

    for(; dd != a.end() && ee != b.end() ;++dd, ++ee){ /*option one*/
        if (*dd!=*ee){
            diff++;
        }

    }


    for (int dd=0;dd<int(a.size());dd++){ /*option two*/
        if (a[dd]!=b[dd]){
            diff++;
        }
    }
    double due = (h/(1-h));
    double q = -log(due)*diff;
    double K = exp(q);
    return (K);
}
4

5 回答 5

3

如果向量在其他方面是任意的，那么您不可能比按顺序比较所有元素更好，就像您现在所做的那样。因此，您剩下的微优化可能会或可能不会提高性能（取决于编译器的优化器如何处理它们）。

我唯一能想到的是将不变的评估排除在循环之外。（也许也不使用++on type double，但我相信编译器无论如何都会以最佳方式处理这个问题）：

double diff = 0;
for (
  auto itA = a.begin(), itB = b.begin(), endA = a.end();
  itA != endA;
  ++itA, ++itB
) {
  if (*itA != *itB) {
    diff += 1.0;
  }
}
于 2013-11-11T08:55:22.247 回答
2

1）您可以通过将其分成几部分并为每个部分使用不同的线程来加快速度。

2）您还可以探索并行处理机器操作码，例如 MMX，看看它们是否适用。

3) 根据您的编译器、它的优化器、CPU 等，您可能会或可能不会从消除分支中发现显着的性能优势：而不是...

if (*dd != *ee){
    diff++;
}

……试试吧……

diff += bool(*dd - *ee);

可能值得先检查if ()版本的汇编语言，看看优化器是否已经这样做了。如果bool(*dd - *ee)仍然有分支，您可以尝试其他一些事情，如有必要，可以使用内联汇编。

4）假设您最终将相同的向量与许多其他向量进行比较，您可以在数据中存储范围的校验和/散列，这样当将相同的向量与不同的替代方案进行比较时，只考虑具有不同散列的区域：这可以错过了一些差异 - 大约 1 in 2 ^bits for a good hash - 但如果这是用于指纹，我认为它无论如何都是概率性的，这将是微不足道的。

5) 如果你是为 NSA 做的，我建议用 VBA 重新编码。

于 2013-11-11T09:41:27.420 回答
1

如果这两个fingerprint值通常相同，如果你先做一个可能会有所帮助

memcmp(&a[0], &b[0], a.size() * sizeof(int))

测试两个数组之间是否有任何区别。只有当有任何差异时，你才会去看看有多少差异。

于 2013-11-11T09:10:54.983 回答
0

非常感谢所有不同的解决方案！非常感激。我将 diff 用作双精度，因为在计算结束时它需要放入内核函数并且来自 Python 背景评论！

另外，为了详细说明指纹（我应该首先做的，我很抱歉），或者 bitstring 可能是一个更好的词，在我的情况下，每个位都包含 1 或 0，我需要在每个索引处比较是否两个位串是否相同。再次感谢您提供的解决方案，我将尝试看看哪一个有助于加快速度！非常感谢你们！

于 2013-11-11T09:31:38.163 回答
0

你不需要自己写，因为 stl 有某些功能可以做到这一点，检查这个

您可以在此处查看更多算法：

http://www.cplusplus.com/reference/algorithm/

于 2013-11-11T08:56:52.623 回答