我编写的程序需要检查二维数组中的数百万个点,以查看它们是否不为空。这是我正在使用的代码:
Particle *particleGrid[1920][1080];
bool Sensor::checkForParticle(int x, int y) {
if (x > 1920 || x < 0) return 0;
if (y > 1080 || y < 0) return 0;
if (mainController->particleGrid[x][y] != NULL) {
return 1;
}
return 0;
}
这个函数在整个应用程序中使用最多的CPU(~70%的应用程序CPU使用率是由于这个函数),甚至比我实现的Bresenham线绘制算法还要多(示例函数在Bresenham算法生成的线的每个点上调用)。是否有更节省 CPU 的方法来执行空检查操作?
如果在循环中调用它,您可以在不检查参数的情况下逃脱。 当您检查内存位置中的数据时,它也会更快,这将减少缓存命中。
如果您与无符号文本进行比较,您可以免费获得针对 0 的检查,因为负数在转换为无符号时最终会非常大。此外,您不需要所有这些如果:
bool Sensor::checkForParticle(int x, int y)
{
return (x < 1920u) && (y < 1080u) // note both "u" suffixes for unsigned
&& (mainController->particleGrid[x][y] != NULL);
}
顺便问一下,为什么你的数组按列主顺序排列?您的外环是在 x 还是 y 上?如果它们在 y 上,切换到 row-major 将大大提高效率,因为缓存友好性:
Particle *particleGrid[1080][1920];
bool Sensor::checkForParticle(int x, int y)
{
return (x < 1920u) && (y < 1080u)
&& (mainController->particleGrid[y][x] != NULL); // note switched order
}
如果 2D 数组很稀疏,这样的东西可以帮助您加快紧密循环的速度:
Particle *particleGrid[1920][1080];
// somewhere before your tight loop
std::map<std::pair<unsigned int, unsigned int>, Particle*> createCache()
{
std::map<std::pair<unsigned int, unsigned int>, Particle*> cache;
for (unsigned int i = 0; i < 1920; ++i)
{
for (unsigned int j = 0; j < 1080; ++j)
{
if (mainController->particleGrid[i][j])
{
std::pair<unsigned int, unsigned int> coord = std::make_pair(i, j);
cache[coord] = mainController->particleGrid[i][j];
}
}
}
return cache;
}
// then this is called in your tight loop
bool Sensor::checkForParticle(unsigned int x, unsigned int y, const std::map<std::pair<unsigned int, unsigned int>, Particle*>& cache)
{
std::pair<unsigned int, unsigned int> coord = std::make_pair(x, y);
return cache.find(coord) != map.end();
}
如果它不稀疏,这将根本无济于事。
第 1 步:将一致性检查提升到循环之外:
bool Sensor::uncheckedCheckForParticle(int x, int y) {
return mainController->particleGrid[y][x];
}
如果你真的需要防止草率的编程,你可以assert()
函数和/或保护呼叫站点。我敢打赌,这将大大提高性能。
第 2 步:使现在微不足道的函数inline
。
您可以将数组从二维展平为一维(遗憾的是,这可能需要在代码中的其他地方进行重构):
Particle *particleGrid[1920 * 1080];
bool Sensor::checkForParticle(int x, int y) {
return (mainController->particleGrid[x * 1080 + y] != NULL)
}