一个压缩的位集类

• 下载演示项目 - 20.1 Kb
• 下载源代码 - 8.3 Kb

引言

标准模板库 bitset 类是一个有用的类，适用于大多数位集操作，但如果您处理大量的位集，那么 STL bitset 类可能缺少一些技巧。

在许多使用位集的应用程序中，您会发现典型的位集要么很少填充位，要么相反，几乎完全设置。 在这些情况下，大的位集会占用大量内存，而实际表示的内容却很少。

为了克服这个问题，我们开发了 CMJBitset 类作为位集的插件替代品。 CMJBitset 类根据编译选项，可能仅需 7 个字节即可表示任何大小的位集，假设所有位都已设置或重置。 相比之下，一个 1024 位的 bitset 将占用 128 个字节。 本质上，如果位集几乎全部设置/重置，则 CMJBitset 通过运行长度编码位集来操作，否则使用 STL bitset 类。 我们将把不同的编码称为正常、稀疏和完全。

使用代码

通用用法

使用 CMJBitset 类应该很简单，只需将代码中的 bitset<N> 替换为 CMJBitset<N>，并包含 CMJBitset.h 头文件。 由于 CMJBitset 提供与 bitset 相同的接口，因此这应该足以使事情正常工作。

加载/保存位集

如果您无法将位集保存和加载到文件中，则该类将无法发挥其潜在优势的一小部分。 因此，提供了成员函数

bool load(FILE *)

和

bool save(FILE *)

但是，更重要的是，该类的所有成员都是公共的，使您可以随意加载和保存。

编译选项

如果您检查 MJBitset.h，则会发现许多编译选项。

用于调试

示例项目使用它来测试 CMJBitset 类。 我也建议在尝试 CMJBitset 类时，您也进行一些测试。 截至目前，尚未对该类进行“完全覆盖”测试，因此肯定存在错误的可能性。

//
// When DEBUG_CMMJBITSET is defined, then a shadow bitset 
// is kept and validated against operations.
// This is obviously very slow and uses loads of memory and 
// defeats any purpose in using this class
// and hence should never be used outside of a debug session.
//
//
//#define DEBUG_CMJBITSET

对于您需要处理的最大位集大小

默认为最大 0xffff。

//
// data representation type for bitsets <= 256 
// CMJBITSET_USE_CHAR should be defined
//

//#define CMJBITSET_USE_CHAR
#define CMJBITSET_USE_SHORT
//#defineCMJBITSET_USE_LONG

示例项目

示例项目是一个简单的 Win32 控制台应用程序，它试图通过创建一系列具有随机填充级别的位图，并对位集执行相当全面的操作来回归 CMJBitset。

您可以轻松地更改回归测试，以比较 CMJBitset 和 bitset 之间的性能。

关注点

性能

CMJBitset 类的性能很难量化。 对于它不编码为完全或稀疏的位集，CMJBitset 类显然比 bitset 慢几倍。

如果您运行示例回归测试并使其使用稀疏位集，则时间仍然比 bitset 快一点。 但是，一旦操作停止完全在内存中，无论是由于分页还是加载/保存到文件，比较速度都会急剧增加。

我们已经在 WhereWasI 产品中测试了该类，并且看到了内存使用量的显着减少和速度的显着提高。

同样值得注意的是，CMJBitset 的某些操作比 bitset 快得多，例如，flip() 只需要反转完全和稀疏表示类型。

在源文件的顶部，有许多编译选项会影响 CMJBitset 分配内存的方式，关键选项默认情况下是设置的，并在类中为最多设置/取消设置 4 位的位集保留空间。 这通常避免了使用 malloc/free 的时间和内存开销，并且在我们的示例中，这是一个明确的性能优势。 您的里程可能会有所不同，您可能需要通过更改其中一些值来调整性能。

历史

• 2004 年 6 月 14 日 - 发布 1.00 版本。
• 2004 年 6 月 18 日 - 发布 1.01 版本。 包含许多优化