是否有更快的TList实现？

Question

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

我知道RtlVCLOptimize.pas 2.77,它优化了几种TList方法的实现.

但是我想知道那里还有什么.我也不要求它是TList后代,我只需要TList功能,无论它是如何实现的.

考虑到TList提供的相当基本的功能,完全有可能没有太大的改进空间,但仍然希望验证这一点,因此这个问题.

编辑:在我的特定用例中,没有列表被排序.有很多列表,其中包含了不同数量的元素.我确实用自己的类替换了TList,以便记录添加/删除调用的数量和元素的数量.它报告(所有列表的toatal):

ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012

我还可以找出单个列表中元素数量最多的是什么.

我没有特别的问题,我只是想知道是否有办法让它更快,因为这些数字甚至小的改进会加起来.

Answer 1

我对TList知道的最大瓶颈之一是大型列表中的删除/提取.删除项目[0]比删除项目[计数-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

看起来你做了很多补充.我不知道有多少列表已经传播,但如果您的个人列表变得非常大,您可能希望实现一个增长更快的列表.

看一下TList.Grow,当您尝试将项目添加到其所有数组元素都在使用的列表中时调用,并且您将看到它增长了25%.这是为了将内存使用降低到合理的水平.但是,如果你需要真正的大型列表,请创建自己的后代类并覆盖Grow,以便在第二行中代替Delta := FCapacity div 4它Delta := FCapacity.这使您的列表每次增长两倍,这意味着更少的reallocs和更少的副本.

但是那些可能会杀死你的东西就是那些删除电话.删除必须找到该项才能删除它,这涉及到对IndexOf的调用,这是对整个数组的线性扫描.如果你有一个大的列表并且你正在进行大量删除,那将会扼杀你的表现.

您使用这些列表的是什么,尤其是大型列表？根据您对它们的处理方式,可能会有更好的数据结构.

Answer 3

您使用的是通知程序吗？如果没有,请创建自己的TList实现.由于Notify过程,TList.Clear(在销毁时调用)是O(n)操作.TList.Clear方法调用SetCount,SetCount又为其包含的所有项调用Delete,因此将为每个删除的项调用Notify过程.如果不需要覆盖Notify方法,则可以调整SetCount过程以不调用Delete.这样可以节省15.766.012 - 10.630.000 = 5.136.012删除电话的时间.

注意:根据Mason Wheeler的建议,您获得的性能提升永远不会像排序列表和优化删除过程所获得的性能提升那么大.除非您的列表包含非常少量的项目,并且比较功能需要花费大量时间.