7

是否有一些相当快的代码可以帮助我快速搜索大位图（几兆字节）以查找连续的零位或一位的运行？

我所说的“相当快”是指可以利用机器字长并一次比较整个字的东西，而不是进行非常慢的逐位分析（例如使用vector<bool>）。

例如，在卷的位图中搜索可用空间（用于碎片整理等）非常有用。

4

3 回答 3

1

Windows 有RTL_BITMAP一种可以与 API 一起使用的数据结构。

但是我前一段时间需要这个代码，所以我在这里写了它（警告，它有点难看）：
https ://gist.github.com/3206128

我只对其进行了部分测试，因此它可能仍然存在错误（尤其是在 上reverse）。但是最近的一个版本（与这个版本略有不同）似乎对我有用，所以值得一试。

整个事情的基本操作是能够 - 快速 - 找到一系列位的长度：

long long GetRunLength(
    const void *const pBitmap, unsigned long long nBitmapBits,
    long long startInclusive, long long endExclusive,
    const bool reverse, /*out*/ bool *pBit);

鉴于其多功能性，其他一切都应该很容易建立在此之上。

我试图包含一些 SSE 代码，但它并没有显着提高性能。但是，总的来说，代码比逐位分析快很多倍，所以我认为它可能有用。

如果你能以某种方式获得 ' 缓冲区应该很容易测试vector<bool>——如果你使用的是 Visual C++，那么我包含的一个函数可以为你做这件事。如果您发现错误，请随时告诉我。

于 2012-07-30T11:01:32.507 回答
0

我不知道如何直接在记忆词上做得很好，所以我制定了一个快速解决方案，它适用于字节；为方便起见，让我们画出计算连续数的算法：

构建两个大小为 256 的表，您将在其中为 0 到 255 之间的每个数字写入字节开头和结尾的尾随 1 的数量。例如，对于数字 167（二进制为 10100111），将 1 放在第一个表中，将 3 放在第二个表中。我们称第一个表为 BBeg，第二个表为 BEnd。然后，对于每个字节 b，有两种情况：如果它是 255，则将 8 加到当前连续的集合的当前总和中，并且您处于一个区域中。否则，您以 BBeg[b] 位结束一个区域，并以 BEnd[b] 位开始一个新区域。根据你想要的信息，你可以调整这个算法（这是我没有放任何代码的原因，我不知道你想要什么输出）。

一个缺陷是它不计算一个字节内的（小）连续的集合......

除了这个算法，有朋友告诉我，如果是做磁盘压缩，只需要寻找不同于0（空盘区）和255（满盘区）的字节即可。构建必须压缩的块的地图是一种快速的启发式方法。也许它超出了这个话题的范围......

于 2012-07-30T13:46:42.517 回答
0

听起来像这样可能有用：

http://www.aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29 和 http://www.aggregate.org/MAGIC/#Leading%20Zero%20Count

您没有说您是否想做某种 RLE 或简单地计算字节内的零和一位（如 0b1001 应该返回 1x1 2x0 1x1）。

用于快速检查的查找表和 SWAR 算法可能会轻松地为您提供该信息。有点像这样：

byte lut[0x10000] = { /* see below */ };
for (uint * word = words; word < words + bitmapSize; word++) {
   if (word == 0 || word == (uint)-1) // Fast bailout
   {
       // Do what you want if all 0 or all 1
   }
   byte hiVal = lut[*word >> 16], loVal = lut[*word & 0xFFFF];
   // Do what you want with hiVal and loVal

LUT 必须根据您的预期算法构建。如果你想计算单词中连续的 0 和 1 的数量，你可以这样构建它：

  for (int i = 0; i < sizeof(lut); i++) 
     lut[i] = countContiguousZero(i); // Or countContiguousOne(i)
  // The implementation of countContiguousZero can be slow, you don't care
  // The result of the function should return the largest number of contiguous zero (0 to 15, using the 4 low bits of the byte, and might return the position of the run in the 4 high bits of the byte
  // Since you've already dismissed word = 0, you don't need the 16 contiguous zero case.
于 2012-08-01T10:27:33.313 回答