C ++: Что быстрее - поиск в hashmap или оператор switch?

Question

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

int t(int value) {
    switch (value) {
        case 1: return const_1;
        case 3: return const_2;
        case 4: return const_3;
        case 8: return const_4;
        default: return 0;
    }
}

В данный момент в нем около 50 записей, возможно, позже будет еще несколько, но, вероятно, не более ста или двух. Все значения предопределены, и, конечно, я могу упорядочить метки регистра по их значениям. Итак, вопрос в том, что будет быстрее - этот подход или поместить это в хэш-карту (у меня нет доступа к std :: map, поэтому я говорю о пользовательской хэш-карте, доступной в моем SDK) и выполнять поиск в этой таблице? Может быть, это немного преждевременная оптимизация, хотя ... Но мне просто нужно ваше мнение.

Заранее спасибо.

РЕДАКТИРОВАТЬ : значения моего регистра будут в диапазоне от 0 до 0xffff. А что касается точки лучшей читаемости хеш-карты. Я не уверен, что он действительно будет лучше читаемым, потому что мне все еще нужно заполнить его значениями, так что отображение константных листов все еще должно быть где-то в моем коде.

РЕДАКТИРОВАТЬ-2 : Многие полезные ответы уже были даны, большое спасибо. Я хотел бы добавить некоторую информацию здесь. Мой хеш-ключ - целое число, а моя хеш-функция для целого числа - это всего лишь одно умножение с целочисленным переполнением:

EXPORT_C __NAKED__ unsigned int DefaultHash::Integer(const int& /*aInt*/)
{
_asm mov edx, [esp+4]
_asm mov eax, 9E3779B9h
_asm mul dword ptr [edx]
_asm ret
}

Так что это должно быть довольно быстро.

Answer 1

Конструкция switch быстрее (или, по крайней мере, не медленнее).

Это в основном потому, что конструкция switch передает статические данные компилятору, а структура времени выполнения, такая как хэш-карта, - нет.

Когда это возможно, компиляторы должны компилировать конструкции switch в массив указателей кода: каждый элемент массива (индексируемый вашими индексами) указывает на связанный код. Во время выполнения это занимает O (1), тогда как хэш-карта может занять больше: O (log n) в среднем случае или O (n) в худшем случае, обычно, и в любом случае большее постоянное число обращений к памяти.

Answer 2

Я добавлю свои 5 центов:

Для числа записей около 50 std :: unordered_map (на основе хэша, O (1)) обычно медленнее, чем std :: map (на основе дерева O (ln (N))), и оба они медленнее затем boost :: flat_map (отсортированный вектор O (ln (N))), который я обычно использую в таких случаях. Не всегда бывает так, что switch может быть скомпилирован для перехода по таблице, и когда это так, вы можете просто поместить свои значения (или функции) в вектор самостоятельно и получить доступ по индексу. В противном случае переключение немного быстрее, чем boost :: flat_map.

Пожалуйста, обратите внимание на слово «обычно» в начале, если вы заботитесь о производительности этого фрагмента кода, выполните профилирование (и поделитесь результатами с нами :)).

Answer 3

A switch statement будет быстрее, чем поиск по хеш-карте.

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

Answer 4

Переключатель будет быстрее. Если это небольшое количество случаев, как в вашем примере, он будет использовать цепочку if. Если большое количество случаев, и если они достаточно компактны, у него есть возможность генерировать таблицу переходов, которая занимает всего несколько инструкций. (Кстати, вам не нужно заказывать случаи.) Хэш-карта O (1), но, вероятно, будет принимать в диапазоне 10-40 инструкций.

Answer 5

Я согласен с использованием массива, но у меня нет репутации, чтобы голосовать за него. Это всего 65536 записей, поэтому, если у вас нет серьезных ограничений памяти и / или вы возвращаете что-то очень большое, вместо int, как в вашем примере, вам будет намного лучше использовать статический константный массив. Массив из 64 тыс. Целых, как правило, составляет всего 256 КБ, и он будет вдвое меньше, чем 1/4, если вы можете использовать short или char. Я думаю, что лучшее, на что вы можете надеяться с помощью оператора switch - это условная ветвь для значений вне массива указателей кода и вторая условная ветвь для перехода к коду для значения внутри массива. Возможность просто выполнить «return my_array [value]» просто приведет к извлечению памяти (возможно, из кэша l3).

Для удобства чтения вы можете поместить массив в отдельный файл и выстроить все значения в сетке примерно в 10 или 16 записей в строке. Затем вы комментируете каждую строку первой частью каждого номера записи (например, "// 0x12A?"), И у вас есть периодические строки комментариев, которые будут выровнены со столбцами, чтобы заполнить последнюю цифру для номера записи (например, "// 0 1 2 3 4 5 6 7 8 9 ABCDEF "). Я сделал это для нескольких массивов из 256 записей, которыми было намного легче управлять, чем оператором switch. Я также использовал массивы с записями 64 КБ для быстрых целочисленных логарифмов, которыми сложнее управлять, но я смог написать программу для генерации всего кода массива.

С чем-то большим, управление кодом может быть не простым, пока вы не разберетесь с большим количеством записей, но это зависит от вашего редактора и навыков работы с ним. Поддерживать такой массив - это просто корректировать место на графике, а не искать значения, которые могут быть или не быть в длинном списке «case 1: return const_1;». Пару циклов for должно быть достаточно для генерации массива из 64 тыс. Записей, которые правильно прокомментированы и заполнены значениями по умолчанию.

В целях безопасности доступа вы можете рассмотреть возможность проверки границ. Это можно сделать с помощью предварительных условий boost, выбрасывая исключение или специальный возврат, если число выходит за границы, или просто «return my_array [value & 0xffff]». Тем не менее, у вас может быть достаточно сильная гарантия на входящую ценность, которая вам не нужна.

Answer 6

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

Answer 7

Массив будет иметь самое быстрое время доступа по определению.

Оператор switch сравнивает значения, а затем использует таблицу переходов (которая представляет собой массив указателей на функции).

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

На большинстве современных платформ, 64 КБ, это небольшой объем данных и может быть статически выделен как постоянный массив.

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

Я предлагаю использовать static const массив значений.

Answer 8

Вам может понравиться эта статья: http://www.codeproject.com/KB/cpp/switch.aspx

Answer 9

Сложность времени хеш-таблицы обычно равна O (1), если не учитывать коллизию. Стандарт C ++ не определяет, как реализован переключатель, но он может быть реализован в виде таблицы переходов, сложность времени которой также равна O (1), или он может быть реализован в виде двоичного поиска, сложность времени которого равна O (log n), или комбинации в зависимости от сколько дел и т. д.

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

Answer 10

Я думаю, что не очевидно, что будет быстрее.Возможно, вам понадобится профилировать оба подхода.

Хэш-карта должна иметь сложность O (1).

Переключатель (с несмежными ключами, такими как ваш) может быть оптимизирован для бинарного поиска(по крайней мере, с GCC), который имеет сложность O (log n).

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