Быстрый выбор бит из набора

Я хотел бы выбрать несколько случайных битов из известной битовой маски. В идеале я хотел бы также выбирать эти биты в случайном порядке, но позже задачу можно разделить на выбор и перетасовку.

Некоторые дополнительные характеристики данных:

  • битовая маска имеет длину 64 бита
  • количество выбранных битов равно 4, 8, 16 или 32
  • обычно устанавливается от 40 до 60 бит (всегда не менее половины)
  • Мне нужны миллионы случайных вариантов для одной битовой маски (результаты используются для статистического моделирования)

Вот пример маски и вещей, которые я ожидаю (выбирая случайные 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 номеров.

Другая идея состоит в том, чтобы создать массив позиций, как указано выше, затем перемешать его с помощью Фишера-Йейтса и выбрать первые n позиций. Это требует больше записей в массиве и всегда должно генерировать столько случайных чисел, сколько установлено битов, что может быть излишним для выбора только 4 битов.

Есть ли более быстрые способы генерировать эти данные? Я стремлюсь к точности симуляции, поэтому на самом деле речь идет о том, сколько случайных итераций я могу проверить за секунду.

Язык на самом деле не важен, но я думаю, что C будет доминировать здесь.


optimization montecarlo language-agnostic
person viraptor    schedule 25.03.2013    source источник
comment
Я бы попытался использовать первый, если вам нужна ‹1/2 доступных номеров, и второй в противном случае.   -  person zch    schedule 26.03.2013

Ответы (1)


arrow_upward
1
arrow_downward

Вам не нужно делать полную перетасовку Фишера-Йейтса. Просто остановитесь после получения первых значений 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;
}
person nwellnhof    schedule 25.03.2013