1

並べ替えとスイープのブロードフェーズ システムを作成しようとしていますが、オーバーラップ レポートの段階でパフォーマンスの問題が発生しました。

私のペア レポート コードは、ボトルネックがある場所です。

基本的なアイデアは、すべての軸についてオーバーラップ ペアの一時的なリストを生成し、次に X のすべてのペアについて、ペアが Y と Z に存在するかどうかを確認することです。スタッキング キューブとコンテインメントを処理するために、ペアの生成にいくつかの追加チェックがあります。エッジケース。ペア生成コードは次のとおりです。

//temporary pair generation for X axis
for (unsigned int i = 0; i < mXExtents.size()-1; i++)
{
    if (!mXExtents[i].mMax)
    {
        for (unsigned int j = i + 1; j < mXExtents.size(); j++)
        {
            if (mXExtents[j].mOwner->getID() == mXExtents[i].mOwner->getID())
            {
                break;
            }
            else
            {
                tempXPairs.push_back(new Pair(mXExtents[i].mOwner, mXExtents[j].mOwner));
            }
        }
    }
}
//temporary pair generation for Y axis
for (unsigned int i = 0; i < mYExtents.size()-1; i ++)
{
    if (!mYExtents[i].mMax)
    {
        for (unsigned int j = i + 1; j < mYExtents.size(); j++)
        {
            if (mYExtents[j].mOwner->getID() == mYExtents[i].mOwner->getID())
            {
                break;
            }
            else
            {
                tempYPairs.push_back(new Pair(mYExtents[i].mOwner, mYExtents[j].mOwner));
            }
        }
    }
}
//temporary pair generation for Z axis
for (unsigned int i = 0; i < mZExtents.size()-1; i ++)
{
    if (!mZExtents[i].mMax)
    {
        for (unsigned int j = i + 1; j < mZExtents.size(); j++)
        {
            if (mZExtents[j].mOwner->getID() == mZExtents[i].mOwner->getID())
            {
                break;
            }
            else
            {
                tempZPairs.push_back(new Pair(mZExtents[i].mOwner, mZExtents[j].mOwner));
            }
        }
    }
}

プロファイリングによって検出されたボトルネックは、== 演算子を介してペアを比較するときに発生します。これは、チェック自体のオーバーヘッドではなく、このようなチェックが多数実行されたためだと思われます。

次のように報告コードをペアにします。

    bool found = false;
    //now search Y & Z temp storage for matching pairs
    for (unsigned int i = 0; i < tempXPairs.size(); i++)
    {
        if (tempXPairs[i] != nullptr)
        {
            //search Y first
            for (unsigned int j = 0; j < tempYPairs.size(); j++)
            {
                if (tempYPairs[j] != nullptr)
                {
                    //match found in Y
                    if (*tempXPairs[i] == *tempYPairs[j])
                    {
                        //make a quick copy and stop searching
                        found = true;
                        delete tempYPairs[j];
                        tempYPairs[j] = nullptr;
                        break;
                    }
                }
            }
            //element in Y found
            if (found)
            {
                found = false;
                //search Z temp list for a match
                for (unsigned int j = 0; j < tempZPairs.size(); j++)
                {
                    if (tempZPairs[j] == nullptr)
                        continue;
                    //match in Z found
                    if (*tempXPairs[i] == *tempZPairs[j])
                    {
                        //if we are at this stage then we have a triple match, so an overlap on all axes.
                        //add the pair to the manager
                        mPairManager->addpair(tempXPairs[i]);
                        //delete extranious pairs
                        delete tempZPairs[j];
                        tempZPairs[j] = nullptr;
                        //clear variables 
                        tempXPairs[i] = nullptr;
                        //and end search
                        break;
                    }

                }
                //not found so get rid of all relevant pairs and move on to next in X list
                delete tempXPairs[i];
                tempXPairs[i] = nullptr;
            }
            else
            {
                delete tempXPairs[i];
                tempXPairs[i] = nullptr;
            }
        }
    }
    //finally clear temp storage
    for (unsigned int i = 0; i < tempXPairs.size(); i++)
    {
        if (tempXPairs[i] != nullptr)
        {
            delete tempXPairs[i];
        }
    }
    for (unsigned int i = 0; i < tempYPairs.size(); i++)
    {
        if (tempYPairs[i] != nullptr)
        {
            delete tempYPairs[i];
        }
    }
    for (unsigned int i = 0; i < tempZPairs.size(); i++)
    {
        if (tempZPairs[i] != nullptr)
        {
            delete tempZPairs[i];
        }
    }

私がソートとスイープ/スイープとプルーンで読んだ資料は、重複ペアの高速検索に対処する高速な方法、または実際には、効率的な方法で同等のペアを他の軸で検索する方法について詳しく説明していません。明らかに何かが足りないので、何か助けていただければ幸いです。

4

1 に答える 1

1

このアルゴリズムの明らかな 2 次複雑さを考えると、パフォーマンスの問題はここでは驚くことではありません。

どのクラスまたは POD が によって返されているかは明確ではありませんgetId()。わかりやすくするために、 がクラスをgetId()返し、がクラスのコンテナであるとしましょう。IdTypemxExtentsExtentsType

がIdType厳密な弱い順序付けを実装しており (つまりoperator<、 に加えて が実装されていることを意味します)、比較の数が返されoperator==た場合にパフォーマンスが向上すると思われる場合は、IdType

 std::multimap<IdType, ExtentsType *> lookup;

次にlookup、 を 1 回パスしmxExtents、各値の を挿入IdTypeし、 の元のインスタンスへのポインタをマルチマップに挿入しますExtentsType。挿入操作は対数的な複雑さを持ち、すべてを挿入した後、マルチマップ コンテナーを 1 回パスするだけExtentsTypeで、同じのすべてのインスタンスを簡単に取得できますIdType。元の挿入操作は対数的な複雑さを持っていたため、最初のパスでの比較の総数ははるかに少なくなると予想されます。

もちろん、2 番目のパスには線形の複雑性がありますが、これは最初に試して、疑わしいボトルネックが修正されるかどうかを確認するのに最も簡単な方法のように思えます。

もう 1 つの潜在的なバリエーションは、カスタム コンパレータ クラスでのstd::multiset代わりにを使用することです。これにより、それぞれとその内部インスタンスstd::multimap間の内部関係に基づいて、いくつかの追加の最適化を採用して、ここでも発生している多くの内部コピー/移動構造を排除することが可能になります。これは、元のアルゴリズムの二次複雑性を継承します (また、マルチマップに切り替えることでそれに応じて削減され、カスタム マルチセット コンパレータを使用することで完全に排除される可能性もあります)。ExtentsTypeIdType

于 2016-01-15T12:20:40.720 に答える