Вопросы Теги

Производительность Delphi: случай, по сравнению с если

Я предполагаю, что могло бы быть некоторое наложение с предыдущим ТАК вопросы, но я не мог найти конкретный вопрос 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;

Я предполагаю, что, если вариант занимает время O (n) для завершения (т.е. найти правильное действие), если правильное действие у ACTIONi есть высокое значение меня, тогда как вариант случая занимает намного меньше времени (O (1)?).

  1. Я корректен, что переключатель намного быстрее?
  2. Я корректен, что время, необходимое для нахождения правильного действия в случае переключателя на самом деле, независимо от n? Т.е. действительно ли это верно, что действительно не берет еще для проверки миллиона случаев, чем проверить 10 случаев?
  3. Как, точно, это работает?
21
задан Andreas Rejbrand 30 March 2010 в 18:47
поделиться

4 ответа

  1. Да, переключатель - O (1), тогда как каскадные if - O (n)
  2. Да, см. (1)
  3. С таблицей перехода
15
ответ дан 29 November 2019 в 06:46
поделиться

Всегда полезно сначала проверить реальность ...

Компилятор 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
...

Барри мог дать нам однозначный ответ на этот вопрос. Я просто тестирую и болтаю.

19
ответ дан 29 November 2019 в 06:46
поделиться

Обратите внимание, что если значение MyAction взвешено, хорошую производительность можно получить с помощью каскадного if..else, где наиболее вероятные случаи помещаются рядом с Топ. Я не говорю, что он будет конкурировать с оператором case / switch с точки зрения производительности, когда вы имеете дело с целыми числами. Но если случай не подходит (предположим, у вас есть строки, например), поместите свои тесты с высоким процентом вверх.

3
ответ дан 29 November 2019 в 06:46
поделиться

Компилятор преобразует оператор case в один из:

  1. Двухуровневую таблицу, используя одну таблицу для сопоставления значения с индексом и используя индекс для выбора адреса из таблицы переходов
  2. Косвенный переход через таблицу
  3. Последовательные переходы
  4. Двоичный поиск - это рекурсивный поиск, поэтому листья двоичного поиска могут использовать любое из 2, 3 или 4.

Он использует эвристику, такую ​​как количество наблюдений, диапазон наблюдений , количество различных альтернатив (каждая альтернатива может реализовывать диапазон различных значений) и т. д.

Интуиция для оператора case состоит в том, что это операция O (1) .

19
ответ дан 29 November 2019 в 06:46
поделиться
Другие вопросы по тегам:

Похожие вопросы: