Если-иначе-если против карты

Question

Предположим, у меня есть такая цепочка if / else-if:

if( x.GetId() == 1 )
{
}
else if( x.GetId() == 2 )
{
}
// ... 50 more else if statements

Что мне интересно, если я сохраню карту, будет ли она лучше с точки зрения производительности? (при условии, что ключи являются целыми числами)

Answer 1

Карты (обычно) реализуются с использованием красно-черных деревьев, что дает O (log N) поисков, поскольку дерево постоянно поддерживается в балансе. Ваш линейный список операторов if будет O (N) в худшем случае. Итак, да, карта будет значительно быстрее для поиска.

Многие люди рекомендуют использовать оператор switch, который может быть не быстрым для вас, в зависимости от ваших реальных операторов if. Иногда компилятор может оптимизировать переключение, используя таблицу переходов, которая будет O (1), но это возможно только для значений, которые не определены критериями; следовательно, это поведение может быть несколько недетерминированным. Хотя здесь есть отличная статья с несколькими советами по оптимизации операторов switch Оптимизация кода C и C ++ .

Технически вы даже могли бы составить сбалансированное дерево вручную, это лучше всего работает для статических данных, и я случайно недавно создал функцию для быстрого поиска того, какой бит был установлен в байте (это использовалось во встроенном приложении на I / Прерывание по контакту и должно быть быстрым, когда в байте 99% времени будет установлен только 1 бит):

unsigned char single_bit_index(unsigned char bit) {
    // Hard-coded balanced tree lookup
    if(bit > 0x08)
        if(bit > 0x20)
            if(bit == 0x40)
                return 6;
            else
                return 7;
        else
            if(bit == 0x10)
                return 4;
            else
                return 5;
    else
        if(bit > 0x02)
            if(bit == 0x04)
                return 2;
            else
                return 3;
        else
            if(bit == 0x01)
                return 0;
            else
                return 1;
}

Это дает постоянный поиск в 3 шага для любого из 8 значений, что дает мне очень детерминированную производительность, линейный поиск - с учетом случайных данных - будет в среднем выполнять 4 шага поиска, с наилучшим случаем 1 и наихудшим кейс из 8 шагов.

Это хороший пример диапазона, который компилятор, вероятно, не оптимизировал бы для таблицы переходов, поскольку 8 значений, которые я ищу, настолько далеко друг от друга: 1, 2, 4, 8, 16, 32, 64 и 128. Было бы необходимо создать очень разреженную таблицу с 128 позициями, содержащую только 8 элементов, содержащих цель, что на ПК с тонной оперативной памяти не имело бы большого значения, но на микроконтроллере это было бы убийственно.

Answer 2

почему вы не используете переключатель?

swich(x.GetId())
{
  case 1: /* do work */ break; // From the most used case
  case 2: /* do work */ break; 
  case ...: // To the less used case
}

EDIT:

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

Answer 3

switch это лучшее, что я думаю

Answer 4

Есть много предложений, касающихся распределительного шкафа. С точки зрения эффективности, это может быть лучше, может быть таким же. Хуже не будет.

Но если вы просто устанавливаете / возвращаете значение или имя на основе идентификатора, тогда ДА. Карта именно то, что вам нужно. Контейнеры STL оптимизированы, и если вы думаете, что можете оптимизировать лучше, то вы либо невероятно умны, либо потрясающе глупы.

например, один вызов с использованием std :: map с именем mymap,

thisvar = mymap[x.getID()];

намного лучше, чем 50 из них

if(x.getID() == ...){thisvar = ...;}

потому что это более эффективно, поскольку число идентификаторов увеличивается. Если вас интересует почему, найдите хороший учебник по структурам данных.

Но то, что я действительно посмотрю здесь, это время обслуживания / ремонта. Если вам нужно изменить имя переменной или использовать getID () или getName (), или внести какие-либо незначительные изменения, вы должны сделать это ПЯТНАДЦАТЬ РАЗ в вашем примере. И вам нужно новую строку каждый раз, когда вы добавляете идентификатор.

Карта сводит это к одному изменению кода. Неважно, сколько у вас идентификаторов.

Тем не менее, если вы на самом деле выполняете различные действия для каждого идентификатора, лучше использовать коммутатор. С помощью switch-case, а не if, вы можете улучшить производительность и удобочитаемость. Смотрите здесь: Преимущество оператора переключения if-else Я бы избегал указателей на функции, если вы не очень ясно знаете, как они улучшат ваш код, потому что, если вы не уверены на 100% в своих действиях, синтаксис может быть испорчен, и это излишне для вас целесообразно использовать карту для.

По сути, меня интересует проблема, которую вы пытаетесь решить. Возможно, вам лучше использовать карту или распределительный шкаф, но если вы думаете, что можете использовать карту, это АБСОЛЮТНО то, что вы должны использовать вместо этого.

Answer 5

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

#include <cstdio>
#include <cstdlib>
#include <ctime>

const unsigned int Max = 4;

void f1();
void f2();
void f3();
void f4();
void (*vp[Max])();

int main()
{
    vp[ 0 ] = f1;
    vp[ 1 ] = f2;
    vp[ 2 ] = f3;
    vp[ 3 ] = f4;

    srand( std::time( NULL ) );
    vp[( rand() % Max )]();
}

void f1()
{
    std::printf( "Hello from f1!\n" );
}

void f2()
{
    std::printf( "Hello from f2!\n" );
}

void f3()
{
    std::printf( "Hello from f3!\n" );
}

void f4()
{
    std::printf( "Hello from f4!\n" );
}

Answer 6

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

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

[отсюда, switchотносится к общей цепочке if/else]

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

A map приведет к некоторым начальным издержкамзагрузка идентификаторов и их привязка к функциям, а затем дополнительные затраты на вызов указателя функции каждый раз, когда вы получаете доступ к идентификатору.switch влечет за собой дополнительные издержки при написании подпрограммы и, возможно, значительные накладные расходы при ее отладке.

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

Answer 7

Лучшим решением было бы утверждение switch. Это позволит вам проверить значение x.GetId() только один раз, а не (в среднем) 25 раз, как сейчас делает ваш код.

Если вы хотите получить фантазию, вы можете использовать структуру данных, содержащую указатели для функций, которые обрабатывают все, что находится в фигурных скобках. Если ваши значения идентификаторов являются последовательными (то есть числами от 1 до 50), тогда лучше всего использовать массив указателей на функции. Если они разложены, то карта была бы более подходящей.