Как часто вы беспокоитесь о том, сколько дел нужно будет обрабатывать?

Question

Если у вас есть следующее:

$var = 3; // we'll say it's set to 3 for this example
if ($var == 4) {
    // do something
} else if ($var == 5) {
    // do something
} else if ($var == 2) {
    // do something
} else if ($var == 3) {
    // do something
} else {
    // do something
}

Если, скажем, в 80% случаев $var равно 3, беспокоит ли вас тот факт, что он проходит через 4 случая, прежде чем найти истинный случай?

Я думаю, что на маленьком сайте это не имеет большого значения, но как насчет того, когда оператор if будет запускаться тысячи раз в секунду?

Я работаю в PHP, но думаю, что язык не имеет значения.

Answer 1

Вот как мы это сделали, когда я писал программы для радиолокационных систем. (Скорость имеет значение в радаре. Это одно из немногих мест, где «реальное время» фактически означает «реальное», а не «быстрое».)

[Я переключусь на синтаксис Python, мне проще, и я уверен, что вы можете его интерпретировать.]

if var <= 3:
    if var == 2:
        # do something
    elif var == 3:
        # do something
    else: 
        raise Exception
else:
    if var == 4:
        # do something
    elif var == 5:
        # do something
    else:
        raise Exception

Ваши операторы if формируют дерево вместо простого списка. Добавляя условия в этот список, вы перемещаетесь по центру дерева. Плоская последовательность n сравнений в среднем занимает n / 2 шага. Дерево приводит к последовательности сравнений, которая берет логарифмические ( n ) сравнения.

Answer 2

Ну, я считаю, что почти все время , например, удобочитаемость, скажем, наличия числовых упорядоченных значений, перевесит любые крошечные преимущества, которые вы можете получить, уменьшив количество инструкций сравнения.

Сказав это, как и при любой оптимизации:

1. Заставь это работать
2. Измерить
3. Если это достаточно быстро, оставь его в покое
4. Если это слишком медленно, ТО оптимизируйте его

О, и я бы, наверное, использовал переключатель / чехол с самого начала! ; -)

Answer 3

Классический случай этого события (буквально 5 опций, как в вашем посте) был в ffmpeg, в функции decode_cabac_residual. Это было довольно важно, так как профилирование (очень важно - не оптимизировать перед профилированием!) Показало, что на него приходится более 10-15% времени, затрачиваемого на декодирование видео H.264. Оператор if контролировал набор операторов, которые рассчитывались по-разному для различных типов невязок, подлежащих декодированию, и, к сожалению, слишком большая скорость терялась из-за размера кода, если функция дублировалась 5 раз для каждого из 5 типов остаточное. Так что вместо этого нужно было использовать цепочку if.

Профилирование было выполнено во многих общих тестовых потоках, чтобы упорядочить их по вероятности; верх был самым распространенным, нижний - наименьшим. Это дало небольшой прирост скорости.

Теперь, в PHP, я подозреваю, что прирост скорости низкоуровневого стиля намного меньше, чем в C, как в приведенном выше примере.

Answer 4

Использование оператора switch / case - определенно правильный путь.

Это дает компилятору (интерпретатору) возможность использовать таблицу переходов для перехода к нужной ветви без необходимости выполнять N сравнений. Представьте, что он создает массив адресов с индексами 0, 1, 2, ... тогда он может просто найти правильный адрес в массиве за одну операцию.

Кроме того, поскольку в выражении case меньше издержек на синтаксис, оно также читается легче.

Обновление: если сравнения подходят для оператора switch, то это область, в которой может помочь оптимизация по профилю. Запустив сборку PGO с реалистичными тестовыми нагрузками, система может сгенерировать информацию об использовании филиала, а затем использовать ее для оптимизации выбранного пути.

Answer 5

Вы можете попробовать иметь массив блоков кода, которые вы вызываете. Тогда все кодовые блоки имеют одинаковые служебные данные.

Perl 6:

our @code_blocks = (
  { 'Code Block 0' },
  { 'Code Block 1' },
  { 'Code Block 2' },
  { 'Code Block 3' },
  { 'Code Block 4' },
  { 'Code Block 5' },
);

if( 0 <= $var < @code_blocks.length ){
  @code_blocks[$var]->();
}

Answer 6

Вместо того, чтобы отвечать на вопрос PHP, я отвечу немного более широко. Он не применяется напрямую к PHP, поскольку будет проходить некоторую интерпретацию.

Многие компиляторы могут преобразовывать в блоки if-elif-elif -... и из них, чтобы переключать блоки при необходимости, и тесты в elif-частях достаточно просты (а остальная семантика оказывается совместимой). Для 3-4 тестов не обязательно что-либо выигрывать при использовании таблицы прыжков.

Причина в том, что предсказатель ветвлений в ЦП действительно хорош в прогнозировании того, что происходит. По сути, единственное, что происходит, это немного большее давление на выбор инструкций, но вряд ли это будет потрясением.

Однако в вашем примере большинство компиляторов распознают, что $ var является константой 3, а затем заменяют $ var на 3 в блоках if..elif ... Это, в свою очередь, делает выражения постоянными, поэтому они складываются в одно из истинных или ложных. Все ложные ответвления уничтожаются средством удаления мертвых кодов, а также проверяется проверка на истинность. Остается случай, когда $ var == 3. Вы не можете полагаться на то, что PHP такой умный. В общем, вы не можете распространять $ var, но это возможно с некоторых колл-сайтов.

Answer 7

Если код должен выполнять дополнительные тесты, он будет выполняться медленнее. Если производительность критична в этом разделе кода, то вы должны поставить наиболее распространенные случаи в первую очередь.

Обычно я согласен с методом «измерить, а затем оптимизировать», когда вы не уверены, будет ли производительность достаточно быстрой, но если код просто должен работать как можно быстрее, а исправить это так же просто, как переставить тесты, затем я бы сделал код быстрым сейчас и выполнил бы некоторые измерения после того, как вы начнете жить, чтобы убедиться, что ваше предположение (например, 3 произойдет в 80% случаев) на самом деле правильно.

Answer 8

Только вы можете сказать, будет ли разница в производительности оптимизации порядка или реорганизации его в двоичное дерево иметь существенное значение. Но я подозреваю, что вам придется иметь миллионы раз в секунду, а не тысячи, чтобы даже думать об этом в PHP (и даже в некоторых других языках).

Время это. Посмотрите, сколько раз в секунду вы можете выполнить приведенный выше оператор if / else if / else без каких-либо действий и $ var не является одним из вариантов.

Answer 9

В объектно-ориентированных языках, если опция предоставляет массивные if, то это означает, что вы должны просто переместить поведение (например, ваши //do something блоки) в объект, содержащий значение.

Answer 10

С кодом, где это чисто анализ равенства, я бы переместил его в переключатель / регистр, так как это обеспечивает лучшую производительность.

$var = 3; // we'll say it's set to 3 for this example
switch($var)
 {
   case 4:
      //do something
      break;
   case 5:
      //do something
      break;
   case:
      //do something when none of the provided cases match (same as using an else{ after the elseif{
 }

теперь, если вы делаете более сложные сравнения, я бы либо вложил их в переключатель, либо просто использовал elseif.