用於搜索連續置位/清除位的位數組的快速代碼？

是否有一些合理的快速代碼可以幫助我快速搜索一個大的位圖（幾兆字節）用於連續零位或一位的運行？「合理快速」我的意思是可以利用機器字的大小並一次比較整個單詞，而不是進行可怕的慢速比特分析（如vector<bool>）。用於搜索連續置位/清除位的位數組的快速代碼？

它對於例如搜索卷的位圖以獲得可用空間（用於碎片整理等）。

來源

2012-07-30 Mehrdad

你不能把你的數組當作一個整數數組並將整數比較爲零嗎？ – Andrew 2012-07-30 11:06:36

@Andrew：這種類型取決於你想要達到的效果......這些比特可能不會一次對齊8比特。 – Mehrdad 2012-07-30 11:42:54

您可以比較6個字節（如果bmp是彩色圖像文件：6個字節是兩個連續像素），並且有6個零的數組。 – 2012-07-30 11:48:35

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代碼，但沒有明顯改善性能。但是，一般來說，代碼比逐位分析快很多倍，所以我認爲它可能有用。

它應該很容易測試，如果你可以以某種方式獲得緩衝區的緩衝區，並且如果你使用Visual C++，那麼我有一個函數可以幫助你。如果您發現錯誤，請隨時通知我。

來源

2012-07-30 11:01:32 Mehrdad

我不知道如何直接在記憶詞上做得很好，所以我編寫了一個快速的解決方案，它處理字節;爲了方便起見，我們來簡單介紹一下連續計數的算法：

構建兩個大小爲256的表，其中您將爲0到255之間的每個數字（在字節開始和結尾處的尾隨1寫入數）寫入兩個表。例如，對於數字167（二進制10100111），在第一個表中放置1，在第二個表中放入3。我們稱第一個表BBeg和第二個表BEnd。然後，對於每個字節b，有兩種情況：如果它是255，則將當前連續集合中的當前總和加8，並且您處於一個區域中。否則，您用一個BBeg [b]位結束一個區域，並用BEnd [b]位開始一個新區域。根據你想要的信息，你可以調整這個算法（這是我沒有把代碼放在這裏的原因，我不知道你想要什麼輸出）。

中的一個缺陷是，它不計數（小）組連續的一個字節內的人的...

除了這個算法，一個朋友告訴我，如果它是磁盤壓縮，只是看不同的字節從0（空盤區）和255（全盤區）。建立你必須壓縮的塊的映射是一種快速啓發式方法。也許它超出了這個話題的範圍......

來源

2012-07-30 13:46:42 Bentoy13

聽起來，這可能是有用的：

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-01 10:27:33 xryl669

用於搜索連續置位/清除位的位數組的快速代碼？

回答

相關問題