Lưu trữ một số thập phân

Question

Tôi gặp sự cố liên quan đến số lượng lớn các số nguyên nhỏ (thực tế là chữ số thập phân). Không gian hiệu quả cách để lưu trữ dữ liệu như vậy là gì?

Bạn nên sử dụng std::bitset<4> để lưu trữ một chữ số thập phân?

Answer 1

Bạn nên sử dụng std :: bitset < 4> để lưu trữ một chữ số thập phân?

Vâng, về nguyên tắc đó là một ý tưởng hay. Đó là một tối ưu hóa nổi tiếng và được gọi là mã hóa BCD.

(chữ số thập phân thực sự). Không gian hiệu quả cách để lưu trữ dữ liệu như vậy là gì?

Bạn có thể thu nhỏ biểu thị chữ số thập phân bằng cách sử dụng một nibble của byte bị chiếm đóng. Toán học cũng có thể được áp dụng tối ưu hóa, so với biểu diễn các chữ số ASCII hoặc như vậy.

std::bitset<4> sẽ không phân phát tốt cho việc nén dữ liệu.
std::bitset<4> sẽ vẫn chiếm một byte đầy đủ.

Một cấu trúc dữ liệu thay thế tôi có thể nghĩ đến là một bitfield

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

Thậm chí còn có một thư viện có sẵn, để chuyển đổi định dạng này sang định dạng số bình thường hỗ trợ tại mục tiêu CPU kiến ​​trúc của bạn:

• XBCD_Math

---

Một cách khác tôi có thể nghĩ đến là viết lớp của riêng bạn:

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. 
    }  
}; 

Answer 2

Tùy thuộc vào cách không gian hiệu quả nó phải được và hiệu quả như thế nào hồi nên, tôi thấy hai khả năng:

• Vì vector của std::bitset<4> là (theo như tôi biết) được lưu trữ trong cài đặt chưa được giải nén (mỗi bitet được lưu trữ trong một từ bộ nhớ, 32 hoặc 64 bit), bạn nên sử dụng một biểu diễn đóng gói như Từ 64 bit để lưu trữ 16 chữ số:

  store (if the digit was not stored before): 
  block |= digit << 4 * index 
  load: 
  digit = (block >> 4 * index) & 0xF 
  reset: 
  block &= ~(0xF << 4 * index); 
  

Một vectơ của các từ 64 bit này (uint64_t) cùng với một số phương pháp truy cập phải dễ triển khai.

• Nếu yêu cầu về không gian của bạn thậm chí còn chặt chẽ hơn, bạn có thể, ví dụ: hãy thử đóng gói 3 chữ số trong 10 bit (tối đa 1024) bằng cách sử dụng các bộ phận và modulo, điều này sẽ ít hiệu quả về thời gian hơn. Ngoài ra sự liên kết với các từ 64 bit là khó khăn hơn nhiều, vì vậy tôi sẽ chỉ khuyên bạn nên điều này nếu bạn cần để có được cải thiện 16% cuối cùng, nhiều nhất bạn có thể nhận được một cái gì đó giống như 3,3 bit cho mỗi chữ số.

Answer 3

Nếu bạn muốn một cách rất nhỏ gọn, thì không, sử dụng bitset<4> là một ý tưởng tồi, vì bitset<4> sẽ sử dụng ít nhất một byte, thay vì 4 bit.

tôi khuyên bạn nên sử dụng std::vector<std::uint32_t>

Bạn có thể lưu trữ nhiều chữ số trong một uint32_t. Hai cách thông thường:

1. Sử dụng cho 4 bit cho mỗi chữ số và sử dụng thao tác bit. Bằng cách này bạn có thể lưu trữ 8 chữ số trong 4 byte. Ở đây, thiết lập/nhận được hoạt động khá nhanh. Hiệu quả: 4 bit/chữ số
2. Sử dụng mã hóa cơ sở 10. Giá trị tối đa uint32_t là 256^4-1, có khả năng lưu trữ 9 chữ số trong 4 byte. Hiệu quả: 3,55 bit/chữ số. Ở đây, nếu bạn cần thiết lập/nhận được tất cả 9 chữ số, thì nó gần như nhanh hơn phiên bản trước (khi phân chia bởi 10 sẽ được tối ưu hóa bởi trình biên dịch tốt, không có bộ phận thực tế nào được thực hiện bởi CPU). Nếu bạn cần truy cập ngẫu nhiên, sau đó thiết lập/nhận sẽ chậm hơn phiên bản trước (bạn có thể tăng tốc nó lên với libdivide).

Nếu bạn sử dụng uint64_t thay vì uint32_t, sau đó bạn có thể lưu trữ 16 chữ số với cách đầu tiên (cùng 4bit/hiệu quả chữ số), và 19 chữ số với cách thứ hai: efficieny 3.36bit/chữ số, mà là khá chặt chẽ đến mức tối thiểu lý thuyết: ~ 3.3219bit/digit