布爾值

我需要實現一個非常大的矩陣的矩陣輕巧，說N×N的標準C.矩陣必須存儲真值表，即布爾值

matrix[i][j] = [true|false]

我知道我可以簡單地使用int矩陣，或者如果使用C99，則爲boolean類型，但正在尋找內存方面最輕量級的解決方案。

這有什麼錯用一個位每單元和，比如存儲位，'無符號long's？ – 2012-02-14 18:07:58

@ nm，這實際上是我迄今爲止實現的解決方案，但我想知道是否有更高效的解決方案（並且非常有趣的答案也隨之而來:)） – 2012-02-14 18:11:55

真值表是否等於1和0 ？它是隨機的嗎？它是稀疏還是密集？典型的N和M有多少？ – osgx 2012-02-14 18:16:03

在內存方面，最簡單的解決方案是保存在一個char 8個布爾：

unsigned char getBit(char byte, unsigned short bit){ 
    assert(bit < 8); 
    return byte&(1<<bit); 
}

然後你就可以節省字節每行中存儲N x 8M矩陣。如果這些字節中有很多是空的，那麼你應該使用稀疏矩陣格式，例如壓縮的備用行。

2012-02-14 18:01:08 Zeta

這是否有助於避免緩存被搗毀？ – 2012-02-14 20:26:14

好吧，如果你要迭代行 - 也許。上面的解決方案對布爾值只使用一位。但是，在計算或操縱矩陣時，應避免使用像getBit這樣的函數，並使用'|，^，＆，〜'和常量位標記直接操作字節爲'0x01'，'0x02'，'0x04'以確保優化。 – Zeta 2012-02-14 20:40:23

謝謝，實際上我發現了一些有用的宏來處理直接在代碼上按位操作，而不使用任何函數...希望它能工作...... :) – 2012-02-15 20:32:33

如果矩陣特別稀疏，您可能需要使用散列實現或列表列表。

此外，如果i或j小於系統可以存儲的最大整數，則可以將布爾位集打包爲一個整數，每個位對應一個索引。然後您可以使用按位操作來訪問或修改它。

2012-02-14 17:58:11 shuttle87

是不是std :: bitset是什麼？

2012-02-14 18:19:47

我現在不使用C++，無論如何感謝參考：） – 2012-02-14 18:40:00

哎呀誤讀標籤抱歉 – 2012-02-14 18:44:42

如果有一個更有效的解決方案

如果你想存儲在單個位超過1個布爾值，你需要使用一些壓縮。

壓縮將只對非隨機數據有效;隨機訪問壓縮數據可能會很慢。

最簡單的一種方法是RLE（獨立壓縮每一行）。更復雜一點的是將數據存儲在稀疏矩陣中（僅當您的0值大於1時，此方法才能壓縮多維數據）。

2012-02-14 18:24:36 osgx

回答