Порядок случая в Операторе переключения может варьироваться производительность?
Позвольте говорят, что у меня есть оператор переключения как ниже
switch(alphabet) {
case "f":
//do something
break;
case "c":
//do something
break;
case "a":
//do something
break;
case "e":
//do something
break;
}
Теперь предположите, что я знаю что частота наличия Alphabet e самым высоким сопровождаемый a, c и f соответственно. Так, я просто реструктурировал case порядок оператора и сделанный ими следующим образом:
switch(alphabet) {
case "e":
//do something
break;
case "a":
//do something
break;
case "c":
//do something
break;
case "f":
//do something
break;
}
Будет второе switch оператор быть быстрее, чем первое switch оператор? Если да и если в моей программе я должен назвать это switch в заявлении много раз говорится, который будет существенным улучшением? Или если не в в любом случае я могу использовать свое знание частоты для улучшения производительности?
4 ответа
Не настолько, чтобы вас беспокоило. Это, конечно, не то, что можно предсказать.
С метками строковых регистров компилятор фактически использует внутреннюю хэш-таблицу, которая сопоставляет строки с индексами в таблице переходов. Таким образом, операция на самом деле O(1) - независима от количества меток.
Что касается целочисленных меток, то я считаю, что фактический код, который генерируется, зависит от количества меток и от того, являются ли числа последовательными (или «почти» последовательными). Если они последовательны (1, 2, 3, 4, ...), то они просто превратятся в таблицу прыжков. Если их много, то будет использоваться таблица Hashtable+jump (как со строками). Если меток всего несколько, и они не являются таблицей, которую нужно немедленно преобразовать в таблицу переходов, только тогда будет преобразован в серию if.. тогда.. другие заявления.
В целом, однако, вы должны писать код так, чтобы вы могли его читать, а не для того, чтобы компилятор мог создавать «более быстрый» код.
(Обратите внимание, что мое описание выше является деталью реализации того, как компилятор C# работает внутри: вы не должны полагаться на то, что он всегда работает таким образом - на самом деле, он может даже не работать точно так же сейчас, но, по крайней мере, это общая идея).
Они имеют одинаковую производительность для относительно небольшого набора значений. Я пытался проверить ассембленный код программы C раньше, компилятор создает таблицу переходов из всех значений, которые у вас есть в операторе switch.
Но если значения регистров слишком много, можно с уверенностью сказать, что они выродятся в , если else if, поэтому размещение вашего случая «E» сверху, безусловно, ускорит ситуацию.
Он также применим в C#, C# также создает таблицу переходов для операторов switch с небольшим набором, хотя и только для смежных значений. Таким образом, это O(1), нет многократного тестирования, даже если первые значения не совпадают.
Это зависит от того, как компилятор реализует оператор switch.
Во-первых, вы не можете произвольно изменять порядок; если у вас есть один блок case в C-подобном языке (C, C++, C#, Java, ...), и этот блок case не заканчивается на break, вы не можете переставить регистры, потому что отсутствие break означает, что компилятор должен реализовать переход к следующему случаю. Если мы проигнорируем эту особую ситуацию, вы можете переставлять остальные случаи.
Если количество случаев невелико, компилятор может реализовать проверку случаев последовательностью сравнений. Если число случаев скромное, он может построить сбалансированное двоичное дерево из случаев. Если число случаев велико, большинство компиляторы реализуют индексированную ветвь на значении переключателя, если оно из плотного набора. Если часть множества значений случаев плотная, а часть нет, компилятор может разделить случаи на группы, используя двоичное дерево для выбора плотного множества и индексированного перехода внутри плотного множества. (На самом деле, компилятор технически может делать все, что передает управление в соответствующему случаю, но чаще всего это одно из вышеперечисленных действий).
Вы видите, что порядок может иметь значение, а может и не иметь, в зависимости от того, как компилятор реализует переключатель. Для большинства хороших компиляторов это не имеет большого значения.
Я думаю, что случай переключателя состоит в том, что он перебирает все случаи сверху вниз, чтобы найти совпадение. Если он совпадает, он останавливается на этом.
Итак, если вы внесли изменения в расстановку приоритетов для частотных случаев, ответ - да, это может как-то помочь с производительностью. Но я считаю, что это не сильно поможет.