從一個集合中快速選擇位

Question

我想從已知的位掩碼中選擇一些隨機位。理想情況下，我也想按隨機順序選擇這些比特，但任務可以分成稍後的選擇和洗牌。

數據的一些附加特徵：

• 位掩碼是64位長
• 數選擇的比特的是4，8，16，或32
40之間通常
• 和60位將設置（總是至少一半）
• 我需要數以百萬計的單位掩碼隨機選擇的（結果用於統計模擬）

這裏的面具和東西我期望（隨機選擇4位）的例子：

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

在這個例子中，我不應該回到0位，因爲它已經被禁用。

這是該算法的一個已知熱點，所以我想盡可能地擠出更多的性能（隨機選擇測試只比我目前的隨機選擇實現長2倍）。我目前的想法是填充char positions[64]中的第一個n數字，並在位掩碼中設置位的位置。所以對於上面的例子，我最終會得到：[1, 2, 3, 4, 5, 6, 8, 9, ...]。然後開始選擇0和n之間的隨機數來選擇一個隨機位的位置。每次選擇後，將位置設置爲-1，如果再次輸入-1，則重複隨機選擇。

這對選擇4個數字很好，但在選擇32個數字時經常反覆選擇。

另一個想法是創建一個如上的位置陣列，然後使用Fisher-Yates對其進行洗牌，並選擇第一個位置爲n。這需要在陣列中進行更多的寫操作，並且始終需要生成與設置位一樣多的隨機數，而這些位對於僅選擇4位可能是過度殺傷力。

有沒有更快的方法來產生這些數據？我的目標是模擬的準確性，所以它實際上是我可以在一秒鐘內檢查多少次隨機迭代。

語言並不重要，但我猜C會在這裏占主導地位。

Answer 1

你不必做一個完整的費雪耶茨洗牌。只需在獲得第一個值後即可停止。您甚至可以重新使用部分混洗陣列進行下一個樣本。以下是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; 
}