3

我正在开发基于客户端-服务器图块的游戏。客户端保存 3 维数据，std::vector并在每一帧中将其内容与服务器发送的内容进行比较（我std::vector在客户端有一个单独的内容，其中填充了服务器发送的数据）。

现在客户端的地图由 15x11 个图块组成，每个图块包含大约 10 个放置在其上的对象的数据，所以我在 a 中得到 15*11*10 = 1650 个元素 std::vector。

我正在比较两个std::vectors 中的数据，如果有变化，我会创建新对象/删除对象/移动对象，具体取决于差异。我就是这样做的：

std::vector<IdAndPosition> clientIds; 
std::vector<IdAndPosition> serverIds;

// Fill client ids
for(unsigned int i = 0; i < m_tiles.size(); i++)
{
    for(unsigned int j = 0; j < m_tiles[i].size(); j++)
    {   
        for(unsigned int s = 0; s < m_tiles[i][j].getObjects().size(); s++)
        {
            clientIds.push_back(IdAndPosition(m_tiles[i][j].getObjectAtPosition(s)->getId(), i, j, s));
        }
    }
}

// Fill server ids
for(unsigned int i = 0; i < g_gameStateData.m_gameObjects.size(); i++)
{
    for(unsigned int j = 0; j < g_gameStateData.m_gameObjects[i].size(); j++)
    {   
        for(unsigned int s = 0; s < g_gameStateData.m_gameObjects[i][j].size(); s++)
        {
            serverIds.push_back(IdAndPosition(g_gameStateData.m_gameObjects[i][j][s].second, i, j, s));
        }
    }
}

for (int i = 0; i < serverIds.size(); i++)
{
    IdAndPosition& serverId = serverIds[i];

    bool found = false;
    for(int j = 0; j < clientIds.size(); j++)
    {
        IdAndPosition& clientId = clientIds[j];

        found = serverId.id == clientId.id;
        if(found)
            break;
    }
    if(!found)
    {
        // If not found, create that object
                        // tileX        // tileY
        m_tiles[serverId.pos[0]][serverId.pos[1]].addObjectAtPosition(
            TGameObjectFactory::createGameObject(g_gameStateData.m_gameObjects[serverId.pos[0]][serverId.pos[1]][serverId.pos[2]].first),   // Game object
            serverId.pos[2]                                                                                                                 // Position at stack
        );

        // And set it's individual id
        m_tiles[serverId.pos[0]][serverId.pos[1]].getObjectAtPosition(serverId.pos[2])->setId(g_gameStateData.m_gameObjects[serverId.pos[0]][serverId.pos[1]][serverId.pos[2]].second);
    }
}

for (int i = 0; i < clientIds.size(); i++)
{
    IdAndPosition& clientId = clientIds[i];

    bool found = false;
    for(int j = 0; j < serverIds.size(); j++)
    {
        IdAndPosition& serverId = serverIds[j];

        found = serverId.id == clientId.id;
        if(found)
            break;
    }
    if(!found)
    {
        // If not found, create empty object at this position
                        // tileX        // tileY
        m_tiles[clientId.pos[0]][clientId.pos[1]].addObjectAtPosition(
            TGameObjectFactory::createGameObject(NO_GAME_OBJECT_ID),        // Empty game object (we're removing deprecated one)
            clientId.pos[2]                                                 // Position at stack
        );
    }
}

问题是由于在调试模式下调用该函数（从 ~90 到 ~20 fps），我的性能大幅下降。我知道每帧都要经过大量数据，但我不知道如何设计它以使其不那么慢。

我在 Visual Studio 2012 中使用了性能分析来找出导致最大性能下降的确切原因，我得到了这个结果： 在此处输入图像描述

所以看起来[] operator是std::vector主要原因。

4

2 回答 2

3

您正在对其进行性能分析的代码看起来像是对每个项目进行线性 O(n) 搜索，从而使整个事情成为 O(n^2)。

我真的不明白你想要实现什么，但原因不是因为 std::vector 的操作符很慢，而是因为你这样做的次数太多了。

我建议首先将您的所有 clientIds 放在一个地图中，这会将订单减少到 O(nlogn)。可能还需要进行其他优化，例如，如果您可以提供帮助，请不要查看外部地图中的每个元素。

for(int j = 0; j < serverIds.size(); j++)
{
    IdAndPosition& serverId = serverIds[j];

    found = serverId.id == clientId.id;
    if(found)
        break;
}
于 2013-02-21T09:59:56.407 回答
3

（在我的 MSVC++ 中）的调试版本中有边界检查，[]它在发行版中被删除，这可能是它相对如此之高的原因。

这是我看到的代码。

const_reference operator[](size_type _Pos) const
        {   // subscript nonmutable sequence
 #if _ITERATOR_DEBUG_LEVEL == 2
        if (size() <= _Pos)
            {   // report error
            _DEBUG_ERROR("vector subscript out of range");
            _SCL_SECURE_OUT_OF_RANGE;
            }

 #elif _ITERATOR_DEBUG_LEVEL == 1
        _SCL_SECURE_VALIDATE_RANGE(_Pos < size()); 
 #endif /* _ITERATOR_DEBUG_LEVEL */

        return (*(this->_Myfirst + _Pos));
        }

几乎每一行都在发行版中消失了，除了最后一个..

于 2013-02-21T10:00:28.150 回答