尋找一種更有效的位域解碼算法

我有一個Visual Studio 2008 C++應用程序，其中我接收的位圖（未的圖像）。翻轉的每個位對應於解碼映射上的位置。尋找一種更有效的位域解碼算法

typedef unsigned char BYTE; 
const unsigned int COL_COUNT = 8; 
const unsigned int ROW_COUNT = 4; 

static char g_decode_map[ ROW_COUNT ][ COL_COUNT ] = 
{ 
    { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' }, 
    { 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p' }, 
    { 'q', 'r', 's', 't', 'u', 'v', 'w', 'x' }, 
    { 'y', 'z', ',', '.', ' ', ':', '-', '+' } 
}; 

// current implementation 
void Decode(const BYTE bitmap[ ROW_COUNT ], 
      const char decode_map[ ROW_COUNT ][ COL_COUNT ], 
      char decoded[ ROW_COUNT * COL_COUNT ]) 
{ 
    int found = 0; 
    for(int i = 0; i < ROW_COUNT; ++i) 
    { 
     for(int j = 0; j < COL_COUNT; ++j) 
     { 
      if(std::bitset<COL_COUNT>(bitmap[ i ]).test(j)) 
      { 
       decoded[ found++ ] = g_decode_map[ i ][ COL_COUNT - j - 1 ]; 
      } 
     } 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    BYTE bitmap[ ROW_COUNT ] = { 0x01, 0x80, 0x00, 0x00 }; 
    // expected output { 'h', 'i' } or { 'i', 'h' } order is unimportant 

    char decoded[ ROW_COUNT * COL_COUNT + 1 ] = { }; 
    Decode(bitmap, g_decode_map, decoded); 
    printf("Decoded: %s\r\n", decoded); 
    return 0; 
}

我目前的解碼實現工作正常，但它讓我感到可能有一個更有效的方法來做到這一點。任何人都可以提出更高性能的算法嗎？

來源

2012-04-29 PaulH

這將是更快地測試每個位是否被設置爲位操作，而不是創建針對每個被測試的位一個bitset。嘗試是這樣的：

for(int i = 0; i < ROW_COUNT; ++i) { 
    for(int j = 0; j < COL_COUNT; ++j) { 
     if(bitmap[i] & (1 << j)) { 
      ...

1 << j產生掩碼，只有你是想測試設置位。只有在bitmap[i]中設置了該位，纔會將位圖字節與掩碼一起返回true。這個條件的結果應該等於你的條件結果，它應該快很多。

來源

2012-04-29 05:33:30

你做的64個條件檢查。 for循環中有32個，for循環中有32個。如果你不能擺脫for循環中的32，你可以做的最好的是循環展開，以減少forloops執行的條件語句的數量。行和列的長度被定義爲常量。您可以展開循環並硬編碼索引的一些數字。而不是內循環，你可以寫下8如果下面的語句。

該離開的問題，如果有人有什麼改變的常數值？然後代碼打破。那是對的。如果您需要足夠強大以抵禦這種情況，您可以使用編譯時遞歸來展開循環（以下鏈接）。而且，任何看着你的代碼的人都會畏懼並且認爲你是上帝。：P另外，傑森的解決方案也會加快速度。

if(std::bitset<COL_COUNT>(bitmap[ i ]).test(0)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(1)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(2)) 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(3)) 
... 
if(std::bitset<COL_COUNT>(bitmap[ i ]).test(7))

Compile Time Loops(Answer #1)
Template Meta Programming

來源

2012-04-29 07:36:35 JustinDanielson

COL_COUNT可能不能改變（8位爲一個字節）。但是ROW_COUNT可以在編譯時改變。 – PaulH 2012-04-29 17:02:26

如果你嘗試做一個編譯時間循環，你將不得不使用一個字節數組，並通過引用 – JustinDanielson 2012-04-29 19:16:06

這是如何做到這一點快，假設COL_COUNT == 8（做真的快，使用在線彙編）：

for(int i = 0; i < ROW_COUNT; ++i) 
    { 
     unsigned char next_byte = bitmap[i] ; 
     for(int j = 0; j < COL_COUNT; ++j) 
     { 
      if (next_byte & 0x80) 
      { 
       decoded[ found++ ] = g_decode_map[ i ][ j ]; 
      } 
      next_byte <<= 1 ; 
     } 
    }

我已經編碼它來重現你的程序的行爲 - 但你確定你有它的權利？我希望你每次增加found，而不是當找到一個1位。

來源

2012-04-29 08:01:50 TonyK

是的，我只想來用解碼陣列具有值解碼它傳遞給他們的功能位打開。 – PaulH 2012-04-29 17:00:56

尋找一種更有效的位域解碼算法

回答

相關問題