3

一連の機能のバイナリの有無に基づいてオブジェクトの比較を実行しています。これらの機能は、次のようなビット文字列で表すことができます。

10011

このビット列には、1 つ目、4 つ目、5 つ目の特徴があります。

ビット文字列のペアの類似性を、両方が共通する機能の数として計算しようとしています。ビット文字列の特定のセットについて、それらがすべて同じ長さになることはわかっていますが、コンパイル時にはその長さがどのくらいになるかわかりません。

たとえば、これらの 2 つの文字列には 2 つの共通点があるため、類似度関数で 2 を返すようにします。

s(10011,10010) = 2

C++ でビット文字列を効率的に表現および比較するにはどうすればよいですか?

4

4 に答える 4

10

std::bitsetSTL クラスを使用できます。

これらは、ビット文字列から構築し、AND を取り、1 の数を数えることができます。

#include <string>
#include <bitset>

int main()
{
  std::bitset<5> option1(std::string("10011")), option2(std::string("10010"));
  std::bitset<5> and_bit = option1 & option2; //bitset will have 1s only on common options
  size_t s = and_bit.count ();                //return the number of 1 in the bitfield
  return 0;
}

編集

コンパイル時にビット数が不明な場合は、次を使用できますboost::dynamic_bitset<>。

boost::dynamic_bitset<> option(bit_string);

boost::dynamic_bitset<>と共通のインターフェイスを共有しているため、例の他の部分は変更されませんstd::bitset。

于 2011-01-26T10:55:59.543 に答える
3

より高速なアルゴリズム:

int similarity(unsigned int a, unsigned int b)
{
   unsigned int r = a & b;
   r = ( r & 0x55555555 ) + ((r >> 1) & 0x55555555 );
   r = ( r & 0x33333333 ) + ((r >> 2) & 0x33333333 );
   r = ( r & 0x0f0f0f0f ) + ((r >> 4) & 0x0f0f0f0f );
   r = ( r & 0x00ff00ff ) + ((r >> 8) & 0x00ff00ff );
   r = ( r & 0x0000ffff ) + ((r >>16) & 0x0000ffff );
   return r;
}

int main() {
        unsigned int a = 19 ;//10011
        unsigned int b = 18 ;//10010
        cout << similarity(a,b) << endl; 
        return 0;
}

出力：

2

ideone でのデモンストレーション : http://www.ideone.com/bE4qb

于 2011-01-26T11:15:17.927 に答える
2

コンパイル時のビット長がわからないため、のboost::dynamic_bitset代わりに使用できますstd::bitset。

次に、operator&（または&=）を使用して共通ビットを検索し、を使用してそれらをカウントできますboost::dynamic_bitset::count()。

パフォーマンスは異なります。最高速度を得るには、コンパイラーによっては、@ Nawazのメソッド、またはBit Twiddling Hacksのメソッドを使用するか、sse / popcountなどのアセンブラー/コンパイラー組み込み関数を使用してループを作成するなど、ループを自分で実装する必要があります。

少なくともllvm、gcc、iccはこの種の多くのパターンを検出し、最適化することに注意してください。手動作業を行う前に、生成されたコードをプロファイリング/チェックしてください。

于 2011-01-26T12:45:21.213 に答える
1

機能のstd::bitsetセットが long のビット数よりも少ない場合 (長いと思います) を使用して、ビットの符号なし long 表現を取得し、 2 つの値を取得して、ここからビットをいじるトリックを使用できます。カウントする。

zip_iteratorビット パターンを表すために引き続き文字列を使用する場合は、 from ブーストを使用して、次のようにすることができます。

#include <iostream>
#include <string>
#include <algorithm>

#include <boost/tuple/tuple.hpp>
#include <boost/iterator/zip_iterator.hpp>

struct check_is_set :
  public std::unary_function<const boost::tuple<char const&, char const&>&, bool>
{
  bool operator()(const boost::tuple<char const&, char const&>& t) const
  {
    const char& cv1 = boost::get<0>(t);
    const char& cv2 = boost::get<1>(t);
    return cv1 == char('1') && cv1 == cv2;
  }
};

size_t count_same(std::string const& opt1, std::string const& opt2)
{
  std::string::const_iterator beg1 = opt1.begin();
  std::string::const_iterator beg2 = opt2.begin();

  // need the same number of items for end (this really is daft, you get a runtime
  // error if the sizes are different otherwise!! I think it's a bug in the
  // zip_iterator implementation...)
  size_t end_s = std::min(opt1.size(), opt2.size());
  std::string::const_iterator end1 = opt1.begin() + end_s;
  std::string::const_iterator end2 = opt2.begin() + end_s;

  return std::count_if(
  boost::make_zip_iterator(
    boost::make_tuple(beg1, beg2)
    ),
  boost::make_zip_iterator(
    boost::make_tuple(end1, end2)
    ),
    check_is_set()
  );
}

int main(void)
{
  std::string opt1("1010111");
  std::string opt2("001101");

  std::cout << "same: " << count_same(opt1, opt2) << std::endl;

  return 0;
}
于 2011-01-26T10:55:40.897 に答える