1

オプションで offset からktha のすべてのビットをクリアする最速の方法は何ですか?boost::dynamic_bitsetj

現在、私はこれをやっていますが、これはかなり遅いです(疑似コード):

for (i = j; i < bitset.size(); i += k) {
    bitset[i] = 0;
}

何百万ものビットクリアを実行する必要があるため、高速な方法を探しています。

4

2 に答える 2

1

わかりました、これがより速いかどうかはわかりませんが、テストできると思います：

重要な操作は、マスク ビット セットの構築です。事前に構築されたマスクのテーブルが必要です (これにより、k1 ビットごとに 32 ビットごとにリセットできます [私のプラットフォームunsigned longでは 32 ビットです])。&次に、高価な操作は、入力と同じサイズの完全なマスクを構築します-常に同じサイズであり、メモリが制約ではない場合、これに対してもルックアップテーブルを構築するだけで、2つを単純に作成できますビットセット。

#include <iostream>
#include <limits>
#include <boost/dynamic_bitset.hpp>

using namespace std;

int main(void)
{
  boost::dynamic_bitset<> orig(64);
  for (int i = 0; i < orig.size(); ++i) {
    orig[i] = rand() % 2;
  }

  std::cout << orig << std::endl;

  unsigned long mask = 0x88888888; // reset every 4th bit
  boost::dynamic_bitset<> mbits(numeric_limits<unsigned long>::digits, mask);

  while(mbits.size() < orig.size())
    mbits.append(mask);
  mbits.resize(orig.size()); // incase not aligned
  mbits <<= 5; // arbitary starting point (i.e. j)
  std::cout << mbits << std::endl;

  mbits.flip();

  std::cout << mbits << std::endl;

  orig &= mbits;

  std::cout << orig << std::endl;

  return 0;
}

更新: わかりました、非常に大まかにテストしたところ、ここで結果を見ることができます: http://www.ideone.com/ez3Oc、事前に構築されたマスクを使用すると、ほぼ +40% 速くなる可能性があります...

于 2011-04-13T14:40:23.523 に答える
0

非常に大きなビットセットの場合、Nim が提案したように n ビット長のマスク (n はネイティブ サイズ、たとえば x86_64 の場合は 64) を計算し、それを適用します。
ネイティブの長さが k の倍数でない場合は、それに応じてシフトします。
したがって、ネイティブ長が 10 で、30 ビット長のビットセットの 3 ビットごとにのみ設定する場合は、次のような 3 つのパスが必要 に なり
ます
。、各マスクを適用した後、左に (n%k) ビットシフトする必要があります。

完了するまで繰り返します。

于 2011-04-13T15:36:40.403 に答える