0

ここですでに回答されている同様の質問に関係なく、次のことを知りたいです。

  • 与えられた2 のハミング距離と同じ hammingweightでランダムな64 ビットネイバーを計算する最速の方法は何ですか?

私は次のやや素朴な実装を思いつきました。Core i7 マシンで MSVC を使用している場合、どうすれば (はるかに) うまくいくでしょうか?

  • 例：

で呼び出される randomNeighbor

00000000000000000000000000000000010111101011110011000111010111

たとえば、

00000000000000000000000000000000010111101011110011001110010111

つまり、ハミング距離は 2 です。

int msb = 36;  // msb
int hw = 19;   // hammingweight

long long randomNeighbor(long long number) {
    long long neighbor = number;

    int setBitCnt = 0;
    int unsetBitCnt = 0;

    int setBitNr = rnd(hw - 1);
    int unsetBitNr = rnd(msb - hw - 1);

    bool setBit = true;
    bool unsetBit = true;

    for (int x = 0; setBit && unsetBit && x < msb; x++)
    {
        if (_bittest64(&neighbor, x))
        {
            if (setBitCnt == setBitNr)
            {
                _bittestandreset64(&neighbor, x);
            }
            setBitCnt++;
        }
        else
        {
            if (unsetBitCnt == unsetBitNr)
            {
                _bittestandset64(&neighbor, x);
            }
            unsetBitCnt++;
        }
    }
    return neighbor;
}
4

2 に答える 2

0

可能性のある近隣が多数ある「中間」のケースで思いつく最速の方法は次のとおりです。

  1. x開始値を割り当てるo
  2. xランダムな量を回転させるr1
  3. 設定されている最下位ビットをリセットするx
  4. xランダムな量を回転させるr2
  5. 最下位クリア ビットを設定します。x
  6. x他のr1+r2場所を回転させる
  7. xとの間のハミング距離を測定しoます ( のビットを数えますx xor o)。必要な距離に達していない場合は、2 に戻ります。

良い面としては、「多くの」場合、これはかなり高速になるはずです。すべてのステップは、新しく追加されたビット操作命令の 1 つの命令に非常に密接にマップされますx = (x | (x+1))。(ちなみに、ARM プロセッサでこれを行うと、おそらくステップごとに 1 つの命令に非常に近くなります...)

ただし、いくつかの重大な欠点があります。

  • これは、ハミングの重みが範囲の中間にある数値に対してのみうまく機能します。元のハミング重みが約 32 で、「エッジ」に近い場合 (たとえば、0 ～ 8 のセット ビットと 56 ～ 64 のセット ビット) に「最適」に機能し、有効な候補を見つけるのに苦労する可能性があります...そして、最果てで、候補にたどり着くことができずに、候補を見つけようとして離れていきます。
  • いくつかの数について見つける近隣の分布は、複雑に歪んでいます。一連の 1 の最初のものを「クリア」し、一連の 0 の最初のものを「設定」する傾向があります。

可能性のある各隣人を生成する均一な可能性が必要な場合、またはほとんどのビットが設定またはクリアされた数値で操作している場合、まだいくつかの方法が思い浮かびますが、「平均」でこれほど高速になる可能性は低いです。 ' 場合。

于 2016-07-14T16:12:35.110 に答える