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

考虑到这个算法明显的二次复杂度，这里的性能问题并不让我感到惊讶。

目前尚不清楚getId(). 为了清楚起见，假设getId()返回一个IdType类，并且mxExtents是一个类的容器ExtentsType。

如果IdType实现了严格的弱排序（这意味着它还实现operator<了 ，除了operator==），并且您相信如果返回比较次数，您将获得更好的性能IdType，那么我建议创建一个

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

现在lookup通过进行单次传递mxExtents、将每个值的IdType和指向原始实例的指针ExtentsType插入到多重映射中来填充。插入操作将具有对数复杂性，然后在插入所有内容后，单次遍历 multimap 容器将使获取ExtentsType具有相同 . 的所有实例变得微不足道IdType。由于原始插入操作具有对数复杂性，因此我预计第一次比较的总数会少得多。

当然，第二遍将具有线性复杂性，但在我看来，这似乎是首先尝试的最容易实现的目标，看看这是否解决了您怀疑的瓶颈。

另一个潜在的变化是使用 astd::multiset而不是 a std::multimap，带有自定义比较器类。这将使得可以根据每个实例ExtentsType与其内部IdType实例之间的内部关系采用一些额外的优化，以消除这里发生的许多内部复制/移动构造。它继承了原始算法的二次复杂度（并且也可以通过切换到多重映射相应地降低，并可能通过使用自定义多重比较器完全消除）。

于 2016-01-15T12:20:40.720 回答