C ++ Длинный оператор switch или поиск с картой? - PullRequest
Новая
       75

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

30 голосов
/ 17 марта 2010

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

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

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

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

Ответы [ 12 ]

8 голосов
/ 17 марта 2010

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

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

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

struct Code { int code; int value; };

Code c = ...

std::cout << "Code " << c.code << ", value " << c.value << std::end;
7 голосов
/ 17 марта 2010

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

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

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

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

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

5 голосов
/ 18 марта 2010

Это скорее зависит от того, какие коды и сколько их. Хорошие компиляторы имеют различные приемы, которые они используют для оптимизации операторов 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: ...
        ...
    }
}

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

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

2 голосов
/ 18 марта 2010

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

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.

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

2 голосов
/ 18 марта 2010

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

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

2 голосов
/ 17 марта 2010

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

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

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

1 голос
/ 18 марта 2010

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

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

0 голосов
/ 12 октября 2018

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

0 голосов
/ 25 марта 2010

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

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

0 голосов
/ 18 марта 2010
  • Считать целые числа в массив / вектор
  • сортировка массива / вектора
  • использовать bsearch для базового массива
Страница:
...