2

假设我有一个具有多个内核的 CPU，我想在其上找到哪些球体正在接触。每个球体连接的任何一组球体（即它们都接触该组中的至少一个球体）称为“组”，并将被组织成一个向量，在下面的示例中，“group_members” ”。为了实现这一点，我目前正在使用一个相当昂贵的操作，在概念上看起来像这样：

vector<Sphere*> unallocated_spheres = all_spheres; // start with a copy of all spheres
vector<vector<Sphere*>> group_sequence; // groups will be collected here

while (unallocated_spheres.size() > 0U) // each iteration of this will represent the creation of a new group
{
    std::vector<Sphere*> group_members; // this will store all members of the current group
    group_members.push_back(unallocated_spheres.back()); // start with the last sphere (pop_back requires less resources than erase)
    unallocated_spheres.pop_back(); // it has been allocated to a group so remove it from the unallocated list

    // compare each sphere in the new group to every other sphere, and continue to do so until no more spheres are added to the current group
    for (size_t i = 0U; i != group_members.size(); ++i) // iterators would be unsuitable in this case
    {
        Sphere const * const sphere = group_members[i]; // the sphere to which all others will be compared to to check if they should be added to the group
        auto it = unallocated_spheres.begin();
        while (it != unallocated_spheres.end())
        {
            // check if the iterator sphere belongs to the same group
            if ((*it)->IsTouching(sphere))
            {
                // it does belong to the same group; add it and remove it from the unallocated_spheres vector and repair iterators
                group_members.push_back(*it);
                it = unallocated_spheres.erase(it); // repair the iterator
            }
            else ++it; // if no others were found, increment iterator manually
        }
    }

    group_sequence.push_back(group_members);
}

有没有人有任何建议来提高这段代码在墙上时间方面的效率？我的程序在这些循环中花费了很大一部分时间，任何关于如何在结构上改变它以使其更高效的建议都将不胜感激。

请注意，由于这些是球体，“IsTouching()”是一个非常快速的浮点运算（比较两个球体的位置和半径）。它看起来像这样（注意 x、y 和 z 是球体在欧几里得维度中的位置）：

// input whether this cell is touching the input cell (or if they are the same cell; both return true)
bool const Sphere::IsTouching(Sphere const * const that) const
{
    // Apply pythagoras' theorem in 3 dimensions
    double const dx = this->x - that->x;
    double const dy = this->y - that->y;
    double const dz = this->z - that->z;

    // get the sum of the radii of the two cells
    double const rad_sum = this->radius + that->radius;

    // to avoid taking the square root to get actual distances, we instead compare 
    // the square of the pythagorean distance with the square of the radii sum
    return dx*dx + dy*dy + dz*dz < rad_sum*rad_sum;
}
4

1 回答 1

2

有没有人有任何建议来提高这段代码在墙上时间方面的效率？

改变算法。低级优化对你没有帮助。（尽管如果您移出group_members循环，while您将获得非常小的加速）

您需要使用空间分区（bsp-tree、oct-tree）或扫描和修剪算法。

Sweep and prune (wikipedia has links to original article, plus you can google it)可以在单核机器上轻松处理100000个移动和潜在碰撞的球体（好吧，只要你不把它们都放在相同的坐标上）和比空间分区更容易实现。如果您知道碰撞对象的最大可能大小，则扫描和修剪将更适合/更简单地实现。

如果你打算使用扫描和修剪算法，你应该学习插入排序算法。当您处理“几乎”排序的数据时，这种排序算法比几乎任何其他算法都快，扫描和修剪就是这种情况。当然，您还需要一些快速排序或堆排序的实现，但标准库提供了这些。

于 2013-05-28T05:42:50.790 回答