0

我想从已知的位掩码中选择一些随机位。理想情况下，我也想以随机顺序选择这些位，但该任务可以分为稍后选择和改组。

数据的一些附加特征：

  • 位掩码是 64 位长
  • 所选位数为 4、8、16 或 32
  • 通常会设置 40 到 60 位（总是至少一半）
  • 我需要对单个位掩码进行数百万个随机选择（结果用于统计模拟）

这是一个掩码示例和我期望的内容（选择随机 4 位）：

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

在此示例中，我不应该返回位位置 0，因为它已被禁用。

这是该算法的一个已知热点，所以我想尽可能多地利用它的性能（随机选择的测试只需要比我当前的随机选择实现长约 2 倍的时间）。我目前的想法是用位掩码中设置的位位置填充na 中的第一个数字。char positions[64]因此，对于上面的示例，我最终会得到：[1, 2, 3, 4, 5, 6, 8, 9, ...]. 然后开始在0和之间选择随机数n来选择一个随机位位置。每次选择后将位置设置为-1，如果我再次点击-1，则重复随机选择。

这对于选择 4 个数字非常有用，但在选择 32 个数字时会经常重复选择。

另一个想法是创建一个如上所述的位置数组，然后使用 Fisher-Yates 对其进行洗牌并选择第一个n位置。这需要在数组中进行更多写入，并且总是需要生成与设置位一样多的随机数，这对于仅选择 4 位可能是一种过度杀伤。

有没有更快的方法来生成这些数据？我的目标是模拟的准确性，所以实际上我可以在一秒钟内检查多少次随机迭代。

语言真的不重要，但我猜 C 将在这里占主导地位。

4

1 回答 1

1

您不必进行完整的 Fisher-Yates 洗牌。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 回答