C++ Длинный оператор switch или поиск с картой?

Question

В моем приложении C++ у меня есть некоторые значения, которые действуют как коды для представления других значений. Чтобы перевести коды, я спорил между использованием оператора switch или stl map. Переключатель будет выглядеть примерно так:

int code;
int value;
switch(code)
{
case 1:
    value = 10;
    break;
case 2:
    value = 15;
    break;
}

Карта будет stl::map<int, int> и перевод будет простым поиском с кодом, используемым в качестве значения ключа.

Какой из них лучше / эффективнее / чище / принят? Зачем?

Answer 1

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

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

Другой подход к этому - подумать, если не было бы больше смысла объединять код и соответствующее значение в структуру данных, особенно если диапазон кодов и значений является статическим:

struct Code { int code; int value; };

Code c = ...

std::cout << "Code " << c.code << ", value " << c.value << std::end;

Answer 2

Если ваши коды достаточно смежны и их диапазон разрешен, вам будет намного лучше с старомодным простым массивом, что-то вроде

int lookup[] = {-1, 10, 15, -1 222};

тогда оператор switch может быть переписан так же просто, как

значение = поиск [код];

все остальные варианты в некоторой степени вводят дополнительные расходы.

Answer 3

Скорее, это зависит от того, что это за коды и сколько их. Хорошие компиляторы имеют различные приемы, которые они используют для оптимизации операторов switch, некоторые из которых они не будут использовать с прямыми операторами if/then. Большинство из них достаточно умны, чтобы выполнять простую математику или использовать таблицы поиска / перехода для случая 0, 1, 2 или случая 3, 6, 9, например.

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

switch (code) {
    case 0x0001: ...
    case 0x0002: ...
    ...
    case 0x8001: ...
    case 0x8002: ...
    ...
}

Вы можете использовать:

if (code & 0x8000) {
    code &= ~0x8000;
    switch (code) {
        case 0x0001: ... // actually 0x8001
        case 0x0002: ... // actually 0x8002
        ...
    }
}
else {
    switch (code) {
        case 0x0001: ...
        case 0x0002: ...
        ...
    }
}

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

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

Answer 4

Я предлагаю использовать статическую, постоянную таблицу пар. Это еще одна форма таблицы поиска:

struct Table_Entry
{
    int code;
    int value;
};

static const Table_Entry  lookup_table[] =
{
  {1, 10},
  {2, 15},
  {3, 13},
};

static const unsigned int NUM_TABLE_ENTRIES =
    sizeof(lookup_table) / sizeof(lookup_table[0]);

Преимущество этого состоит в том, что таблица генерируется во время компиляции, в отличие от std::map который должен быть инициализирован во время выполнения. Если количество велико, вы можете использовать std::lower_bound найти запись при условии, что стол заказан.

Еще одно преимущество заключается в том, что этот метод основан на данных. Данные могут измениться без изменений в поисковой системе. Изменения в коде или процессе могут потребовать серьезного регрессионного тестирования, но изменения данных не могут; YMMV.

Это похоже на то, что может генерировать компилятор.

Answer 5

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

Пойти за то, что делает ваш код легче поддерживать в долгосрочной перспективе.

Ваш образец слишком короткий, чтобы сделать какой-либо значимый вызов в этом отношении.

Answer 6

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

Все ИМХО, конечно.

Answer 7

Если вы можете использовать tr1, вы можете использовать unordered_map для хэширования значений (хеширование также может быть очень быстрым), что должно сделать большинство поисков постоянным временем.

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

Answer 8

Я говорю map, если все, что вы делаете, это присваиваете значение. Моя причина в том, что он расширяемый без изменения кода, чего нет у вашего оператора switch.

Кстати, как насчет перечисления?

Answer 9

Я думаю, что сгенерированный код структуры switch-case может вырасти довольно большим, если количество "кодов" станет большим, и в этом случае я думаю, что stl::map является более подходящим.

Answer 10

unordered_map, вероятно, подойдет лучше, так как здесь используется хеш-таблица, и поиск будет быстрее, чем switch.

Answer 11

Обычно я бы предложил карту или поисковый массив или, может быть, даже какого-нибудь гибридного поискового монстра (конечно, при условии, что вы оптимизируете скорость или размер кода, а не читабельность), но стоит отметить, что новые версии GCC разумны достаточно, чтобы заменить переключение / регистр назначений, как это для поиска таблиц. Хотя это не очень хорошо для полностью разреженных ключей, это может быть, если ваши ключи находятся в глыбах, таких как: 0, 1, 2, 3, 4, 5, 11, 12, 13, 14, 15, 193, 194, 195, 196, 197, 198...

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

Answer 12

• Читайте целые числа в массив / вектор
• сортировать массив / вектор
• использовать bsearch для базового массива