德尔福表现:案例与If

Question

我想可能与以前的SO问题有一些重叠,但我找不到关于这个主题的Delphi特定问题.

假设您要检查无符号的32位整数变量"MyAction"是否等于任何常量ACTION1,ACTION2,...,ACTIONn,其中n是 - 比如说1000.我想,除了更优雅之外,

case MyAction of
  ACTION1: {code};
  ACTION2: {code};
  ...
  ACTIONn: {code};
end;

比...快得多

if MyAction = ACTION1 then
  // code
else if MyAction = ACTION2 then
  // code
...
else if MyAction = ACTIONn then
  // code;

我猜if if变量需要时间O(n)来完成(即找到正确的动作)如果正确的动作ACTIONi具有高的i值,而case变量需要更少的时间(O(1)？) .

1. 我是否正确,开关速度更快？
2. 我是否认为在开关盒中找到正确动作所需的时间实际上与n无关？也就是说,检查一百万个案件比检查10个案件真的需要更长的时间吗？
3. 这究竟是如何工作的？

Answer 1

先检查现实总是好的...

Delphi 2010编译器似乎很喜欢测试和分支.例如,以下简单代码不会编译到分支表中.

var
  c: (aaa, bbb, ccc);

begin
  case c of
    aaa: sleep(0);
    bbb: sleep(0);
    ccc: sleep(0);
  end;
end.

编译器将生成以下代码:

Project56.dpr.24: case c of
0040A1C4 0FB6053C0E4100   movzx eax,[$00410e3c]
0040A1CB 2C01             sub al,$01
0040A1CD 7208             jb $0040a1d7
0040A1CF 740F             jz $0040a1e0
0040A1D1 FEC8             dec al
0040A1D3 7414             jz $0040a1e9
0040A1D5 EB19             jmp $0040a1f0
Project56.dpr.25: aaa: sleep(0);
0040A1D7 6A00             push $00
0040A1D9 E86EDAFFFF       call Sleep
0040A1DE EB10             jmp $0040a1f0
Project56.dpr.26: bbb: sleep(0);
0040A1E0 6A00             push $00
0040A1E2 E865DAFFFF       call Sleep
0040A1E7 EB07             jmp $0040a1f0
Project56.dpr.27: ccc: sleep(0);
0040A1E9 6A00             push $00
0040A1EB E85CDAFFFF       call Sleep

更复杂的案例将被编译成一个测试和跳转系列.例如 ...

var
  c: (aaa, bbb, ccc, eee, fff, ggg, hhh);

begin
  case c of
    aaa: sleep(0);
    bbb: sleep(0);
    ccc: sleep(0);
    hhh: sleep(0);
  end;
end.

......编译成......

Project56.dpr.24: case c of
0040A1C4 0FB6053C0E4100   movzx eax,[$00410e3c]
0040A1CB 2C01             sub al,$01
0040A1CD 720C             jb $0040a1db
0040A1CF 7413             jz $0040a1e4
0040A1D1 FEC8             dec al
0040A1D3 7418             jz $0040a1ed
0040A1D5 2C04             sub al,$04
0040A1D7 741D             jz $0040a1f6
0040A1D9 EB22             jmp $0040a1fd
Project56.dpr.25: aaa: sleep(0);
0040A1DB 6A00             push $00
0040A1DD E86ADAFFFF       call Sleep
0040A1E2 EB19             jmp $0040a1fd
Project56.dpr.26: bbb: sleep(0);
0040A1E4 6A00             push $00
0040A1E6 E861DAFFFF       call Sleep
0040A1EB EB10             jmp $0040a1fd
Project56.dpr.27: ccc: sleep(0);
0040A1ED 6A00             push $00
0040A1EF E858DAFFFF       call Sleep
0040A1F4 EB07             jmp $0040a1fd
Project56.dpr.28: hhh: sleep(0);
0040A1F6 6A00             push $00
0040A1F8 E84FDAFFFF       call Sleep

导致此类代码的最可能原因是,跳转表对L1缓存的效果不佳,并且如果没有大量的案例标签,则测试跳转版本可能会更快.

该推理的"证明"是以下程序,它被转换为跳转表.

var
  b: byte;

begin
  case b of
    0: sleep(0);
    1: sleep(0);
    2: sleep(0);
    3: sleep(0);
    4: sleep(0);
    5: sleep(0);
    6: sleep(0);
    7: sleep(0);
    8: sleep(0);
    9: sleep(0);
   10: sleep(0);
   11: sleep(0);
   12: sleep(0);
   13: sleep(0);
   14: sleep(0);
   15: sleep(0);
   16: sleep(0);
   17: sleep(0);
   18: sleep(0);
   19: sleep(0);
   20: sleep(0);
  end;
end.

Project56.dpr.12: case b of
0040A178 0FB6C0           movzx eax,al
0040A17B 83F814           cmp eax,$14
0040A17E 0F8728010000     jnbe $0040a2ac
0040A184 FF24858BA14000   jmp dword ptr [eax*4+$40a18b]
...
Project56.dpr.14: 1: sleep(0);
0040A1EB 6A00             push $00
0040A1ED E85ADAFFFF       call Sleep
0040A1F2 E9B5000000       jmp $0040a2ac
Project56.dpr.15: 2: sleep(0);
0040A1F7 6A00             push $00
0040A1F9 E84EDAFFFF       call Sleep
0040A1FE E9A9000000       jmp $0040a2ac
Project56.dpr.16: 3: sleep(0);
0040A203 6A00             push $00
0040A205 E842DAFFFF       call Sleep
0040A20A E99D000000       jmp $0040a2ac
...

巴里可以给我们一个明确的答案.我只是在测试和漫步.

Answer 2

编译器将case语句转换为以下之一:

1. 两级表,使用一个表将值映射到索引,并使用索引从跳转表中选择一个地址
2. 间接跳过表格
3. 连续跳跃
4. 二进制搜索 - 这是递归的,因此二进制搜索的叶子可以使用2,3或4中的任何一个.

它使用启发式,例如案例数,案例范围,不同备选方案的数量(每个备选方案可以实现一系列不同的值)等.

案例陈述的直觉是它是一种O(1)操作.

Answer 3

1. 是开关是O(1)而级联if是O(n)
2. 是的,见(1)
3. 带分支表