快速访问(排序) TList

Question

我的项目(在Delphi 6上运行！)需要内存分配(TMemoryAllocation)列表，我将其存储在一个对象中，该对象还保存有关分配大小(FSize)和分配是否正在使用(FUsed)的信息。我基本上将它作为一个GarbageCollector，并将其作为一种方法来保持我的应用程序一直在分配/释放内存(并且需要大量的分配/释放位置)。

每当我的项目需要分配时，它会查找列表，以找到符合所需大小的免费分配。为了实现这一点，我使用了一个简单的for循环：

for I := 0 to FAllocationList.Count - 1 do
begin
  if MemoryAllocation.FUsed and (MemoryAllocation.FSize = Size) then
...

我的应用程序运行的时间越长，这个列表就会增长到几千个条目，并且在我非常频繁地运行它(每秒几次)时，它会慢很多。

我正在设法加快这一解决办法。我考虑按分配的大小对TList进行排序。如果我这样做了，我应该使用一些智能的方式访问列表的特定大小，我需要在每次调用。有什么简单的方法吗？

我考虑的另一种方式是拥有两个TLists。一个用于未使用的拨款，一个用于已使用的拨款。这意味着我必须从一个列表中提取TList.Items，然后一直添加到另一个列表中。我仍然需要使用for循环来检查(现在)较小的列表。这条路对吗？

其他建议也是非常欢迎！

Answer 1

你有几种可能性：

• 当然，使用一个经过验证的内存管理器作为FastMM4或一些专门用于多线程应用程序更好规模的其他；
• 重新发明轮子。

如果您的应用程序对内存分配非常敏感，那么可能会有一些关于重新发明轮子的反馈：

• 利用您的块大小(例如，每16字节倍数)，然后保持每个块大小的一个列表--这样您就可以快速地达到好的块“系列”，并且不必将每个块大小存储在内存中(如果它在32字节列表中是自己的，那么它就是一个32字节的块)；
• 如果您需要重新分配，尝试猜测最佳的增长因素，以减少内存复制；
• 按大小对块进行排序，然后使用二进制搜索，这比I := 0计数-1循环要快得多；
• 在列表中保留一组已删除的项目，以便在需要新项目时查找(这样您就不必删除该项目，只需将其标记为空闲--如果列表很大，这将大大加快速度)；
• 不要使用列表(在删除或插入具有大量项的排序项时会出现一些速度问题)，而是使用一个链接列表，用于项和已释放的项。

这显然不是那么简单，所以您可能希望之前查看一些现有的代码，或者只依赖现有的库。我认为您不必在应用程序中编写这个内存分配，除非FastMM4不够快，我对此非常怀疑，因为这是一段很棒的代码！