Оптимизация переключателя для многих случаев гарантирует равное время доступа для какого-либо случая? (C++)
Я видел ответы здесь для определенных языков о переключателях больше чем с 5 случаями, оптимизируемыми с таблицами переходов для гарантии постоянного времени доступа для любого случая.
Это так для C / C++?
Это в особенности для gcc? для Visual Studio?
В противном случае был бы, сортируя случаи в порядке справки частоты возникновения?
6 ответов
Это то, что компилятор сделает для вас. В случае GCC он будет использовать таблицу переходов.
-121--3579345-Я думаю, что хорошее совпадение для вашей проблемы Twill : простой язык сценариев для просмотра веб-страниц.
Другой проверяемый - Ветряная мельница (разновидность селена, но все написаны на Python).
-121--2643514-Стандарт ничего не гарантирует о том, как будет реализована инструкция switch. Я никогда не видел, чтобы компилятор создавал хеш-таблицу, хотя довольно многие создадут таблицу прыжков. Если моя память не работает еще хуже, чем обычно, и VS, и gcc могут создавать таблицы скачков, когда случаи достаточно плотные (для различных значений «достаточно»). К сожалению, практически невозможно сказать (или обязательно даже выяснить), когда сортировка по частоте появления поможет - она отличается не только между компиляторами, но даже между различными версиями одного и того же компилятора.
For gcc's implementation see:
http://old.nabble.com/optimization-of-switch-statements-on-i386-to15366926.html#a15367662
- C и C++ ничего не гарантируют о времени работы операторов переключения.
- Боюсь, я не знаю подробностей реализации ни для одного компилятора. Вероятно, это зависит от флагов оптимизации.
- Сортировка случаев не гарантированно поможет, опять же она не задана стандартом, и ваша реализация может быть или не быть:
- Делайте разные вещи в соответствии с опциями компилятора
- Документируйте, что он делает
- Гарантируйте, что он не изменит того, что делает в будущих версиях
- Полностью игнорируйте порядок случаев в исходном коде, и переупорядочивайте их, как ему заблагорассудится. Допуская, конечно, что случаи "независимы": никаких падений; никаких объявлений переменных, начинающихся в одном случае и охватывающих другой; ничего больше я не забыл.
c (а по расширению c++) включает только целочисленные типы, поэтому хэширование не требуется. Компилятор обычно использует идиому, соответствующую архитектуре, для которой вы компилируете. Это может быть индексированная адресация (если используется небольшой диапазон), таблицы переходов или что-то совершенно другое.
Это то, что компилятор сделает для вас. В случае GCC это будет использовать таблицу прыжка.