关于TList效率的讨论
来自：aimingoo, 时间：2001-10-18 15:41:00, ID：679634
好了，我来给一段代码吧。哈哈~~~~~~~~
最近在写ISAPI Filter，为了实现好的性能，我想要以尽可能快的速度操
作TList。到底要以什么速度呢？哈哈，大家看看下面的代码就明白了。
:)
1. 问题提出：如何更快速地从TList中删除部分连续的Item。
有这样的一段代码：
var p : pChar = 'abcdefgh';
procedure TestDelFromTList;
var t1 : TList;
i : integer;
maxI : integer;
begin
t1 := tlist.create;
t1.count := 100000;
for i:=0 to t1.count-1 do t1[i] := p;
maxI := t1.count-10-1; //最后一个结点
for i:= maxI downto 10 do t1.delete(i);
//for i:=10 to t2.count-10-1 do t2.delete(10);
end;
这段代码是初始化一个100000个结点的List，然后删除其中的第10个到倒数第10个。这段
代码是逆向的，这样的删除速度比较快。如果换成正向删除(已经注释掉)，则速度就慢得
非常多了。
这样的删除是正常的算法。我用测效率的程序测试过，逆向删除算法的耗时是21.66个毫秒，
则正向删除的耗时却能达到58099.02个毫秒。速度慢了2680倍！！！
但这样就很快了么？不是！我认为就算是逆向删除的速度也并不是快的。
分析TList这个类的源码，我们可以看到，它是这样写的(我加入了注释)：
procedure TList.Delete(Index: Integer);
var
Temp: Pointer;
begin
if (Index < 0) or (Index >= FCount) then Error(@SListIndexError, Index); //判定Index值是否超界
Temp := Items[Index]; //取待删除结点
Dec(FCount); //Count减一
if Index < FCount then System.Move(FList^[Index + 1], FList^[Index],(FCount - Index) * SizeOf(Pointer)); //将待删除结点后的Buffer提前
if Temp <> nil then Notify(Temp, lnDeleted); //发通告
end;
由于在TList类是将全部的结点指针存放在FList这个动态数组的指针中，所以只需
要将Index+1之后的内存块向前移4个字节，即SizeOf(Pointer)，即可实现Index结
点的删除。
但是，如果使用这样来删除成批连续的(N个)结点，则要实现N次system.move()操作，
操作的内存块的大小决定了system.move()操作的耗时，而Index值越小的的结点在FList
中越靠前，则system.move()要操作的内存块也就越大。这就是我认为上述成批删除效
率不高的原因，也是正向删除比逆向删除的耗时慢了慢了2680倍的原因。
对于成批删除，理想的算法是从index+len结点开始位置，向前移动count-index-len个
结点，这样，就能够一次完成全部的结点移动，实现删除操作。
这个思路非常好，至少我认为是这样。为此，我实现了下面的代码：
procedure CutList(aList:TList; left,len:integer);
begin
with aList do begin
System.Move(List^[left+len], List^[left], (Count-left-len) * SizeOf(Pointer));
count := count-len;
end;
end;
这段代码的功能是在TList.List这个Buffer中，将删除后的剩余结点直接移动到Left
这个位置上，从而完成全部的移动操作。
然后，我们再设count := count-len;来使用个数减少，从而完成了成批量的删除。
好的，如果一切正常，算法的速度将大幅度提升！OHHH，美妙的想法！
但是，真的是这样么？我再用效率测试程序来测试了一轮，结果是这样的：
测试数据为10万个结点，则逆向删除算法耗时为20.56毫秒，CutList()函数耗时9.69毫秒；
测试数据为100万个结点，则逆向删除算法耗时为209.13毫秒，CutList()函数耗时98.01毫秒。
速度比逆向算法提高了一倍，而且应该注意到，CutList()的耗时仍然随数据量的增大而等比
例的增大！！！而事实上，从CutList()函数的实现来看，数据量增大，算法耗时应该只增加
极少才对。
为什么呢？？？要知道，只加快一倍速度的CutList()，并不是我所想要的！！！
再次分析TList类的实现代码，发现count接口实现时，是用setCount来写值，即CutList()函
数中，
count := count-len;
一行的调用，实际上将调用TList.setCount(count-len);
而TList.setCount()的实现代码如下：
procedure TList.SetCount(NewCount: Integer);
var
I: Integer;
begin
if (NewCount < 0) or (NewCount > MaxListSize) then Error(@SListCountError, NewCount);
if NewCount > FCapacity then SetCapacity(NewCount);
if NewCount > FCount //如果要增加Count的值，则调用Fillchar()来填充FList这个Buffer
//如果是要减少Count的值，则用for循环调用Delete()来删除结点
then FillChar(FList^[FCount], (NewCount - FCount) * SizeOf(Pointer), 0)
else for I := FCount - 1 downto NewCount do Delete(I);
FCount := NewCount;
end;
请注意看我在上面注释！OH！事实上，setCount这个操作仍然将调用Delete()来删除各个结点
(注意，Borland为了提高这个删除速度，也使用了逆向删除的算法来实现对Delete()的调用)。
所以，我们并不能在CutList()中得到更好的算法效率！--尽管，我们已经只要，只需要将count
设成指定值即可，而并不需要再来一次成批的Delete()！
Count属性是可读写的，它的定义是这样的：
TList = class(TObject)
private
FList: PPointerList;
FCount: Integer;
...
protected
...
procedure SetCount(NewCount: Integer);
...
public
...
property Count: Integer read FCount write SetCount;
...
property List: PPointerList read FList;
end;
我们看到，Count读是直接读FCount的值，而写操作是调用SetCount()函数。那么，我们想一想，
既然"Count读是直接读FCount的值"，那么，Count的地址是不是也直接指向FCount呢？？？
下面的测试代码可以证明这一点：
program testFixCount;
uses classes, Dialogs, sysUtils;
var t : TList;
pCount : ^Integer;
begin
t := TList.create;
t.Count := 10000;
pCount := @t.Count;
pCount^ := 10;
showMessage(t.Count);
end.
我们看到，我们已经成功地修改了FCount的值，而没有通过TList.setCount()。^-^
--事实上，我们已经突破了Delphi在"类"封装时对FCount的保护，我们能够直接访
问Delphi的类中的私有属性了！！！:)
接下来，我们可以将curList()函数修改一下下了：
procedure CutList(aList:TList; left,len:integer);
var pCount : ^Integer;
begin
with aList do begin
System.Move(List^[left+len], List^[left], (Count-left-len) * SizeOf(Pointer));
//count := count-len;
pCount := @Count;
pCount^ := count-len;
end;
end;
OK! 我再次用那个可爱的效率测试工具测试了一下下，结果，哈哈，漂亮！--
测试数据为10万个结点，则逆向删除算法耗时仍为20.56毫秒，准确地说是20333.25个微秒，而
新CutList()函数耗时仅为1.08个微秒；
测试数据为100万个结点，则逆向删除算法耗时为212.67毫秒(212668.22微秒)，而这种情况下，
CutList()函数耗时仅为1.26个微秒，比10万个结点略略多了一点儿！:)
快了NNNNNNN倍！！！
哈哈，这就是我要的结果！一个不会随数据量增加而变慢的cutList()!
将全部测试代码写到下面：
program cutListFun;
uses windows, classes;
procedure CutList(aList:TList; left,len:integer);
var pCount : ^Integer;
begin
with aList do begin
System.Move(List^[left+len], List^[left], (Count-left-len) * SizeOf(Pointer));
pCount := @Count;
pCount^ := count-len;
end;
end;
var
t1,t2 : TList;
p : pChar = 'abc';
oldTick : DWORD;
i,maxI : integer;
begin
t1 := TList.create;
t2 := TList.create;
t1.count := 1000000;
t2.count := 1000000;
for i:=0 to t1.count-1 do t1[i] := p;
maxI := t1.count-10-1;
oldTick := GetTickCount;
for i:= maxI downto 10 do t1.delete(i);
writeln('need:', GetTickCount-oldTick, 'ms');
oldTick := GetTickCount;
CutList(t2,10, t2.count-20);
writeln('need:', GetTickCount-oldTick, 'ms');
end.
没有经过仍何优化，这段代码仅787个字节。^-^，如果按"有效字节数"来数，相信
可以低于512字节。
其它：
---------------
1. 这段代码主要实现cutList()函数，用于极快速地从TList中删除一批连续结点。
2. 函数主要技巧是通过TList.list属性操作FList，使用system.move()快速移除结点。
3. 函数最重要的是使用@TList.Count有效地突破Delphi的类封装，直接访问和写私有域FCount。
4. 函数提供的突破类方法的思路可以进一步地扩展，可以通过突破一个私有域来访问该类所有的
域。示例代码如下：
program myTest;
{$APPTYPE CONSOLE}
uses classes, Dialogs, sysUtils;
var
t : TList;
pPrivateStrart : pointer;
pCount,pCapacity : ^Integer;
begin
t := TList.create;
t.Count := 10000;
pPrivateStrart := pointer(@t.List);
pCount := pointer(integer(pPrivateStrart) + sizeof(pointer));
pCapacity := pointer(integer(pCount) + sizeof(integer));
pCount^ := 10;
pCapacity^ := 1000;
writeln('FCount:',t.Count);
writeln('FCapacity:',t.Capacity);
end.
分析：首先，TList的类定义如下，
TList = class(TObject)
private
FList: PPointerList;
FCount: Integer;
FCapacity: Integer;
protected
...
end;
这样，通过取TList.List就取得到FList的地址，同时，也就取得了整个private区的起始
地址，然后，通过指针运算，可以找到FCount和FCapacity的地址。--这得益于Delphi总
是用一个连续内存块来存储一个结构！
5. 由于直接访问私有域的方法超越了Delphi的对象保护，所以，访问私有域可能导致一些
负面影响。比如，直接修改FCount的方法并不会使FList占用的Buffer的空间增大或者减
小，也不会使Capacity的值发生任何变化。而在Delphi对于TList的类封装中，这三者之
间是有联系的。我们必须再加一些代码来维护这种关系，以保证TList类操作的正常。因
此，我们有必要进一步地修改cutList()函数。完整版本的cutList()函数如下(加注释)：
//////////////////////
//需要维护Count与Capacity的关系，请在"pCount^ := count-len;"一行后加入如下代码：
// Capacity := Count;
//上一行代码在本函数的实现中被取消的原因如下：
//由于在TList中，Capacity决定了FList这个Buffer的大小，但在TList的算法实现上，并
//不在Delete()时减小Buffer的大小，多余出来的空间将留给以后的Add()使用，这样可以
//避免频繁的ReallocMem()调用导致效率下降。
//基于上述原因，我们不必要在这里用重设Capacity的方法来实际删除List^所占用的空间。
//但如果用户需要释放cut掉的空间，本行代码是可用的。
//另外，对于其它类中直接访问私有属性的情况，请考虑相关属性的重设。
//////////////////////
procedure CutList(aList:TList; left,len:integer);
var pCount : ^Integer;
begin
with aList do begin
System.Move(List^[left+len], List^[left], (Count-left-len) * SizeOf(Pointer));
pCount := @Count;
pCount^ := count-len;
end;
end;
6. 程序功能的实现重要的在于思想，而代码字节数是次要的。