複数のstd :: bitset <N>で1の出現回数を最も速く計算する方法は？

Question

同じ位置にある複数のビットセット内の発生数を1と数えます。各位置のカウントはベクトルに格納されます。

など。

b0 = 1011 
b1 = 1110 
b2 = 0110 
    ---- 
c = 2231 (1+1+0,0+1+1,1+1+1,1+0+0) 

私は以下のコードで簡単にそれを行うことができますが、このコードでは、性能の不足に思えるが、私はよく分かりません。だから私の質問は簡単です：1を数えるより速い方法はありますか？

#include <bitset> 
#include <vector> 
#include <iostream> 
#include <string> 

int main(int argc, char ** argv) 
{ 
    std::vector<std::bitset<4>> bitsets; 
    bitsets.push_back(std::bitset<4>("1011")); 
    bitsets.push_back(std::bitset<4>("1110")); 
    bitsets.push_back(std::bitset<4>("0110")); 

    std::vector<unsigned> counts; 

    for (int i=0,j=4; i<j; ++i) 
    { 
    counts.push_back(0); 
    for (int p=0,q=bitsets.size(); p<q; ++p) 
    { 
     if (bitsets[p][(4-1)-i]) // reverse order 
     { 
     counts[i] += 1; 
     } 
    } 
    } 

    for (auto const & count: counts) 
    { 
     std::cout << count << " "; 
    } 
} 

for (int i=0,j=4; i<j; ++i) 
{ 
    for (int p=0,q=b.size(); p<q; ++p) 
    { 
    if(b[p][i]) 
    { 
     c[p] += 1; 
    } 
    } 
} 

Answer 1

私はあなたのご注文の方法を転記します。

1011    110 
1110 becomes 011 
0110    111 
        100 

2つの主な理由：stlアルゴリズムを使用することができ、より大きなサイズで作業するときにパフォーマンスのためのデータローカリティを持つことができます。ベクター管理から数えロジックを分離する

#include <bitset> 
#include <vector> 
#include <iostream> 
#include <string> 
#include <iterator> 

int main() 
{ 
    std::vector<std::bitset<3>> bitsets_transpose; 
    bitsets_transpose.reserve(4); 
    bitsets_transpose.emplace_back(std::bitset<3>("110")); 
    bitsets_transpose.emplace_back(std::bitset<3>("011")); 
    bitsets_transpose.emplace_back(std::bitset<3>("111")); 
    bitsets_transpose.emplace_back(std::bitset<3>("100")); 

    std::vector<size_t> counts; 
    counts.reserve(4); 
    for (auto &el : bitsets_transpose) { 
     counts.emplace_back(el.count()); // use bitset::count() 
    } 

    // print counts result 
    std::copy(counts.begin(), counts.end(), std::ostream_iterator<size_t>(std::cout, " ")); 
} 

Live code

出力さ

Answer 2

リファクタリングは、計数アルゴリズムの効率を検査するために、私たちを可能にする：

#include <bitset> 
#include <vector> 
#include <iostream> 
#include <string> 
#include <iterator> 

__attribute__((noinline)) 
void count(std::vector<unsigned> counts, 
      const std::vector<std::bitset<4>>& bitsets) 
{ 
    for (int i=0,j=4; i<j; ++i) 
    { 
    for (int p=0,q=bitsets.size(); p<q; ++p) 
    { 
     if (bitsets[p][(4-1)-i]) // reverse order 
     { 
     counts[i] += 1; 
     } 
    } 
    } 
} 

int main(int argc, char ** argv) 
{ 
    std::vector<std::bitset<4>> bitsets; 
    bitsets.push_back(std::bitset<4>("1011")); 
    bitsets.push_back(std::bitset<4>("1110")); 
    bitsets.push_back(std::bitset<4>("0110")); 

    std::vector<unsigned> counts(bitsets.size(), 0); 

    count(counts, bitsets); 

    for (auto const & count: counts) 
    { 
     std::cout << count << " "; 
    } 
} 

-O2と

gcc5.3はこれを得られます。まったく非効率的な私には思えない

count(std::vector<unsigned int, std::allocator<unsigned int> >, std::vector<std::bitset<4ul>, std::allocator<std::bitset<4ul> > > const&): 
     movq (%rsi), %r8 
     xorl %r9d, %r9d 
     movl $3, %r10d 
     movl $1, %r11d 
     movq 8(%rsi), %rcx 
     subq %r8, %rcx 
     shrq $3, %rcx 
.L4: 
     shlx %r10, %r11, %rsi 
     xorl %eax, %eax 
     testl %ecx, %ecx 
     jle  .L6 
.L10: 
     testq %rsi, (%r8,%rax,8) 
     je  .L5 
     movq %r9, %rdx 
     addq (%rdi), %rdx 
     addl $1, (%rdx) 
.L5: 
     addq $1, %rax 
     cmpl %eax, %ecx 
     jg  .L10 
.L6: 
     addq $4, %r9 
     subl $1, %r10d 
     cmpq $16, %r9 
     jne  .L4 
     ret 

。

Answer 3

プログラムに冗長メモリの再割り当てやその他のコードがあります。 たとえば、メソッドpush_backを使用する前に、まずベクトルに十分なメモリを確保できます。

プログラムは次のように見えます。

#include <iostream> 
#include <bitset> 
#include <vector> 

const size_t N = 4; 

int main() 
{ 
    std::vector<std::bitset<N>> bitsets = 
    { 
     std::bitset<N>("1011"), 
     std::bitset<N>("1110"), 
     std::bitset<N>("0110") 
    }; 

    std::vector<unsigned int> counts(N); 

    for (const auto &b : bitsets) 
    { 
     for (size_t i = 0; i < N; i++) counts[i] += b[N - i -1]; 
    } 

    for (unsigned int val : counts) std::cout << val; 
    std::cout << std::endl; 

    return 0; 
} 

その出力は

2231 

Answer 4

テーブル駆動型のアプローチです。これは明らかに*その限界を持っていますが、用途に応じて非常に適して証明することができます：

#include <array> 
#include <bitset> 
#include <string> 
#include <iostream> 
#include <cstdint> 

static const uint32_t expand[] = { 
     0x00000000, 
     0x00000001, 
     0x00000100, 
     0x00000101, 
     0x00010000, 
     0x00010001, 
     0x00010100, 
     0x00010101, 
     0x01000000, 
     0x01000001, 
     0x01000100, 
     0x01000101, 
     0x01010000, 
     0x01010001, 
     0x01010100, 
     0x01010101 
}; 

int main(int argc, char* argv[]) 
{ 
     std::array<std::bitset<4>, 3> bits = { 
      std::bitset<4>("1011"), 
      std::bitset<4>("1110"), 
      std::bitset<4>("0110") 
     }; 

     uint32_t totals = 0; 

     for (auto& x : bits) 
     { 
       totals += expand[x.to_ulong()]; 
     } 

     std::cout << ((totals >> 24) & 0xff) << ((totals >> 16) & 0xff) << ((totals >> 8) & 0xff) << ((totals >> 0) & 0xff) << std:: 
endl; 
     return 0; 
} 

編集:: *実際に、それは1が思っているより少ない限られたのです...