Более эффективный случай переключения или std:: map

Ответ 1

Карта STL, которая поставляется с visual studio 2008, даст вам O (log (n)) для каждого вызова функции, поскольку она скрывает древовидную структуру внизу. С современным компилятором (в зависимости от реализации) оператор switch даст вам O (1), компилятор переводит его в какую-то таблицу поиска. Так что в общем случае, коммутатор работает быстрее.

Однако, рассмотрим следующие факты:

Разница между картой и коммутатором заключается в следующем: карта может быть построена динамически, а переключатель не может. Карта может содержать любой произвольный тип в качестве ключа, в то время как переключатель очень ограничен С++ примитивными типами (char, int, enum и т.д.).

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

Изменить

Я пишу следующее только для удовольствия и для обсуждения

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

Когда вы пишете код: Вы делите токены на две группы, одна группа будет очень часто использоваться, а другая из часто используемых. Вы также сортируете высоко часто используемые токены. Для часто встречающихся токенов вы пишете строку if-else с самым высоким часто используемым в начале. для часто используемого минимума вы пишете оператор switch.

Идея состоит в том, чтобы использовать предсказание ветвления процессора, чтобы избежать другого уровня косвенности (при условии, что проверка состояния в операторе if почти не требует затрат). в большинстве случаев ЦП будет выбирать правильную ветвь без какого-либо уровня косвенности. Однако их будет несколько случаев, что филиал пойдет не туда. В зависимости от характера вашего languege, статистически это может дать лучшую производительность.

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

Ответ 2

Я бы предложил прочитать switch() vs. lookup table? от Joel on Software. В частности, этот ответ интересен:

"Премьер-пример людей, тратящих время пытаясь оптимизировать наименее значительная вещь."

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

В виртуальных машинах обычно выбираются таблицы поиска, в которых хранятся вычисленные адреса для вызова. (прямая резьба или "метка как значения" ) напрямую вызывает адрес метки, хранящийся в таблице поиска). Это потому, что позволяет при определенных условиях уменьшить неверное предсказание отрасли, что чрезвычайно дорого для процессоров с длинными конвейерами (это заставляет промывать трубопровод). Это, однако, делает код менее портативным.

Этот вопрос широко обсуждался в сообществе VM, я бы предложил вам искать научные статьи в этой области, если вы хотите больше узнать об этом. В 2001 году Эртль и Грегг великую статью по этой теме, Поведение эффективных интерпретаторов виртуальной машины на современных архитектурах

Но, как уже упоминалось, я уверен, что эти данные не относятся к вашему коду. Это небольшие детали, и вы не должны слишком много внимания уделять этому. Python-интерпретатор использует переключатели, потому что они думают, что делает код более удобочитаемым. Почему бы вам не выбрать наиболее удобное для вас использование? Влияние производительности будет довольно небольшим, вам лучше сосредоточиться на читаемости кода на данный момент;)

Изменить. Если это имеет значение, использование хэш-таблицы всегда будет медленнее, чем таблица поиска. Для таблицы поиска вы используете типы перечислений для своих "ключей", и значение извлекается с помощью одного косвенного перехода. Это единая операция сборки. O (1). Для поиска таблицы хешей сначала требуется вычисление хэша, а затем для получения значения, которое дороже.

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

Подводя итог, имеем:

• стоимость (Hash_table) → стоимость (direct_lookup_table)
• cost (direct_lookup_table) ~ = cost (switch), если ваш компилятор переводит коммутаторы в таблицы поиска.
• cost (switch) → cost (direct_lookup_table) (O (N) vs O (1)), если ваш компилятор не переводит коммутаторы и не использует условные обозначения, но я не могу думать о компиляторе, выполняющем это.
• Однако встроенная прямая резьба делает код менее читаемым.

Ответ 3

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

Ответ 4

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

Чтобы получить быстрый переход, ваши значения должны соответствовать следующему правилу: они должны быть последовательными, т.е. 0,1,2,3,4. Вы можете оставить некоторые значения, но такие вещи, как 0,1,2,34,43, вряд ли будут оптимизированы.

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

Ответ 5

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

Ответ 6

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

Такие вопросы, которые лучше или быстрее или эффективнее, бессмысленны, если вы не указали, какую реализацию вы говорите. Например, обработка строки в определенной версии определенной реализации JavaScript была ужасной, но вы не можете экстраполировать ее как функцию соответствующего стандарта.

Я даже зашел так далеко, чтобы сказать, что это не имеет значения, независимо от реализации, поскольку функциональность, предоставляемая switch и std::map, отличается (хотя и перекрывается).

Такие микро-оптимизации практически не нужны, на мой взгляд.