5

私のアプリを callgrind で実行すると、この行が他のすべてのものを約 10,000 倍小さくすることが明らかになりました。おそらくそれを中心に再設計するつもりですが、疑問に思いました。それを行うより良い方法はありますか？

現時点で私がやっていることは次のとおりです。

int i = 1;
while
(
    (
        (*(buffer++) == 0xffffffff && ++i) || 
        (i = 1)
    )
    &&
    i < desiredLength + 1
    &&
    buffer < bufferEnd
);

32 ビット符号なし int 配列で、desiredLength 0xffffffff 値の最初のチャンクのオフセットを探しています。

これは、私が思いついた内部ループを含むどの実装よりも大幅に高速です。しかし、それでも遅すぎる。

4

6 に答える 6

4

私もsearch_n提案に行きます。これが適切に行われると確信しているためです。これは実際には非常に簡単で、基本的に desired_length 倍高速化できます。ターゲット値が配列内で非常に密集していない限り。

アイデアは次のとおりです。 position でK始まる値の連続したインスタンスがある場合、 positionにその値が含まれてIいる必要があります。I + K - 1したがって、最初にそれを確認します。そうでない場合、K 個の連続した値を含む可能性がある最も早い位置はI + Kであるため、そこでアルゴリズムを再起動できます。

一方、 に値が見つかった場合は、到達するまで(この場合は成功)、または目標値を含まない位置に到達I + K - 1するまで逆方向にスキャンします。後者の場合、 からまでのターゲット値があることがわかっているので、 をチェックします。それが機能する場合は、 まで逆方向にスキャンするだけです。うまくいかない場合は、 でアルゴリズムを再起動します。IJ - 1JI + K - 1J + K - 1I + KJ + K

ほとんどの場合K'th、ベクトル内のすべての位置のみを確認します。大きなK、それは大きな勝利です。

于 2012-10-18T22:29:47.603 に答える
3

c++ にタグを付けたので、STL アルゴリズムが利用可能であると仮定します。

std::search_n(buffer, bufferEnd, desiredLength, 0xffffffff);
于 2012-10-18T22:10:44.260 に答える
2

memcmpC 標準ライブラリから使用してみてください。最新のコンパイラはmemxxx、最新の CPU の速度を最大限に引き出す関数の実装を非常に最適化する必要があります。

于 2012-10-18T22:09:18.847 に答える
2

考えただけですが、int 配列を 1 つずつ反復処理していますか? これについて考えてみてください。その間にチェックインしても意味がない*(buffer) != 0xffffffffとbuffer[desiredLength-1] != 0xffffffff確信できる場合は、1 よりもはるかに大きい場合に速度が大幅に向上する可能性がある 1 だけでbufferはdesiredLengthなく、1だけ先に進むことができます。desiredLengthもちろん、次の理由で関数が複雑になります。

  1. 両方*(buffer)がbuffer[desiredLength-1]等しい場合0xffffffff、それらの間で連続しているとは想定できないため、それでも確認する必要があります。
  2. *(buffer)等しくない0xffffffffがbuffer[desiredLength-1]等しい場合は、シーケンス0xffffffffの先頭まで追跡する必要があります。0xffffffff
  3. チェックするときにバッファをオーバーランしないようにする必要がありますbuffer[desiredLength-1]

もう少し複雑ですが、速度が向上する可能性があります。それが理にかなっていることを願っています。

于 2012-10-18T22:28:23.953 に答える
1

これを実装したい場合は、とを使用して実装しmemchrますmemcmp：

bool found = false;
std::vector<unsigned char> tmp(desiredLength*sizeof(uint32_t), 0xFF);
while( true ) {
    void* p = memchr(bufferStart, 0xFF,
        (bufferEnd-bufferStart-desiredLength) * sizeof(uint32_t));
    if( !p ) break;
    if( !memcmp(p, &tmp[0], desiredLength * sizeof(uint32_t)) ) {
        found = true;
        break;
    }
}

またstd::search_n、独自のコードよりも最適化されている可能性のあるものを使用できます

于 2012-10-18T22:13:00.173 に答える
0

利用できない場合std::search_n:

int i = 1;
while
(
    (
        i == 1
        &&
        buffer < bufferEnd
        &&
        (
            (
                *buffer == desired
                &&
                *(buffer + desiredLength - 1) == desired
                &&
                (i = 3)
            )
            ||
            (buffer += desiredLength && (i = 1))
        )
    )
    ||
    (
        i == 2
        &&
        (
            (
                buffer > arr
                &&
                (*(--buffer) == desired)
            )
            ||
            (i = 3)
        )
    )
    ||
    (
        i >= 3
        &&
        buffer < bufferEnd
        &&
        (
            (
                *(buffer++) == desired
                &&
                (i++ || true)
            )
            ||
            (i = 1)
        )
        &&
        (
            i < 3
            ||
            i - 3 < desiredLength + 1
        )
    )
);
buffer -= i - 4;

if (buffer > bufferEnd - (i-3))
    buffer = bufferEnd;

よりわずかに遅いだけで同一の結果を返しますstd:search_n:

buffer = std::search_n(buffer, bufferEnd-1, desiredLength, desired);
if (buffer == bufferEnd-1)
    buffer = bufferEnd;
于 2012-10-19T12:38:49.497 に答える