0

既知のビットマスクからランダムなビット数を選択したいと思います。理想的には、これらのビットもランダムな順序で選択したいのですが、タスクは後で選択してシャッフルすることに分割できます。

データのいくつかの追加特性:

  • ビットマスクの長さは 64 ビットです
  • 選択されたビットの数は、4、8、16、または 32 のいずれかです
  • 通常、40 ～ 60 ビットが設定されます (常に少なくとも半分)。
  • 1 つのビットマスクに対して何百万ものランダムな選択が必要です (結果は統計シミュレーションに使用されます)

マスクと私が期待するものの例を次に示します(ランダムな4ビットを選択):

mask    0111111011111011111110111111111111111101111111100111101111111111
random4 ....1...........1........1...............1......................
shuffled bit positions: 41, 16, 4, 25

この例では、既に無効になっているため、ビット位置 0 を返すべきではありません。

これはアルゴリズムの既知のホットスポットであるため、可能な限り多くのパフォーマンスを絞り出したいと思います (ランダム選択のテストは、現在のランダム選択の実装よりも ~2 倍長くかかります)。私の現在の考えは、ビットマスクに設定されたビットの位置で最初のn数字を埋めることです。char positions[64]したがって、上記の例では、次のようになります[1, 2, 3, 4, 5, 6, 8, 9, ...]。次に、0との間の乱数の選択を開始nして、ランダムなビット位置を選択します。各選択の後、位置を -1 に設定し、もう一度 -1 をヒットした場合はランダムな選択を繰り返します。

これは 4 つの数字を選択するのに最適ですが、32 の数字を選択すると、あまりにも頻繁に選択が繰り返されます。

もう 1 つのアイデアは、上記のように位置の配列を作成し、Fisher-Yates を使用してそれをシャッフルし、最初のn位置を選択することです。これには、配列へのより多くの書き込みが必要であり、設定されたビットと同じ数の乱数を常に生成する必要があるため、4 ビットのみを選択するのはやり過ぎになる可能性があります。

このデータを生成するより高速な方法はありますか? シミュレーションの精度を目指しているので、1 秒間に何回ランダムな反復をチェックできるかが重要です。

言語はそれほど重要ではありませんが、ここでは C が優勢になると思います。

4

1 に答える 1

1

完全なフィッシャー イェーツ シャッフルを行う必要はありません。最初の値を取得したら、単に停止しますn。部分的にシャッフルされた配列を次のサンプルに再利用することもできます。C99 での例を次に示します。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

// Assumes that the array a contains numbers 0..63 in any order
static void print_random_bits(uint64_t bitmask, int num_bits, int a[64]) {
    for (int i = 0, j = 63; i < num_bits; ++i, --j) {
        int r = rand() % (j + 1);
        int t = a[r];
        if (r != j) {
            a[r] = a[j];
            a[j] = t;
        }
        printf("random bit %2d: %d\n", t, bitmask & (1ULL << t) ? 1 : 0);
    }
}

int main(void) {
    int a[64];

    for (int i = 0; i < 64; ++i) {
        a[i] = i;
    }

    uint64_t bitmask = 0x5555555555555555ULL;

    for (int i = 0; i < 10; ++i) {
        print_random_bits(bitmask, 8, a);
        printf("\n");
    }

    return 0;
}
于 2013-03-25T23:45:40.483 に答える