實現的查找陣列的有限範圍

Question

N個整數的數組我有一個arr[N]，和需要實現的查找陣列針對所有可能的值設置arr可以採取，例如對於數組爲bool arr[N]的最簡單情況，可能有2^N個值。

這可以通過定義N維布爾查找數組來完成。例如，對於N = 4和arr是布爾值，它將是bool lookup[2][2][2][2]。然後lookup可以通過lookup[arr[0]][arr[1]][arr[2]][arr[3]]存儲和檢索arr的任何可能的值。

由於N各不相同，所以寫起來很尷尬，效率也可能很低，所以實際的實現將不得不使用for循環來存儲和檢索。這是一個問題，因爲查找是一個非常常見的操作，並且儘可能快地完成這個練習是整個練習的重點。

有沒有其他的方法來實現這個想法？我會對一個布爾型arr的解決方案感興趣，可能使用某種比特表示法，以及更一般的解決方案，其中arr中的值範圍比2更寬。

Answer 1

對於布爾值，你應該確實使用位：任何可處理的N必須適合N^2條目到內存中，在現代機器上的順序是2^32到2^38，所以無論如何你都不能達到N = 64。

這就是說，你可以用最少的顯著位爲每個陣列條目，簡單地分配2^N值的商店。然後，您的數組的位表示可以簡單地作爲該商店的索引。

事情是這樣的：

uint64_t compressArray(long length, bool* array) { 
    uint64_t result = 0; 
    for(long i = length; i--;) result = (result << 1) | (array[i] ? 1 : 0); 
    return result; 
} 

... 

int* store = malloc(sizeof(*store) * (1 << N)); 
bool* array = ...; 
// Now you can access the ints in store like this: 
store[compressArray(N, array)] = 3; 

Answer 2

如果我理解正確的，你...... 對於布爾類型是不夠的，如果你使用元素的索引中的一維數組來表示你的位。 例如，對於ARR [4]

ar[0] = 0, ar[1] = 0, ar[2] = 0, ar[3] = 0 0000 
ar[0] = 1, ar[1] = 0, ar[2] = 0, ar[3] = 0 0001 
ar[0] = 0, ar[1] = 1, ar[2] = 0, ar[3] = 0 0010 
ar[0] = 1, ar[1] = 1, ar[2] = 0, ar[3] = 0 0011 

等...

對於含有從1至3的值ARR，例如，可以利用每一個值的兩個比特。

Answer 3

以下可能會有所幫助：

所以，從你的例子ValueRange = 2爲bool可以採取2個值; Size = N

#include <cassert> 
#include <cstddef> 

#include <vector> 

template<typename T, int ValueRange, int Size> 
class MultiArray 
{ 
    static_assert(ValueRange > 1, "Need at least 2 or more values"); 
    static_assert(Size > 0, "Size should be strictly positive"); 
public: 
    MultiArray() : values(computeTotalSize()) 
    { 
     assert(!values.empty()); 
    } 

    const T& get(const std::vector<size_t>& indexes) const 
    { 
     return values[computeIndex(indexes)]; 
    } 
    T& get(const std::vector<size_t>& indexes) 
    { 
     return values[computeIndex(indexes)]; 
    } 

    size_t computeIndex(const std::vector<size_t>& indexes) const 
    { 
     assert(indexes.size() == Size); 

     size_t index = 0; 
     size_t mul = 1; 

     for (size_t i = 0; i != Size; ++i) { 
      assert(indexes[i] < ValueRange); 
      index += indexes[i] * mul; 
      mul *= ValueRange; 
     } 
     assert(index < values.size()); 
     return index; 
    } 

    std::vector<size_t> computeIndexes(size_t index) const 
    { 
     assert(index < values.size()); 

     std::vector<size_t> res(Size); 

     size_t mul = values.size(); 
     for (size_t i = Size; i != 0; --i) { 
      mul /= ValueRange; 
      res[i - 1] = index/mul; 
      assert(res[i - 1] < ValueRange); 
      index -= res[i - 1] * mul; 
     } 
     return res; 
    } 

private: 
    size_t computeTotalSize() const 
    { 
     size_t totalSize = 1; 

     for (int i = 0; i != Size; ++i) { 
      totalSize *= ValueRange; 
     } 
     return totalSize; 
    } 

private: 
    std::vector<T> values; 
}; 

因此，使用這樣的：

int main() 
{ 
    MultiArray<int, 2, 4> m; 

    m.get({0, 0, 1, 0}) = 42; 
    m.get({1, 1, 0, 0}) = 42; 

    // Just for test purpose: 
    for (size_t i = 0; i != 16; ++i) { 
     assert(m.computeIndex(m.computeIndexes(i)) == i); 
    } 
    return 0; 
}