请教字符串算法,很有意思的问题 (300分)

L

LiChaoHui

Unregistered / Unconfirmed
GUEST, unregistred user!
也不知道楼上是怎么测试的,我用了更高精度的测试
下面是多次测试的结果和源代码
计算机配置: PII350 RAM256
测试结果:
第一次
Time set ops: 2665771
Time compare: 2003729
第二次
Time set ops: 2687311
Time compare: 2019305
第三次
Time set ops: 2680279
Time compare: 2025879
第四次
Time set ops: 2704012
Time compare: 2020918

源代码
procedure TForm1.Button1Click(Sender: TObject);
var
A, I: Integer;
//dwStart, dwEnd: DWORD;
t1, t2: Int64;
begin
A := 20;
//dwStart := GetTickCount;
QueryPerformanceCounter(t1);
for I := 0 to 100000000 do
if A in [9, 10, 13, 32] then
A := 20;
//dwEnd := GetTickCount;
QueryPerformanceCounter(t2);
//Memo1.Lines.Add(Format('Time: %d', [dwStart - dwEnd]));
Memo1.Lines.Add(Format('Time set ops: %d', [t2 - t1]));

//dwStart := GetTickCount;
QueryPerformanceCounter(t1);
for I := 0 to 100000000 do
if (A = 9) or (A = 10) or (A = 13) or (A = 32) then
A := 20;
//dwEnd := GetTickCount;
QueryPerformanceCounter(t2);
//Memo1.Lines.Add(Format('Time: %d', [dwStart - dwEnd]));
Memo1.Lines.Add(Format('Time compare: %d', [t2 - t1]));
Memo1.Lines.Add('');
end;

可以得出结论在没有命中时,常规比较比集合运算快 25%以上
而不是快一点点

但是,当集合的元素为8个时,都不命中,常规的比较简直慢了一倍
如果,集合元素为8个,第一个就命中,常规的比较简直快了一倍

情况比较复杂,看那位高手能总结出一个推论,
以作为编程时提升算法性能的参考!!
 
C

copy_paste

Unregistered / Unconfirmed
GUEST, unregistred user!
不会吧,我的是这样(用你的代码):
Time set ops: 1059527
Time compare: 1268930

Time set ops: 1027391
Time compare: 1272184

Time set ops: 1045595
Time compare: 1305424

Time set ops: 1051513
Time compare: 1302431

不过我的机子配置高点:P4 1.8G + 1G
 
L

LiChaoHui

Unregistered / Unconfirmed
GUEST, unregistred user!
哈哈,和CPU的类型还有关系,情况更复杂了
(不同类型的CPU在执行某些指令时所用的时间是不同的)
这种问题看来是不会有理想的答案了?:)

不过还是期待最终的推论!
 
C

copy_paste

Unregistered / Unconfirmed
GUEST, unregistred user!
在我同事:PIII800 + 128M那里也是in操作比较快点(无翕中,多元素)

唉,其实无所谓这样,差不多的情况下,以代码简洁为主。呵
 
A

Adnil

Unregistered / Unconfirmed
GUEST, unregistred user!
把酒论英雄啊,呵呵!

我最终准备使用LiChaoHui的代码版本,对Text,Keyw[m]这些使用pwidechar方式来
进行些优化,过后贴出来

copy_paste和LiChaoHui我另外发贴给分。
 
A

Adnil

Unregistered / Unconfirmed
GUEST, unregistred user!
LiChaoHui 300:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1620173

copy_paste 200:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1620156
 
顶部