Вопрос о Случае Переключателя Таблицы переходов

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

switch (i) {
   case 1: printf("case 1"); break;
   case 2: printf("case 2"); break;
   case 3: printf("case 3"); break;
}

, он может генерировать код, примерно эквивалентный примерно такому:

void case1() { printf("case 1"); }
void case2() { printf("case 2"); }
void case3() { printf("case 3"); }

typedef void (*pfunc)(void);

pfunc functions[3] = {case1, case2, case3};

if ((unsigned)i<3)    
    functions[i]();

Это имеет сложность O (K). Типичная хеш-таблица также имеет примерно O (K) ожидаемую сложность, хотя в худшем случае обычно O (N). Таблица переходов обычно работает быстрее, но обычно она будет использоваться только в том случае, если таблица будет достаточно плотной, тогда как хеш-таблица / словарь работает достаточно хорошо, даже когда случаев будет довольно мало.

Предположим, у вас есть массив процедур:

void fa() { 
 printf("a\n");
}

...

void fz() { 
 printf("it's z!\n");
}



typedef void (*F)();
F table[26]={fa,fb,...,fz};

Предположим, вы принимаете символ (из az) ввода от пользователя и запускаете fc:

char c;
switch(c) {
   case 'a': fa();break;
   case 'b': fb();break;
   ...
   case 'z': fz();break;       
   default: exit(-1);
}

В идеале это должно быть заменено чем-то вроде :

if (c<'a' || c>'z') exit(-1);
else (*table[c-'a'])();

Естественно, вы могли бы увеличить таблицу, чтобы не было необходимости в проверке диапазона.

Компилятор будет делать это для произвольного кода, не обязательно только для вызовов функций, и будет делать это, сохраняя адрес для перехода to (по сути, goto). C не поддерживает напрямую какие-либо вычисляемые goto (индексацию в таблицу или что-то еще), но инструкции ЦП для этого довольно просты.

Компиляция для оператора switch может принимать разные формы в зависимости от случая. Если случаи расположены близко друг к другу, это не проблема: используйте таблицу переходов. Если случаи сильно различаются, используйте if (case == value) или используйте карту. Или компилятор может использовать комбинацию: острова таблиц переходов, определяемые проверками if диапазонов таблиц переходов.

Таблица переходов - это просто массив указателей на функции, вы можете представить таблицу переходов примерно так:

int (* functions [10]) (); / * Массив из 10 указателей функций * /

Насколько я понимаю, это используется с таким выражением case: каждое условие case _ будет индексом в этом массиве, например:

switch( a ) {
    case 1:  // (*functions[1])() // Call function containing actions in case of 1
        ...  
    case 2:  // (*functions[2])() // Call function containing actions in case of 2
        ...

Каждый case, преобразуется в простые функции [a]. Это означает, что доступ к функциям [9] осуществляется так же быстро, как и к функциям [1]. Давая вам время O (1), о котором вы упомянули.

Очевидно, что если у вас есть случай 1 и случай 4907, это не будет хорошим методом, и упомянутые вами методы хеш-таблицы / словаря могут пригодиться .