С++: что быстрее - поиск в hashmap или switch statement?

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

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. И в отношении лучшей читаемости хэш-карты. Я не уверен, что он действительно будет иметь лучшую читаемость, потому что мне все равно нужно заполнить его значениями, так что отображение содержимого констант должно быть где-то в моем коде.

EDIT-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
}

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

Ответы

Ответ 1

Конструкция

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 6

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

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

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

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

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

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

Ответ 7

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

Ответ 8

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

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

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

Для обеспечения безопасности доступа вы можете использовать некоторую проверку границ. Это может быть сделано с предварительными условиями форматирования, выбрасыванием исключения или специального возврата, если число выходит за пределы, или простое "return my_array [value & 0xffff]". Однако у вас может быть достаточно надежная гарантия на входящее значение, которое вам не нужно.

Ответ 9

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

Карта хешей должна иметь сложность O (1).

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

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

Ответ 10

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

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