c++ - c++算法:搜索 'list'的子集，无序

更新:我的坏。这不是双重减速的原因。我还有其他错误。

C++ MFC。 Visual Studio 12。

我正在尝试在绘制循环内优化性能。我有我所有对象的列表(ListAll)，可以说它有300个对象，所有对象都有唯一的ID。我有第二个需要呈现的ID的list(ListNow)，大小为100。ListNow中的所有值都有关联的对象存储在ListAll中。

当前，ListAll是CMap ，而ListNow是CArray 。

// this is the slower, current method
for (int i = 0; i < ListNow.GetSize(); i++)
{
    UINT id = ListNow.GetAt(i);
    if (ListAll->Lookup(id, object))
    {
        object->draw();
    }
}

过去我只有ListAll(CMap)，并且对其中的每个对象都调用了draw()。它只有我想绘制的100张，每当我切换绘制的内容时，我都会“重建”它。

// this is the faster, old method
POSITION pos = ListAll->GetStartPosition();
while (pos)
{
    ListAll->GetNextAssoc(pos, id, object);
    object->Draw();
}

从技术上讲，这两种算法都以O(n)的速度执行...但是简单地将CMap::Lookup函数添加到循环中，所需时间增加了一倍。我已经将我的CMap大小正确设置为一个质数，该质数大于CMap中的对象数。列表大小超过300,000或更大的列表会明显降低速度。

我切换到该系统，以便可以将所有对象存储在绘制列表中，并可以使用相同的对象列表在不同窗口之间绘制的内容之间快速交换。大幅切换时，这可以加快时间，但会降低每个单独的绘图调用的速度。现在不能切换回去，我们知道它会稍微降低每次抽奖的速度，但幅度不会太大。放慢速度肯定是在我向您展示的代码中，因为当我切换回绘制所有内容(删除查找)时，它可以节省一半的时间。

我提高性能的唯一想法是将LastDrawn对象指针记录在一个列表中，并告知函数是否需要更改(调用lookup())，或者是否可以简单地重用最后绘制的对象(GetNext())。自从90％的时间以来，通话之间没有任何变化。

有谁能比这更快的解决方案？我梦想着一个棘手的位屏蔽解决方案，以某种方式产生我想要的对象指针，我不知道。在这一点上任何事情都会有所帮助。

最佳答案

如果将Object的指针而不是其ID存储到ListNow中，似乎可以解决问题。