boost :: dynamic_bitesetまたはstd :: bitsetを連結します
https://stackoverflow.com/questions/3061721
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2ビットセットを連結する最良の方法は何ですか？
たとえば、私は持っています
boost::dynamic_bitset<> test1( std::string("1111") );
boost::dynamic_bitset<> test2( std::string("00") );
それらはスリッドビットセットテスト3に連結する必要があります。
111100
ソリューションはboost :: dynamic_bitsetを使用する必要があります。ソリューションがSTD :: Bitsetで動作する場合、それもいいでしょう。ビットを連結するときは、パフォーマンスに焦点を当てる必要があります。
更新：私は両方の方法（私とニールとメッセンジャーからのShiftMethodからのStringMethod）の両方を比較し、StringMethodははるかに高速でした（Factor 10 ++）。ここでコード：http://pastebin.com/hfpfyfy8
パステビンが長いコードリストを投稿しても大丈夫だと思います。より良い方法がある場合は、私に連絡してください。
解決
標準ビットセットの場合、次のようなもの
#include <bitset>
#include <string>
#include <iostream>
using namespace std;
template <size_t N1, size_t N2 >
bitset <N1 + N2> concat( const bitset <N1> & b1, const bitset <N2> & b2 ) {
string s1 = b1.to_string();
string s2 = b2.to_string();
return bitset <N1 + N2>( s1 + s2 );
}
int main() {
bitset <4> a( string("1010") );
bitset <2> b( string("11") );
cout << concat( a, b ) << endl;
}
他のヒント
いくつかのソリューションをテストしましたが、次のようです。
- 古き良き「ループのための」は最速です
- Bitsetは、dynamic_bitesetよりもはるかに高速です（驚くことではありません）。メモリの割り当てが不要な場合、オーバーヘッドは低くなりますが、存在します。
- それは明らかなように思えるかもしれませんが、新しいものを作成せずに別のビットセットを直接追加することはより速いです。このソリューションは、最初のビットセットを変更せずに保持する必要がある場合は適していません（明白）。
- 3つのソリューションは同じ結果を生成しません。必要に応じてチューニングを行う必要があります（以下を参照）。
これが私のテストコードです：
#include <iostream>
#include <bitset>
#include <boost/dynamic_bitset/dynamic_bitset.hpp>
#include "scul/PreciseTimer.h"
boost::dynamic_bitset<> concatOperatorsDyn( const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2)
{
boost::dynamic_bitset<> bs1Copy(bs1);
boost::dynamic_bitset<> bs2Copy(bs2);
size_t totalSize=bs1.size()+bs2.size();
bs1Copy.resize(totalSize);
bs2Copy.resize(totalSize);
bs1Copy<<=bs2.size();
bs1Copy|=bs2Copy;
return bs1Copy;
}
template<size_t sRes,size_t s1,size_t s2>
std::bitset<sRes> concatString( const std::bitset<s1>& bs1,const std::bitset<s2>& bs2)
{
std::string s1=bs1.to_string<char,std::char_traits<char>,std::allocator<char> >();
std::string s2=bs2.to_string<char,std::char_traits<char>,std::allocator<char> >();
std::bitset<sRes> res(s1+s2);
return res;
}
template<size_t sRes,size_t s1,size_t s2>
std::bitset<sRes> concatLoop( const std::bitset<s1>& bs1,const std::bitset<s2>& bs2)
{
std::bitset<sRes> res;
for(size_t i=0;i<s1;i++)
res[i]=bs1[i];
for(size_t i=0;i<s2;i++)
res[i+s1]=bs2[i];
return res;
}
boost::dynamic_bitset<> concatLoopDyn( const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2)
{
boost::dynamic_bitset<> res(bs1);
res.resize(bs1.size()+bs2.size());
size_t bs1Size=bs1.size();
size_t bs2Size=bs2.size();
for(size_t i=0;i<bs2.size();i++)
res[i+bs1Size]=bs2[i];
return res;
}
boost::dynamic_bitset<> concatStringDyn( const boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2)
{
std::string s1;
std::string s2;
to_string(bs1,s1);
to_string(bs2,s2);
boost::dynamic_bitset<> res(s1+s2);
return res;
}
template<size_t s1,size_t s2>
void injectLoop( std::bitset<s1>& bs1,const std::bitset<s2>& bs2,int start=s1-s2)
{
for(size_t i=0;i<s2;i++)
bs1[i+start]=bs2[i];
}
void injectLoopDyn( boost::dynamic_bitset<>& bs1,const boost::dynamic_bitset<>& bs2,int start)
{
for(size_t i=0;i<bs2.size();i++)
bs1[i+start]=bs2[i];
}
void testBitstream()
{
const std::bitset<20> bs1(std::string("11111111110000000000"));
std::bitset<30> bs1Bis(std::string("11111111110000000000"));
const std::bitset<10> bs2(std::string("0000011111"));
std::bitset<30> bs3;
const boost::dynamic_bitset<> bs1D(std::string("11111111110000000000"));
boost::dynamic_bitset<> bs1DBis(std::string("11111111110000000000"));
bs1DBis.resize(30);
const boost::dynamic_bitset<> bs2D(std::string("0000011111"));
boost::dynamic_bitset<> bs3D;
scul::PreciseTimer t;
double d=0.;
int nbIter=100;
std::cout<<"Bitset concat with strings"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
bs3=concatString<30,20,10>(bs1,bs2);
d=t.stop();
std::cout<<bs3.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;;
std::cout<<"Bitset concat with loop"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
bs3=concatLoop<30,20,10>(bs1,bs2);
d=t.stop();
std::cout<<bs3.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
std::cout<<"Bitset inject with loop"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
injectLoop<30,10>(bs1Bis,bs2);
d=t.stop();
std::cout<<bs1Bis.to_string<char,std::char_traits<char>,std::allocator<char> >()<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
std::cout<<"Dynamicbitset concat with loop"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
bs3D=concatLoopDyn(bs1D,bs2D);
d=t.stop();
std::string s;
to_string(bs3D,s);
std::cout<<s<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
std::cout<<"Dynamicbitset inject with loop"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
injectLoopDyn(bs1DBis,bs2D,20);
d=t.stop();
to_string(bs1DBis,s);
std::cout<<s<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
std::cout<<"Dynamicbitset concat with operators"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
bs3D=concatOperatorsDyn(bs1D,bs2D);
d=t.stop();
to_string(bs3D,s);
std::cout<<s<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
std::cout<<"Dynamicbitset concat with strings"<<std::endl;
t.start();
for(int i=0;i<nbIter;++i)
bs3D=concatStringDyn(bs1D,bs2D);
d=t.stop();
to_string(bs3D,s);
std::cout<<s<<std::endl;
std::cout<<"duration="<<d<<std::endl<<std::endl;
}
これが私のコンピューターでVS7.1で得られる出力です：
Bitset concat with strings
111111111100000000000000011111
duration=0.000366713
Bitset concat with loop
000001111111111111110000000000
duration=7.99985e-006
Bitset inject with loop
000001111111111111110000000000
duration=2.87995e-006
Dynamicbitset concat with loop
000001111111111111110000000000
duration=0.000132158
Dynamicbitset inject with loop
000001111111111111110000000000
duration=3.19994e-006
Dynamicbitset concat with operators
111111111100000000000000011111
duration=0.000191676
Dynamicbitset concat with strings
111111111100000000000000011111
duration=0.000404152
ループを使用して書いた関数が異なる結果を生成することに気付くことができます。それは、最初のビットセットのLSBを最初のビットセット（右側のLSB）の後に書いたからです。文字列または「ビット演算子」関数を使用すると、呼び出しパラメーターを切り替える必要があります。
次の2つのアプローチを比較してテストを実行しました。
/* ... */
for( int ii = 0; ii < 1000000; ++ii ) {
std::bitset<16> v1( randomUlongs[ii] );
std::bitset<16> v2( randomUlongs[ii+1] );
#ifdef STRING_TEST
std::bitset<32> v3( v1.to_string() + v2.to_string() );
#else
std::bitset<32> v3( v2.to_ulong() | (v1.to_ulong() << 16) );
/* print out v3 */
}
... どこ randomUlongs それぞれの実行中に一定（ヘッダーの大きな配列）は、汚染の結果を避けるためでした。私はそれをタイミングしました：
~ time for ((ii=0; ii<1000; ii++)); do ./bitset_test >/dev/null; done
Linux（x86_i686）の下 gcc 4.4.6 最適化レベル3：文字列連結は最速で、2倍でした。
Solaris（SPARC）の下 gcc 3.4.3 と Sun Studio C++ 5.12 (2011/11/16), 、両方とも最適化レベル3：非弦のアプローチは10倍で最も速かった。
「最速」ソリューションはコンパイラに大きく依存していると思うでしょうが、プラットフォームも重要な役割を果たす可能性があると思います。
始めるために、自分で可能なソリューションを追加します。次のコードでは、std :: stringでビットセットを構築し、ビットセットからstd :: stringを生成する可能性を使用します。
#include <sstream> // for std::ostringstream
#include <boost/dynamic_bitset.hpp>
boost::dynamic_bitset<> test1( std::string("1111") );
boost::dynamic_bitset<> test2( std::string("00") );
std::ostringstream bitsetConcat;
bitsetConcat << test1 << test2;
boost::dynamic_bitset<> test3( bitsetConcat.str() );
std::cout << test3 << std::endl;
これは機能しますが、他の、よりパフォーマンスのあるソリューションがなければなりません...
アップデート：
JCLeitãoが編集されてくれてありがとう
これが解決策での刺し傷です。コンパイルするかどうかはわかりません。
typedef boost::dynamic_bitset<> Bits;
Bits Concatenate(const Bits& first, const Bits& second)
{
Bits value(first);
//Increase the size of the bit buffer to fit the data being placed in it
value.resize(first.size() + second.size());
value <<= second.size();
value |= second;
return value;
}
所属していません StackOverflow
