逻辑表达式效率和优化问题(100分)

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-14

• #21

忘了一个比较重要的细节——如果要在理论层面进行优化，那么上述的子判定的真假概率
就是一个非常重要的参考。不过，仅仅进行全局的概率统计还是不够的，例如：有A,B,C三
个判定，全局统计的结果是A,B的判真概率均为60%，C的判真概率为50%——看起来没有太大
区别，但是，如果考虑“条件概率”的话——当判定A的结果为真时，C的结果为真的概率就
不再是全局的50%而是80%。在实际中，条件概率属于高级概率分析（贝叶斯公式），实用价
值远大于全概率。
根据LeeChange兄的分析，楼主的算法涉及到3个判定，也就是说，如果要进行贝叶斯概率
统计，就要针对数十种组合情况进行细分——唉！看起来还是直接试验来的划算[]

 

0

007vivi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-14

• #22

看了那么多,嘿嘿,果然很久没有人去讨论高深的东西了,^_^.鉴定完毕..

 

L

llaaddoo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-14

• #23

//代码难看~~速度比你那个要块些~~哈哈

if b then
begin
for i=0 to x do
begin
if (P = ' ') or (P = #0) then
begin
end;
end;
end
else
begin
for i=0 to x do
begin
if (P <> ' ') or (P = #0) then
begin
end;
end;
end;

 

L

llaaddoo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-14

• #24

100个字符的字符串如果全部扫描一遍~~
(b=(P=' ')) or (P=#0) 这个要执行 3*100次判断

上面这个代码只执行 2*100+2 次判断~~~提高了 30%左右的速度哈~~~

 

L

llaaddoo

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-14

• #25

另 and、not、=、<>和xor 这几个代码的效率差异应该可以忽略~~~
都是一条cpu指令搞定~~~实在要计较~~~
还要去查每个指令的执行周期~~~不至于~~

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-15

• #26

私下认为楼主的b很可能会在循环内部发生变化，所以不考虑利用b的值分割为两个循环的
情况。不过，我认为有一点还是可以优化的——将P=#0独立出来，放在循环外部，从而
让主循环体不必考虑这个只会在最后触发一次的情况。
为了对不同的表达式计算效率进行“一般性”的检验，我在此设计了一个比较“精确”的
比较试验场景（我在循环内使用了b:=not b以让b的真假情况分布均匀）：

procedure TForm1.Button1Click(Sender: TObject);
var
i:Integer;
DataLen:Integer;
P:array of Char;
ct1,ct2:Int64;
dt:array[0..7]of Int64;
b:Boolean;
begin
DataLen:=10000000;
SetLength(P,DataLen);
RandSeed:=9876;
for i:=0 to Pred(DataLen shr 2) do
PInteger(@P[i shl 2])^:=Random(MaxInt) or $20202020
//确保中间的数据不含#0
P[DataLen-1]:=#0
//末位为#0
b:=false;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen) do
begin
if b then //2 line
b:=not not b
//2 line
b:=not b
//1 line
end;
QueryPerformanceCounter(ct2);
dt[0]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen) do
begin
if (b and (P = ' ')) or ((not b) and (P <> ' ')) or (P = #0) then //13 line
b:=not not b;
b:=not b;
end;
QueryPerformanceCounter(ct2);
dt[1]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen) do
begin
if ((not b) and (P <> ' ')) or (b and (P = ' ')) or (P = #0) then //13 line
b:=not not b;
b:=not b;
end;
QueryPerformanceCounter(ct2);
dt[2]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen) do
begin
if (not (b xor (P <> ' '))) or (P = #0) then //8 line
b:=not not b;
b:=not b;
end;
QueryPerformanceCounter(ct2);
dt[3]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen)-1 do
begin
if (b and (P = ' ')) or ((not b) and (P <> ' ')) then //10 line
b:=not not b;
b:=not b;
end;
if true then b:=not b
//P[DataLen-1]=#0 always true
QueryPerformanceCounter(ct2);
dt[4]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen)-1 do
begin
if ((not b) and (P <> ' ')) or (b and (P = ' ')) then //10 line
b:=not not b;
b:=not b;
end;
if true then b:=not b
//同上
QueryPerformanceCounter(ct2);
dt[5]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen)-1 do
begin
if not (b xor (P <> ' ')) then //5 line
b:=not not b;
b:=not b;
end;
if true then b:=not b
//同上
QueryPerformanceCounter(ct2);
dt[6]:=ct2-ct1;
//
QueryPerformanceCounter(ct1);
for i:=0 to Pred(DataLen)-1 do
begin
if (b xor (P = ' ')) then //5 line ——Delphi 7 编译优化的结果与 not (b xor (P <> ' ')) 的优化结果完全一致！
b:=not not b;
b:=not b;
end;
if true then b:=not b
//同上
QueryPerformanceCounter(ct2);
dt[7]:=ct2-ct1;
if b then ;
SetLength(P,0);
ShowMessage(Format('0: %6d, 1: %6d, 2: %6d, 3: %6d, 4: %6d, 5: %6d, 6: %6d, 7: %6d',
[dt[0],dt[1],dt[2],dt[3],dt[4],dt[5],dt[6],dt[7]])
+#13#10+Format('-> %6d, 1: %6d, 2: %6d, 3: %6d, 4: %6d, 5: %6d, 6: %6d, 7: %6d',
[0,dt[1]-dt[0],dt[2]-dt[0],dt[3]-dt[0],dt[4]-dt[0],dt[5]-dt[0],dt[6]-dt[0],dt[7]-dt[0]]));
end;

0: 95695, 1: 218596, 2: 185088, 3: 286977, 4: 205215, 5: 158836, 6: 145413, 7: 145650 //原始计时(0:为空耗值)
-> 0, 1: 122901, 2: 89393, 3: 191282, 4: 109520, 5: 63141, 6: 49718, 7: 49955 //减去空耗之后的值


从结果可以看出：虽然算法1,2的产生的机器指令数一样，但由于涉及P以及b的子判定的
概率不同，实际执行耗时有较大的差别（100比73），而算法3虽然看起来最“简洁”，但效
率反而最低（俺看不出啥问题导致它如此慢...）。而算法4,5,6,7虽然均使用了末位优化技
术，但是除了优化编译结果代码完全相同的6,7之外，效率还是有一些差距——4与1相近，
而5与2相近，在去掉了#0累赘后，1比2慢的结果更加清晰的体现在了4和5上。而算法6与3接
近，但由于没有#0判定，效率比4,5都要高（而3并不比1,2都快！）。

好了——“一般性”分析到此结束——就等着看楼主在实际运行中的各个子判定的判定结
果出现概率不同所导致的各个算法效率如何了。

ps:即便数据概率保持稳定，但考虑到编译器优化以及不同类型的CPU执行特点不同，以上算
法的效率还是存在着较大的变数。上面的数值结果仅代表偶的Delphi7+迅驰1代1.4G CPU的
情况。[]

 

F

FreeAndNil

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2008-09-20

• #27

多人接受答案了。