c++ 算法 : searching for a subset of a 'list' , 无序

Question

更新:我的错。这不是双重放缓的原因。我还有其他错误。

C++ MFC。 Visual Studio 12。

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

目前，ListAll 是一个 CMap < UINT, UINT, Object*, Object*>，而 ListNow 是一个 CArray< UINT,UINT>。

// 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% 以来，通话之间没有任何变化。

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

Answer 1

如果将对象的指针而不是它们的 ID 存储到 ListNow 中，看来问题将得到解决。