有没有更快的TList实现？

Question

我的应用程序大量使用TList，所以我想知道是否有更快或针对特定用例进行优化的替代实现。

我知道RtlVCLOptimize.pas 2.77，它优化了几个TList方法的实现。

但我想知道外面是否还有其他东西。我也不要求它是TList的后代，我只需要TList功能，不管它是如何实现的。

考虑到TList提供的相当基本的功能，这是完全可能的，没有太多的改进空间，但仍然想要验证这一点，因此这个问题。

编辑:在我的特定用例中，没有对列表进行排序。有许多列表，其中包含不同数量的元素。我确实用我自己的类替换了TList，以便记录添加/删除调用的数量和元素的数量。它报告(所有列表的全称)：

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012

我还可以找出单个列表中元素的最大数量是多少。

我没有特别的问题，我只是想知道是否有一种方法可以让它更快，因为有了这些数字，即使是很小的改进也会加起来。

Answer 1

我所知道的关于TList的最大瓶颈之一是对大列表的删除/提取。删除item比删除ItemCount-1慢得多，因为随后会发生内存移动。

例如，在包含65536个元素的列表中：

while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete

for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec

因此，如果您有一个包含数百万个元素的TList，那么删除一个较低的索引项在性能方面可能会耗费大量资源。另外，考虑到没有排序的列表会使查找其中的元素变得非常慢。在大型列表上，IndexOf的速度非常慢。您可能想要考虑保持列表的排序。

此外，考虑到您的项目计数可能非常大，您可能希望考虑使用TList列表来存储您的元素，这将有助于减少我已经提到的删除/提取开销。

Answer 2

看起来你做了很多adds。我不知道有多少列表，但如果您的单个列表变得非常大，您可能希望实现一个增长更快的列表。

看看TList.Grow，当您尝试将一个项添加到其所有数组元素都在使用的列表中时，就会调用它，您将看到它增长了25%。这是为了将内存使用率保持在合理的水平。但是如果你需要非常大的列表，可以创建自己的子类并覆盖Grow，这样在第二行中，它就会显示Delta := FCapacity，而不是Delta := FCapacity div 4。这使得你的列表每次都会增长两倍，这意味着更少的reallocs和更少的副本。

但最要命的可能是所有这些Remove调用。Remove必须先找到项目，然后才能删除它，这涉及到对IndexOf的调用，这是对整个数组的线性扫描。如果你有一个很大的列表，并且你做了很多删除，这会毁了你的性能。

你用这些列表做什么，尤其是那些大的列表？根据您对它们所做的操作，可能会有更好的数据结构用于该作业。

Answer 3

您是否在使用Notify程序？如果没有，请创建您自己的TList实现。由于Notify过程，TList.Clear (在销毁时调用)是一个O(n)操作。TList.Clear方法调用SetCount，而Delete又为它包含的所有项调用Delete，因此将为每个删除的项调用Notify过程。当不需要重写Notify方法时，可以调整SetCount过程使其不调用Delete。这样可以节省15.766.012 - 10.630.000 = 5.136.012 Delete调用的时间。

注:您获得的性能增益永远不会像Mason Wheeler建议的那样，通过对列表进行排序和优化删除过程来获得更大的性能增益。除非列表中包含的项目非常少，并且比较功能需要很长时间。