, (Count-left-len) *
SizeOf(Pointer));
count := count-len;
end;
end;
这段代码的功能是在TList.List这个Buffer中,将删除后的剩余结点直接移动到Left这个位置上,从而完成全部的移动操作。
然后,我们再设count := count-len;来使用个数减少,从而完成了成批量的删除。
好的,如果一切正常,算法的速度将大幅度提升!OHHH,美妙的想法!
但是,真的是这样么?我再用效率测试程序来测试了一轮,结果是这样的:
1. 测试数据为10万个结点,则逆向删除算法耗时为20.56毫秒,CutList()函数耗时9.69毫秒;
2. 测试数据为100万个结点,则逆向删除算法耗时为209.13毫秒,CutList()函数耗时98.01毫秒。
速度比逆向算法提高了一倍,而且应该注意到,CutList()的耗时仍然随数据量的增大而等比例的增大!!!而从CutList()函数的实现来看,数据量增大,算法耗时应该只增加极少才对。
要知道,只加快一倍速度的CutList(),并不是我所想要的!!!但为什么CutList()函数得不到更高的性能呢???
三、 面对私有域FCount,我咬牙切齿!!!
再次分析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()中得到更好的算法效率!——尽管,我们已经只要,仅仅只需要将FCount设成指定值即可,而并不需要再来一次成批的Delete()!
然而,FCount是一个私有域!!!从Delphi对OOP的实现机制来看,我只能通过SetCound()来实现写访问!!!在Classes.pas单元中的这段代码清楚地表明了这一切:
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呢???
OK,且让我们用一段代码来证明它:
program testFixCount;
uses classes, Dialogs, sysUtils;
var t : TList;
pCount : ^Integer;
begin
t := TList.create;
pCount := @t.Count
//取得地址?
ShowMessage(IntToStr(pCount^));
t.Count := 10000;
ShowMessage(IntToStr(pCount^));
end.
很明显,pCount成功地得到了FCount的地址。哈哈,我们既然已经取得了一个变量在内存中的地址,那么,还有什么是不能做的呢???
我们可以很快完成这样的一段代码来测试对FCount私有域的直接写访问:
program testFixCount;
uses classes, Dialogs, sysUtils;
var t : TList;
pCount : ^Integer;
begin
t := TList.create;
pCount := @t.Count;
pCount^ := 10;
showMessage(IntToStr(t.Count));
end.
接下来,我们可以将curList()函数修改一下下了:
procedure CutList(aList:TList
left,len:integer);
var pCount : ^Integer;
begin
with aList do begin
System.Move(List^[left+len], List^
, (Count-left-len) *
SizeOf(Pointer));
//count := count-len;
pCount := @Count;
pCount^ := count-len;
end;
end;
OK! 我再次用那个可爱的效率测试工具测试了一下下,结果,哈哈,漂亮!——
1. 测试数据为10万个结点,则逆向删除算法耗时仍为20.56毫秒,准确地说是20333.25个微秒,而新CutList()函数耗时仅为1.08个微秒;
2. 测试数据为100万个结点,则逆向删除算法耗时为212.67毫秒(212668.22微秒),而这种情况下,CutList()函数耗时仅为1.26个微秒,比10万个结点略略多了一点儿!
快了NNNNNNN倍!!!
这才是我要的结果!一个不会随数据量增加而变慢的CutList()!
五、 突破更多的私有域……
存在的问题是,如果域不提供公用访问接口,那么,也就无法取到它的地址。这种情况下,我们是不是什么也得不到了呢?
仍然参考上述代码上TList的类定义,我们发现,在private域的定义中,FList和FCount被连续定义,从数据结构的角度来看,通常它们在内存中占用连续的空间。事实上,在Delphi中也正是如此处理的。因此,我们只需要得到FList的地址,并用“@List+SizeOf(PPointerList)”,就可以得到FCount的地址了。
我们用下面这段代码来测试不使用TList.Count而直接访问FCount的方法。这意味着,只要我们可以突破一个私有域,我们就可以通过地址计算的方法来突破全部的私有域!
program myTest;
{$APPTYPE CONSOLE}
uses classes, Dialogs, sysUtils;
var
t : TList;
pPrivateStrart : pointer;
pCount,pCapacity : ^Integer;
begin
t := TList.create;
pPrivateStrart := pointer(@t.List);
pCount := pointer(integer(pPrivateStrart) + sizeof(pointer));
pCapacity := pointer(integer(pCount) + sizeof(integer));
t.Count := 10000;
writeln('FCount:',t.Count);
writeln('FCapacity:',t.Capacity);
pCount^ := 10;
pCapacity^ := 1000;
writeln('FCount:',t.Count);
writeln('FCapacity:',t.Capacity);
end.
六、 其它
1. 由于直接访问私有域的方法超越了Delphi的对象保护,所以,访问私有域可能导致一些负面影响。比如,直接修改FCount的方法并不会使FList占用的Buffer的空间增大或者减小,也不会使Capacity的值发生任何变化。而在Delphi对于TList的类封装中,这三者之间是有联系的。我们有必要进一步地修改CutList()函数,再加一些代码来维护这种关系,以保证TList类操作的正常。完整的Cutlist()的实现可以在
http://www.delphibbs.com/delphibbs/dispq.asp?lid=650664
或者我的个人主页
http://www.doany.net/ 或 http://aiming.ynxx.com/
上找到。
2. CutList只实现对TList的连续区间的删除,对于任意Item的成批删除,creation-zy在DelphiBBS上有一段极其精彩的论述。它实现的AdvSoftDelete()函数可以极其快速地处理任意结点的成批删除。我建议你到
http://www.delphibbs.com/delphibbs/dispq.asp?lid=650664
翻阅一下creation-zy对该问题的论述。