0

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;
}

私の現在のデコード実装は正常に機能しますが、これを行うためのより効率的な方法があるかもしれないと私は思います。誰かがよりパフォーマンスの高いアルゴリズムを提案できますか？

4

3 に答える 3

1

64の条件付きチェックを実行しています。forループ内で32、forループ内で32。forループ内の32を取り除くことができない場合、forloopsによって実行される条件ステートメントの数を減らすためにループを展開するのが最善の方法です。行と列の長さは定数として定義されています。ループを展開して、インデックスの数値の一部をハードコーディングできます。内部のforループを使用する代わりに、次のような8ifステートメントを記述できます。

これは疑問を残します、誰かが定数値を変更した場合はどうなりますか？その後、コードが壊れます。それは正しいです。それに耐えるのに十分な堅牢性が必要な場合は、コンパイル時の再帰を使用してループを展開できます（以下のリンク）。また、あなたのコードを見る人は誰でも恐れを抱き、あなたが神だと思うでしょう。：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 ) )

コンパイル時のループ（回答＃1）
テンプレートメタプログラミング

于 2012-04-29T07:36:35.547 に答える
1

テストされるビットごとにビットセットを作成するよりも、各ビットがビット単位の演算で設定されているかどうかをテストする方が高速です。次のようなものを試してください。

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

1 << jテストしたいビットのみを含むマスクを生成します。ビット単位でマスクをビット単位バイトで固定すると、そのビットがに設定されている場合にのみtrueが返されますbitmap[i]。この条件付きの結果は、条件付きの結果と同等である必要があり、はるかに高速である必要があります。

于 2012-04-29T05:33:30.300 に答える
0

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 ;
        }
    }

私はあなたのプログラムの振る舞いを再現するためにそれをコーディングしました-しかしあなたはそれが正しいと確信していますか？-bitが見つかっfoundたときだけでなく、毎回インクリメントすることを期待します。1

于 2012-04-29T08:01:50.803 に答える