在很小的内存中表示非常大的位数组
我想以某种方式将包含 250 M 状态（每个状态 1 位）的结构表示为尽可能少的内存（最多 100 k）。对它的操作是set/get。我冷不说它是密集或稀疏，它可能会有所不同。 我想使用的语言是 C。
我在这里查看了其他线程以找到也合适的语言。例如，像布隆过滤器这样的概率结构就不适合，因为可能存在错误答案。
请问有什么建议吗？
I would like to represent a structure containing 250 M states(1 bit each) somehow into as less memory as possible (100 k maximum). The operations on it are set/get. I cold not say that it's dense or sparse, it may vary.
The language I want to use is C.
I looked at other threads here to find something suitable also. A probabilistic structure like Bloom filter for example would not fit because of the possible false answers.
Any suggestions please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
如果您知道您的数据可能稀疏，那么您可以使用游程编码。但除此之外，你无法压缩它。
If you know your data might be sparse, then you could use run-length encoding. But otherwise, there's no way you can compress it.
结构的大小取决于信息的熵。如果没有重复的模式，就无法将信息压缩到小于给定的大小。最坏的情况仍然是您的情况下大约有 32Mb 的存储空间。如果您了解位之间的关系，那么也许有可能......
The size of the structure depends on the entropy of the information. You cannot squeeze information something in less than a given size if you have no repeated pattern. The worst case would still be about 32Mb of storage in your case. If you know something about the relation between the bits then it's maybe possible...
我认为不可能做到你所要求的。如果您需要覆盖 2.5 亿个状态，每个状态 1 位，则需要 250Mbits/8 = 31.25MBytes。与 100KBytes 相差甚远。
您通常会创建一个大型字节数组，并使用函数来确定字节 (
index >> 3) 和位位置 (index & 0x07)设置/清除/获取。I don't think it's possible to do what you're asking. If you need to cover 250 million states of 1 bit each, you'd need 250Mbits/8 = 31.25MBytes. A far cry from 100KBytes.
You'd typically create a large array of bytes, and use functions to determine the byte (
index >> 3) and bit position (index & 0x07) to set/clear/get.250M 位将需要 31.25 MB 来存储（当然假设 8 位/字节），远远超过您的 100k 目标。
解决这个问题的唯一方法是开始利用数据中的一些稀疏性或模式。
250M bits will take 31.25 megabytes to store (assuming 8 bits/byte, of course), much much more than your 100k goal.
The only way to beat that is to start taking advantage of some sparseness or pattern in your data.
100K 内存中可以存储的最大位数为 819,200 位。假设 1 K = 1024 字节，1 字节 = 8 位。
The max number of bits you can store in 100K of mem is 819,200 bits. This is assuming that 1 K = 1024 bytes, and 1 byte = 8 bits.
您的环境中可能存在文件吗？
如果是这样，您可以交换，例如 4k 大小的分段位缓冲区。
您的解决方案应该以序列化的方式访问这些位
最小化磁盘加载/保存操作。
are files possible in your environment ?
if so, you might swap, say for example 4k sized segmented bit buffer.
your solution shoud access those bits in a serialized way to
minimize disk load/save operation.