0

I'm working on a the Hamming weight for a vector and what I do is count in linear way all the 1 in the vector, is there any more efficient way?

int HammingWeight(vector<int> a){
    int HG=0;

    for(int i=0; i<a.size(); i++){
        if(a[i] == 1)
            HG++;
    }
    return HG;
}
4

1 回答 1

1

要计算汉明权重，您需要访问每个元素，为您提供 O(n) 最佳情况，使您的循环在忽略微优化时尽可能高效。

但是，您的函数调用本身效率极低：您按值传递向量，从而生成其所有内容的副本。这个副本很容易比功能的其余部分组合起来更昂贵。此外，您的函数中根本没有任何东西实际上需要该副本。因此，将签名更改为int HammingWeight(const std::vector<int>& a)应该会使您的功能更加高效。

另一个（可能的）优化浮现在脑海中，假设你vector只包含一个和零（否则我看不出你的代码是如何有意义的）。在这种情况下，您只需将相应的向量元素添加到HG，摆脱if（添加通常比分支快得多）：

 for(size_t i=0; i<a.size(); ++i)
    HG+=a[i];

我认为这可能会更快，但是它是否真的是取决于编译器如何优化。

如果您确实需要，当然可以应用常见的微优化（循环展开、矢量化等），但除非您有充分的理由这样做，否则为时过早。此外，在这种情况下，要做的第一件事（再次假设向量只包含零和一）将使用更紧凑（读取效率）的数据表示。

另请注意，两种方法（直接求和和 if 版本）也可以使用标准库表示：

  • int HG=std::count(a.begin(), a.end(), 1);与您的代码基本相同
  • int HG=std::accumulate(a.begin(), a.end(), 0);相当于我上面提到的循环

现在这不太可能有助于提高性能，但是使用更少的代码来实现相同的效果通常被认为是一件好事。

于 2013-05-25T11:23:54.673 回答