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.34 亿个体素。我正在对每个体素进行计算（嗯，不完全是，但我不会详细介绍，因为它在这里无关紧要），这是很多计算。我需要每帧执行这些计算。每个函数调用的任何速度提升都将有助于这些计算量。为了给你一个想法，我的算法（在某些时候）需要确定浮点数是负数、正数还是零（在一些错误内）。我在那里有 if 语句，并且大于/小于检查。我用一个快速的 float to int 函数替换了它，并缩短了四分之一秒。目前，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

黑客的喜悦，第一页：

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

有一种方法，它不是“漂亮”，但它有效。

(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 回答
0

我在 OpenTTD 代码中注意到了类似的算法。事实证明它完全没用：不分解这样的数字会更快。相反，用vector<>对字节位的迭代替换你现在拥有的迭代。这对缓存更加友好。

IE

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 回答