c++ - vector<int> C++ 的汉明权重

Question

我正在研究一个 vector 的汉明权重，我所做的是以线性方式计算 vector 中的所有 1，有没有更有效的方法？

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

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

Answer 1

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

然而，您的函数调用本身效率极低:您按值传递 vector ，导致其所有内容的拷贝。这个拷贝很容易比其他功能组合起来更昂贵。此外，您的函数中根本不需要该拷贝。所以将签名更改为 int HammingWeight(const std::vector<int>& a)应该使您的功能更有效率。

想到另一个(可能的)优化，假设您的 vector只包含 1 和 0(否则我看不出你的代码有什么意义)。在那种情况下，您可以将相应的 vector 元素添加到 HG , 摆脱 if (加法通常比分支快得多):

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

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

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

另请注意，这两种方法(直接求和和 if 版本)也可以使用标准库表示:

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

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