從緊湊INT選擇一個隨機元素陣列

Question

我創建一個數據結構來緊湊地表示小的整數的數組：

/* 
* Compactly represents an array of N unsigned integers, where each one only 
* requires B bits to store. 
*/ 
template<uint32_t N, uint8_t B> 
class __attribute__((packed)) small_int_array { 
private: 
    static const uint32_t items_per_page = 64/B; 
    static const uint32_t num_pages = (N + items_per_page - 1)/items_per_page; 
    static const uint64_t mask_unit = (1UL << B) - 1; 

    struct helper_t { 
    uint32_t page; 
    uint8_t offset; 

    helper_t(uint32_t index) : page(index/items_per_page), 
     offset(index%items_per_page) {} 
    }; 

    uint64_t _pages[num_pages]; 

public: 
    small_int_array() { memset(this, 0, sizeof(this)); } 

    uint8_t get(uint32_t index) const { 
    helper_t helper(index); 
    uint8_t shift = B*helper.offset; 
    return (_pages[helper.page] & (mask_unit << shift)) >> shift; 
    } 

    void set(uint32_t index, uint8_t value) { 
    helper_t helper(index); 
    uint8_t shift = B*helper.offset; 
    _pages[helper.page] &= ~0UL - (mask_unit << shift); 
    _pages[helper.page] |= ((uint64_t)value) << shift; 
    } 
}; 

我然後實現這個特殊的方法：

/* 
    * Returns a uniformly random index such that get(index)==value. 
    * Returns -1 if no such index exists. 
    */ 
    int32_t get_random_index(uint8_t value) const { 
    int32_t candidates[N]; 
    int size=0; 
    uint32_t index = 0; 
    for (int i=0; i<num_pages; ++i) { 
     uint64_t page = _pages[i]; 
     for (int j=0; j<items_per_page; ++j) { 
     candidates[size] = index++; 
     if (index==N) break; 
     bool match = (page & mask_unit) == value; 
     size += match ? 1 : 0; 
     page = page >> B; 
     } 
    } 
    if (size==0) return -1; 
    return candidates[rand() % size]; 
    } 

此做什麼我想，但我想知道是否有更有效的實現使用位技巧來代替第二個for循環。只要尺寸不增加，我可以改變對象的位表示。

我使用N〜= 100和B = < 4。

Answer 1

我沒有看到很多避免內循環的選項。這對我來說非常重要：您必須檢查「頁面」中的每個值是否與參數值匹配。需要一個循環。對我來說似乎很重要。

我看到避免了顯式循環的唯一方法是編寫一個毛茸茸的專業功能，本質上，生成頁面的每個值一個明確的編譯時檢查。這是可能的，因爲你已經制定了items_per_page。將其轉換爲std::index_sequence以獲取所有索引，並將它們傳遞給可變函數，該函數將「頁面」中的每個項目與value進行手動比較。

從技術上講，這將避免一個明確的內部循環，但我懷疑它會有很大的不同。