c++ - 在 C++ 中对大量元素进行分组的最快方法

Question

我需要一种方法来快速将大量连接(目前为 300k)分组到组中，每个组都有允许的最大元素数(目前为 14k)，并且同一组中的所有连接不能连接到同一个观点。基本上，每个连接都在两点之间，我需要将它们分组到桶中，桶中的连接不共享一个点。希望这是有道理的。

这是我目前所拥有的，它有效但速度相当慢:

for (size_t i = 0; i < ConnectionGroups.size(); i++)
{
    auto& group = ConnectionGroups[i];
    if (group.size() < MaxConnectionGroupSize) // Has room for us...
    {
        int validGroupIdx = i;
        for (size_t gIdx = 0; gIdx < group.size(); gIdx++)
        {
            const auto groupConnection = ConnectionsQuickAccess[group[gIdx]];

            // Are we directly connected to one of the Connections in this group by one degree...
            if (Connection.Point1 == groupConnection->Point1 || Connection.Point1 == groupConnection->Point2 ||
                Connection.Point2 == groupConnection->Point1 || Connection.Point2 == groupConnection->Point2)
            {
                validGroupIdx = -1;
                break; // We are, check the next group
            }
        }

        if (validGroupIdx != -1)
        {
            ConnectionGroups[i].push_back(Connection.Slot);
            Connection.Group = i;
            return;
        }
        else
            continue;
    }
}

// All groups are full, create a new group
vector<int> newGroup;
newGroup.push_back(Connection.Slot);
ConnectionGroups.push_back(newGroup);

此代码需要 29.68 秒才能完成 30 万个连接，是否有更快的方法？或者可能采用不同的方法？

谢谢!

Answer 1

发布的代码似乎处理了一个连接，即它被调用了 n 次，其中 n 是连接数。该算法显然是 O(n * n):添加新连接所需的时间呈二次方增长 - 这是您通常不希望看到的。

除非内存是主要限制条件，否则我会为每个组简单存储一个包含所有现有端点的散列并检查它，即，按照

for (std:size_t i(0); i != ConnectionGroups.size(); ++i) {
    if (ConnectionGroups[i].size () < MaxConnectionGroupSize)
        && !ConnectionGroups[i].usesEndPoint(Connection.Point1)
        && !ConnectionGroups[i].usesEndPoint(Connection.Point2)) {
        ConnectionGroups[i].addEndPoint(Connection.Point1);
        ConnectionGroups[i].addEndPoint(Connection.Point2);
        ConnectionGroups[i].addConnection(Connection);
    }
}

显然，ConnectionGroups[i] 将是连接和使用相应函数访问的端点散列的组合。