0

当社の最新プロジェクトでは、char ry を半バイト左に移動したいと考えています。

char buf[] = {0x12, 0x34, 0x56, 0x78, 0x21}

buf を次のようにしたい

0x23, 0x45, 0x67, 0x82, 0x10

プロセスをより効率的にするにはどうすればよいですか? 処理するバイト数が N の場合、時間の複雑さを O(N) より小さくすることはできますか?

SOS...
4

4 に答える 4

3

これ以上のコンテキストがなければ、実際の配列の必要性を疑問視することさえあります。4 バイトの場合は、 を使用して簡単に表すことができ、シフト操作uint32_tを実行できます。O(1)

uint32_t x = 0x12345678;
uint32_t offByHalf = x << 4;

このようにして、次のように、配列アクセスをビット マスキングに置き換えます。

array[i]

と同等です

(x >> 8 * (3 - i)) & 0xff

そして、演算はメモリ アクセスよりも高速である可能性さえあります。しかし、私の言葉を鵜呑みにしないで、ベンチマークしてください。

于 2013-10-23T06:48:11.183 に答える
2

いいえ、実際に配列をシフトしたい場合は、すべての要素を少なくとも 1 回ヒットする必要があるため、O(n) になります。それを回避することはできません。次のようなものでそれを行うことができます：

#include <stdio.h>

void shiftNybbleLeft (unsigned char *arr, size_t sz) {
    for (int i = 1; i < sz; i++)
        arr[i-1] = ((arr[i-1] & 0x0f) << 4) | (arr[i] >> 4);
    arr[sz-1] = (arr[sz-1] & 0x0f) << 4;
}

int main (int argc, char *argv[]) {
    unsigned char buf[] = {0x12, 0x34, 0x56, 0x78};
    shiftNybbleLeft (buf, sizeof (buf));
    for (int i = 0; i < sizeof (buf); i++)
        printf ("0x%02x ", buf[i]);
    putchar ('\n');
    return 0;
}

これにより、次のことが得られます。

0x23 0x45 0x67 0x80

より効率的にすることができないと言っているわけではありません(a)。代わりに、異なる動作をするように抽出コードを変更すると、シフト操作を回避できます。

つまり、配列をシフトせずに、単にオフセット変数を設定し、それを使用して抽出プロセスを変更します。次のコードを調べます。

#include <stdio.h>

unsigned char getByte (unsigned char *arr, size_t index, size_t shiftSz) {
    if ((shiftSz % 2) == 0)
        return arr[index + shiftSz / 2];
    return ((arr[index + shiftSz / 2] & 0x0f) << 4)
        | (arr[index + shiftSz / 2 + 1] >> 4);
}

int main (int argc, char *argv[]) {
    unsigned char buf[] = {0x12, 0x34, 0x56, 0x78};
    //shiftNybbleLeft (buf, sizeof (buf));
    for (int i = 0; i < 4; i++)
        printf ("buf[1] with left shift %d nybbles -> 0x%02x\n",
            i, getByte (buf, 1, i));
    return 0;
}

0にshiftSz設定すると、配列がシフトされていないかのようになります。shiftSzゼロ以外に設定すると、O(1) 操作getByte()は実際には、その量だけシフトしたかのように要素を返します。出力は期待どおりです。

Index 1 with left shift 0 nybbles -> 0x34
Index 1 with left shift 1 nybbles -> 0x45
Index 1 with left shift 2 nybbles -> 0x56
Index 1 with left shift 3 nybbles -> 0x67

これは不自然な例のように思えるかもしれませんが (実際にそうであるため)、潜在的にコストのかかる操作を回避するためにそのようなトリックを使用することには十分な前例があります。また、配列外の参照に関する問題をキャッチするために、いくつかの境界チェックを追加することも必要になるでしょう。

トレードオフがあることに注意してください。配列をシフトする必要がないことで得られるものは、抽出中に行われる計算によってある程度相殺される場合があります。実際に価値があるかどうかは、データをどのように使用するかによって異なります。配列が大きいがそこから多くの値を抽出しない場合、このトリックは価値があるかもしれません。

コストのかかる操作を防ぐために「トリック」を使用する別の例として、(文字を削除するときなどに) 行の内容をわざわざ移動しないテキスト エディターを見てきました。代わりに、文字を 0 コード ポイントに設定し、行を表示するときにそれを処理します (0 コード ポイントは無視します)。

通常、最終的にはクリーンアップされますが、多くの場合、編集速度を妨げないバックグラウンドでクリーンアップされます.

（a）実際にこれが必要であることを確認したい場合があります。

あなたのコメントの 1 つは、あなたの配列の長さは約 500 エントリであると述べており、私の極端に不機嫌ではない開発ボックスは、その配列を毎秒約 50 万回の割合で左に 1 ニブルシフトできると言えます。

そのため、プロファイラーがそこに多くの時間が費やされていると述べたとしても、それは必ずしもそれが大量の時間であることを意味するわけではありません.

特定の識別されたボトルネックがある場合にのみ、コードの最適化を検討する必要があります。

于 2013-10-23T06:40:54.203 に答える
0

質問の唯一の客観的に答えられる部分に取り組みます。それは次のとおりです。

処理するバイト数が N の場合、時間の複雑さを O(N) 未満にすることはできますか?

出力配列全体が必要な場合は、いいえ、以上のことはできませんO(N)。

出力配列の特定の要素のみが必要な場合は、それらだけを計算できます。

于 2013-10-23T06:41:15.750 に答える