2

いくつかのコアを備えた CPU があり、どの球が接触しているかを調べたいとします。各球が接続されている (つまり、すべてがセット内の少なくとも 1 つの球に接触している) 球のセットは「グループ」と呼ばれ、以下の例では「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()" は非常に高速な浮動小数点操作です (2 つの球の位置と半径を比較します)。次のようになります (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 (ウィキペディアには元の記事へのリンクがあり、Google で検索できます) は、シングルコア マシンで 100000 個の移動球と衝突する可能性のある球を簡単に処理できます (すべてを同じ座標に配置しない限り)。スペースパーティショニングよりも実装が少し簡単です。衝突するオブジェクトの最大可能サイズがわかっている場合は、スイープとプルーニングがより適切で実装が簡単になります。

スイープ アンド プルーン アルゴリズムを使用する場合は、挿入ソートアルゴリズムを学習する必要があります。このソート アルゴリズムは、「ほぼ」ソートされたデータ (スイープ アンド プルーンの場合) で作業する場合、他のどのアルゴリズムよりも高速です。もちろん、クイックソートまたはヒープソートの実装も必要ですが、標準ライブラリがそれを提供します。

于 2013-05-28T05:42:50.790 に答える