存儲一個十進制數字

我有一個問題，它涉及大量的小整數（實際上是十進制數字）。什麼是空間有效的方式來存儲這樣的數據？存儲一個十進制數字

使用std::bitset<4>來存儲一位十進制數字是不是個好主意？

2017-07-08 dann

什麼給sizeof給你的bitset？ – 2017-07-08 12:05:24

你所有的號碼都是單個數字嗎？你有多少號碼？你需要通過他們的位置訪問數字嗎？您是否願意爲了空間效率而進行交易？ **顯然，在進行這種優化之前，你必須弄清楚你需要什麼！**在大多數情況下，使用適當的整數或字符類型可能綽綽有餘。 – Phil1970

另外，有沒有可以在數字序列或序列中的一部分中使用的模式？有些數字可能比其他數字更頻繁地發生？如果是這樣，你可能可以使用一些編碼，而不是直接表示。 – Peter

使用std :: bitset < 4>來存儲一個十進制數字是不錯的主意嗎？

是的，原則上這是一個好主意。這是一個衆所周知的優化，稱爲BCD編碼。

（實際上是十進制數字）。什麼是空間有效的方式來存儲這樣的數據？

可以使用佔用字節的一個半字節壓縮十進制數字表示形式。數學也可能被應用優化，與數字的ASCII表示等。

std::bitset<4>將不能很好地壓縮數據。
std::bitset<4>仍將佔用全部字節。

另一種數據結構，我能想到的是位域

// Maybe #pragma pack(push(1)) 
struct TwoBCDDecimalDigits { 
    uint8_t digit1 : 4; 
    uint8_t digit2 : 4; 
}; 
// Maybe #pragma pack(pop)

甚至還有可用庫，這種格式轉換成你的目標CPU架構支持的標準化數字格式：

XBCD_Math

我能想到的另一種方式是寫自己的類：

class BCDEncodedNumber { 
    enum class Sign_t : char { 
     plus = '+' , 
     minus = '-' 
    }; 
    std::vector<uint8_t> doubleDigitsArray; 
public: 
    BCDEncodedNumber() = default; 
    BCDEncodedNumber(int num) { 
     AddDigits(num); // Implements math operation + against the 
         // current BCD representation stored in 
         // doubleDigitsArray. 
    }  
};

來源

2017-07-08 12:10:22 user0042

C++中的所有對象都必須至少佔用1個字節，所以如果使用「bitset <4>」，那麼僅僅使用'char'就沒有什麼優勢。 –

@MatteoItalia好的，那是一個誤解。我並不是說要使用0-9的每個數字一個完整的字節，而是使用單個字節的半字節。讓我糾正我的答案。 – user0042

肯定會更好，儘管這裏使用位域的恕我直言只是一個障礙 - 比如說你有一個向量「TwoBCDDecimalDigits」，現在要訪問第n位數字，你必須得到元素n/2，然後有一個如果在n ％2決定要閱讀哪個成員。如果它只是一個'uint8_t'數組，就像在第二個解決方案中那樣，你可以在沒有分支的情況下進行移位（第n位數字='array [n >> 1] >>（（n＆1）<< 2）' ）。 –

根據如何節省空間的必須是，如何高效的檢索應該是，我看到了兩個可能性：

由於std::bitset<4>的矢量（據我所知）存儲在一個解壓縮的設置中（每個bitset存儲在一個內存字，32位或64位），您應該至少使用打包的表示，如使用64位字存儲16位數字：
```
store (if the digit was not stored before): 
block |= digit << 4 * index 
load: 
digit = (block >> 4 * index) & 0xF 
reset: 
block &= ~(0xF << 4 * index); 
```

這些64位字（uint64_t）的向量連同一些訪問方法應該很容易實現。

如果您的空間要求更嚴格，您可以嘗試使用分區和模數來打包10位（最多1024位）的3位數字，這將少得多的時間效率。此外，與64位字的對齊要困難得多，所以如果您需要最終提高16％，我只會推薦這樣做，最多可以獲得3.3位每位數字。

來源

2017-07-08 12:13:14

如果你想有一個非常緊湊的方式，則沒有使用bitset<4>是一個壞主意，因爲bitset<4>會使用至少一個字節，而不是4位。

我推薦使用std::vector<std::uint32_t>

您可以存儲多個數字在uint32_t的。兩種常用的方法：

用於每位4位，並使用位操作。這樣你可以存儲8個數字4個字節。在這裏，set/get操作非常快。效率：4位/數字
使用基數10編碼。 uint32_t的最大值是256^4-1，它能夠以4個字節存儲9個數字。效率：3.55bit /位。在這裏，如果您需要設置/獲取所有9位數字，那麼它幾乎與以前的版本相比速度更快（因爲除以10將被優化的編譯器優化，不會由CPU完成實際的分割）。如果你需要隨機訪問，那麼set/get會比以前的版本慢（你可以用libdivide加速）。

如果使用的uint64_t代替uint32_t，則可以存儲16位與第一種方式（4位相同/數字效率），和19位與第二方式：3.36bit /數字高效化，這是非常接近到理論上的最小值：〜3.3219bit/digit

來源

2017-07-08 12:27:16 geza

存儲一個十進制數字

回答

相關問題