高效的bits容器
我有一个位数组，它在某些部分非常密集，而在其他部分非常稀疏。该数组最大可达2**32位。我将它转换成一堆包含偏移量和长度的元组，以便在内存中更有效地处理它。然而，对于像10101010100011这样的东西，这有时效率较低。有没有什么好办法把它存储在内存中？
回答 5
Stack Overflow用户
发布于 2009-08-10 02:01:42
如果我没理解错的话，你是用(offset, length)的元组来表示1位的游程吗？如果是这样的话，更好的方法是使用压缩位字段的运行。对于密集区域，你会得到一个很好的高效数组，而在非密集区域，你会得到隐含的零。例如，在C++中，表示形式可能如下所示：
// The map key is the offset; the vector's length gives you the length
std::map<unsigned int, std::vector<uint32_t> >查找包括在相关比特位置之前找到关键字，以及查看比特是否落入其向量中。如果是，则使用向量中的值。否则，返回0。例如：
typedef std::map<unsigned int, std::vector<uint32_t> > bitmap; // for convenience
typedef std::vector<uint32_t> bitfield; // also convenience
bool get_bit(const bitmap &bm, unsigned int idx) {
unsigned int offset = idx / 32;
bitmap::const_iterator it = bm.upper_bound(offset);
// bm is the element /after/ the one we want
if (it == bm.begin()) {
// but it's the first, so we don't have the target element
return false;
}
it--;
// make offset be relative to this element start
offset -= it.first;
// does our bit fall within this element?
if (offset >= it.second.size())
return false; // nope
unsigned long bf = it.second[offset];
// extract the bit of interest
return (bf & (1 << (offset % 32))) != 0;
}Stack Overflow用户
发布于 2009-08-10 02:08:28
了解更多会有所帮助。所谓“非常稀疏/密集”，是指数百万个连续的0/1，还是指本地(多大本地？)0的比例非常接近于0还是1？哪一种值占主导地位？有没有什么模式可以让游程编码变得有效？您将如何使用此数据结构？(随机访问？被访问索引的分布是什么样的？大块是从未访问过还是很少访问？)
我只能猜测你不会以每秒数十亿比特的速率随机访问和修改所有40亿比特。
Stack Overflow用户
发布于 2009-08-10 03:27:47
如何组织事物将取决于你的数据是什么。为了尝试表示大量数据，您将需要具有长时间的0或1运行。这将消除重新呈现它的需要。如果不是这样，并且你有大约相同数量的1和0，你会更好地使用所有的内存。
将其视为压缩问题可能会有所帮助。为了使压缩有效，必须有一个模式(或整个空间中使用的一组有限的项目)和不均匀的分布才能使压缩起作用。如果所有元素都被使用并均匀分布，则很难进行压缩，或者可能会占用比实际数据更多的空间。
如果只有0和1的游程(多于1)，使用偏移量和长度可能会有一定的意义。如果存在不一致的运行，您可以将位复制为位数组，其中有偏移量、长度和值。
上面的效率将取决于您是否有大量的1或0运行。你要小心确保你没有使用更多的内存来表示你的内存，然后只使用内存本身，(即你使用更多的内存来表示内存，而不是直接把它放到内存中)。
https://stackoverflow.com/questions/1252847
复制相似问题
腾讯云开发者
