c++ - STL:在海量数据中进行排序和搜索

Question

我有两组点(source 和target)。目标是为每个 source 点在 target 中找到一个唯一的 1:1 最近邻点。

我的尝试按预期进行，但速度慢得离谱。我已经测试了几千点，但在实际场景中点将是数百万。我不是 STL 方面的专家。有什么建议可以优化它吗？

std::vector<UT_Vector3> targetPosVector;
for (auto i = 0; i < targetNumPoints; i++)
{
    auto pos = target->getPos3(i);

    targetPosVector.push_back(pos);
}

std::vector<int> uniqueNeighborVector;
for (auto ptoff = 0; ptoff < sourceNumPoints; ptoff++)
{
    std::vector<std::pair<int, fpreal>> nearpointVector; // neighbor vector in form of "(idx, dist)"

    auto pos = source->getPos3(ptoff);
    for (auto j = 0; j < targetNumPoints; j++)
    {
        fpreal dist = pos.distance(targetPosVector[j]);

        std::pair<int, fpreal> neighbor {j, dist};
        nearpointVector.push_back(neighbor);
    }
    std::sort(nearpointVector.begin(), nearpointVector.end(), [](const std::pair<int, fpreal> &left,
                                                                 const std::pair<int, fpreal> &right)
                                                                { return left.second < right.second; });

    std::vector<int> neighborVector;
    for (auto i : nearpointVector)
    {
        neighborVector.push_back(i.first);
    }

    // trying to imitate Python's next() function
    // uniqueNeighborList[]
    // uneighbor = next(i for i in neighborVector if i not in uniqueNeighborVector)
    // uniqueNeighborVector = set(uniqueNeighborList.append(uneighbor))
    for (auto i : neighborVector)
    {     
        if (std::find(uniqueNeighborVector.begin(), uniqueNeighborVector.end(), i) == uniqueNeighborVector.end())
        {
            int uneighbor = i; // later on binds to the geometry attribute

            uniqueNeighborVector.push_back(i);

            break;
        }
    }
}

哪里:

• source 和target 是Detail Geometry 数据
• distance 是计算两个 vector 之间距离的函数
• getPos3 是获取3-float vector 点位置的函数
• fpreal 又名 64 位 float
• UT_Vector3 是 3-float vector
• sourceNumPoints 和 targetNumPoints 是点数source 和 target 几何体。

Answer 1

正如评论中提到的，在尝试计算数百万个点时，二次复杂度是一个失败。即使您优化了代码，如果方法不改变，二次复杂度也会保持不变。

这听起来像是 R3 中的经典 NN 问题。一个众所周知的方法是使用 k-d trees ，它们允许在 O(n log n) 构造时间和线性空间内进行 O(log n) 查询时间。可以通过各种库寻找实现:nanoflann , kdtree (这些来自快速搜索，我敢肯定还有包含 k-d 树的精心设计的库。)

简短回顾:我会使用 3 维树并在您的目标点集上构建它。然后获取每个源点(一个接一个)并在 O(log n) 时间内找到 3-d 树中最近的邻居，这将导致 O(|source| log |target|) 时间和 O(|目标|) 尺寸。

一个相关question .