1

を使用しunsigned charて 8 つのフラグを格納しています。各フラグは立方体の角を表します。したがって00000001、コーナー101000100はコーナー3と7などになります。私の現在の解決策は&、1、2、4、8、16、32、64、および128の結果に対するもので、結果がゼロでないかどうかを確認し、コーナーを保存します。つまり、if (result & 1) corners.push_back(1);. その「if」ステートメントを取り除くことができる可能性はありますか? ビット単位の演算子でそれを取り除くことができることを望んでいましたが、何も考えられませんでした。

if ステートメントを削除したい理由について少し背景を説明します。この立方体実際には、サイズが少なくとも 512x512x512 のグリッドの一部であるボクセルです。これは 1 億 3,400 万を超えるボクセルです。ボクセルのそれぞれに対して計算を実行しています (厳密には正確ではありませんが、ここでは関係がないため詳細には触れません)。これは大量の計算です。そして、フレームごとにこれらの計算を実行する必要があります。関数呼び出しごとのわずかな速度向上は、これらの量の計算に役立ちます。アイデアを提供するために、私のアルゴリズムは（ある時点で）フロートが負、正、またはゼロであるかどうかを（何らかのエラー内で）判断する必要がありました。そこにifステートメントがあり、チェックよりも大きい/小さい。これを int 関数への高速フロートに置き換え、4 分の 1 秒短縮しました。現在、128x128x128 グリッドの各フレームには 4 秒強かかります。

4

5 に答える 5

5

まったく別のアプローチを検討します。フラグのさまざまな組み合わせの可能性は 256 しかありません。256 個のベクトルを事前に計算し、必要に応じてそれらにインデックスを付けます。

std::vector<std::vector<int> > corners(256);
for (int i = 0; i < 256; ++i) {
    std::vector<int>& v = corners[i];
    if (i & 1) v.push_back(1);
    if (i & 2) v.push_back(2);
    if (i & 4) v.push_back(4);
    if (i & 8) v.push_back(8);
    if (i & 16) v.push_back(16);
    if (i & 32) v.push_back(32);
    if (i & 64) v.push_back(64);
    if (i & 128) v.push_back(128);
}

for (int i = 0; i < NumVoxels(); ++i) {
    unsigned char flags = GetFlags(i);
    const std::vector& v = corners[flags];

    ... // do whatever with v
}

これにより、すべての条件が回避され、push_back呼び出しnewが発生する可能性が高くなります。

于 2010-11-15T01:02:53.163 に答える
1

Hackers's Delightの最初のページ:

x & (-x) // isolates the lowest set bit
x & (x - 1) // clears the lowest set bit

メソッドをインライン化するpush_backことも役立ちます (すべてのフラグを一緒に受け取る関数を作成することをお勧めします)。

通常、パフォーマンスが必要な場合は、それを念頭に置いてシステム全体を設計する必要があります。より多くのコードを投稿すると、支援が容易になる可能性があります。

編集：ここにいいアイデアがあります：

unsigned char LOG2_LUT[256] = {...};
int t;
switch (count_set_bits(flags)){
    case 8:     t = flags; 
                flags &= (flags - 1);       // clearing a bit that was set
                t ^= flags;                 // getting the changed bit
                corners.push_back(LOG2_LUT[t]);
    case 7:     t = flags; 
                flags &= (flags - 1);       
                t ^= flags;                 
                corners.push_back(LOG2_LUT[t]);
    case 6:     t = flags; 
                flags &= (flags - 1);       
                t ^= flags;                 
                corners.push_back(LOG2_LUT[t]);
    // etc...
};

count_set_bits()非常によく知られている関数です: http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

于 2010-11-15T00:48:59.270 に答える
1

ビットが設定されている場合は実行する必要があり、設定されていない場合は実行する必要がある操作がある場合は、どこかに何らかの条件を設定する必要があるようです。どういうわけか計算として表現できる場合、次のように回避できます。たとえば、次のようになります。

numCorners = ((result >> 0) & 1) + ((result >> 1) & 1) + ((result >> 2) & 1) + ...
于 2010-11-15T00:59:59.417 に答える
0

OpenTTD コードに同様のアルゴリズムがあることを確認しました。それはまったく役に立たないことが判明しました。そのように数値を分解しないことで、より速く作業を進めることができます。代わりに、vector<>現在の反復をバイトのビットの反復に置き換えます。これははるかにキャッシュフレンドリーです。

いえ

unsigned char flags = Foo(); // the value you didn't put in a vector<>
for (unsigned char c = (UCHAR_MAX >> 1) + 1; c !=0 ; c >>= 1)
{
  if (flags & c) 
    Bar(flags&c);
}
于 2010-11-15T10:29:00.257 に答える
0

「きれい」ではない方法がありますが、機能します。

(result & 1)   && corners.push_back(1);
(result & 2)   && corners.push_back(2);
(result & 4)   && corners.push_back(3);
(result & 8)   && corners.push_back(4);
(result & 16)  && corners.push_back(5);
(result & 32)  && corners.push_back(6);
(result & 64)  && corners.push_back(7);
(result & 128) && corners.push_back(8);

C++ 言語のほとんど知られていない機能であるブール値のショートカットを使用します。

于 2010-11-15T00:53:25.863 に答える