0

ベクトルのハミング重みに取り組んでいますが、ベクトル内のすべての 1 を線形にカウントしています。より効率的な方法はありますか?

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)、関数がより効率的になるはずです。

vector1と 0 のみが含まれていると仮定すると、別の (可能な) 最適化が思い浮かびます(そうでない場合、コードがどのように意味を持つのかわかりません)。その場合、対応する vectorelement を に追加してHG、 を取り除くことができますif(追加は通常、分岐よりもはるかに高速です)。

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

これはおそらく高速であると思いますが、実際に高速であるかどうかは、コンパイラがどのように最適化するかによって異なります。

実際に必要な場合は、もちろん、一般的なマイクロ最適化 (ループ展開、ベクトル化など) を適用できますが、正当な理由がない限り、それは時期尚早です。その場合に加えて、最初に行うことは (ベクトルに 0 と 1 のみが含まれていると仮定して)、データのよりコンパクトな (読み取り効率の高い) 表現を使用することです。

また、両方のアプローチ (直接和と if バージョン) も標準ライブラリを使用して表現できることに注意してください。

  • int HG=std::count(a.begin(), a.end(), 1);基本的にあなたのコードと同じことをします
  • int HG=std::accumulate(a.begin(), a.end(), 0);上記の loopI と同等です

現在、これがパフォーマンスを向上させる可能性は低いですが、より少ないコードを使用して同じ効果を達成することは、通常は良いことと考えられています。

于 2013-05-25T11:23:54.673 に答える