代码之家 › 专栏 › 技术社区 › dlras2

优化象限选择

bit-manipulation optimization c#

dlras2 · 技术社区 · 14 年前

我正在研究一种数据结构,它将项目细分为象限,我发现的瓶颈之一是我选择点象限的方法。诚然,它相当简单,但它被多次调用,加起来就是这样。我想应该有一种有效的方法来把它变成我想要的东西,但我想不起来。

private int Quadrant(Point p)
{
    if (p.X >= Center.X)
        return p.Y >= Center.Y ? 0 : 3;
    return p.Y >= Center.Y ? 1 : 2;
}

Center 属于类型 Point ,坐标为 ints . 是的,我运行了一个代码配置文件,不,这不是过早的优化。

因为这只在内部使用,我想我的象限没有有待在 Cartesian order ,只要它们在0-3之间。

4 回复 | 直到 10 年前

ruslik 14 年前

C/C++中最快的方法是

(((unsigned int)x >> 30) & 2) | ((unsigned int)y >> 31)

(30/31或62/63,取决于int的大小)。这将按顺序0、2、3、1给出象限。

为lbushkin编辑:

(((unsigned int)(x - center.x) >> 30) & 2) | ((unsigned int)(y-center.y) >> 31)

LBushkin 14 年前

我不知道您可以在C中使此代码显著更快。然而,您可能能够做的是,查看您如何处理点,并查看是否可以避免对该方法进行不必要的调用。也许你可以创造一个 QuadPoint 存储点所在象限的结构(在您计算一次之后),这样您就不必再这样做了。

但是,不可否认,这取决于您的算法在做什么,以及是否可以存储/记忆象限信息。如果每一点都是独一无二的,这显然没有帮助。

Stanislav Pankevich 10 年前

我刚刚听说了产生0,1,2,3象限结果的解决方案,其顺序正确:

#define LONG_LONG_SIGN (sizeof(long long) * 8 - 1)

double dx = point.x - center.x;
double dy = point.y - center.y;

long long *pdx = (void *)&dx;
long long *pdy = (void *)&dy;

int quadrant = ((*pdy >> LONG_LONG_SIGN) & 3) ^ ((*pdx >> LONG_LONG_SIGN) & 1);

此解用于双类型的x,y坐标。

我已经对这个方法和原始问题中带有分支的方法做了一些性能测试:我的结果是 分支方法总是快一点(目前我有稳定的160/180关系) ,所以我更喜欢分支方法而不是按位操作的方法。

更新

如果有人感兴趣,这三种算法都被合并到 EKAlgorithms C/Objective-C repository 作为“笛卡尔象限选择”算法:

原始分支算法
@ruslik从接受的答案中选择位算法。
另一个由我的一个同事按位提升的算法,比第二个算法慢一点,但按正确的顺序返回象限。

这里的所有算法都经过了优化,可以使用双类型点。

性能测试表明 一般来说,第一个分支算法是赢家 在MacOSX上,尽管在Linux机器上,我们确实看到了第二种算法的执行速度比分支算法快一点。

因此,一般的结论是坚持使用分支算法,因为按位版本不提供任何性能增益。

Peter G. 14 年前

我的第一个尝试是去掉嵌套条件。

int xi = p.X >= Center.X ? 1 : 0;
int yi = p.Y >= Center.Y ? 2 : 0;
int quadrants[4] = { ... };
return quadrants[xi+yi];

如果允许对象限重新编号,则象限中的数组查找是可选的。我的代码仍然需要两个比较,但它们可以并行进行。

我为任何C错误预先道歉,因为我通常编码C++。

当两个无符号31位坐标存储在一个64位无符号长变量中时,可能会有更高效的方法。

// The following two lines are unnecessary
// if you store your coordinated in unsigned longs right away
unsigned long Pxy = (((unsigned long)P.x) << 32) + P.y;
unsigned long Centerxy = (((unsigned long)Center.x) << 32) + Center.y;

// This is the actual calculation, only 1 subtraction is needed.
// The or-ing with ones hast only to be done once for a repeated use of Centerxy.
unsigned long diff = (Centerxy|(1<<63)|(1<<31))-Pxy;
int quadrant = ((diff >> 62)&2) | ((diff >> 31)&1);

后退一步,可能会有不同的解决方案。不要立即将数据结构拆分为象限,而是在两个方向交替排列。这也是在相关的 Kd-tree