Вопрос о переключателе переходного стола

Question

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

Мне сказали, что таблица переходов - это структура O (1), которую генерирует компилятор, который делает поиск значений практически настолько быстрым, насколько вы можете получить. Однако в некоторых случаях Hashtable / Dictionary может быть быстрее. Мне также сказали, что это будет работать, только если регистр коммутатора содержит ordered значения данных.

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

Answer 1

A таблица переходов - это абстрактная структура, используемая для передачи управления в другое место. Goto, continue и break аналогичны, за исключением того, что они всегда переносятся в определенное место вместо одной возможности из многих. В частности, этот поток управления не совпадает с вызовом функции. (Статья Википедии о таблицах ветвей связана.)

A оператор switch - это способ записи таблиц переходов на C / C ++. Предоставляется только ограниченная форма (можно включать только целочисленные типы), чтобы сделать реализацию проще и быстрее в этом общем случае. (Как эффективно реализовать таблицы переходов было изучено гораздо больше для целочисленных типов, чем для общего случая.) Классическим примером является Устройство Даффа .

Однако, полная возможность таблицы перехода часто не требуется , например, когда в каждом случае будет оператор break. Эти «таблицы ограниченных переходов» представляют собой другой шаблон , в котором используется только хорошо изученная эффективность таблицы переходов, и они распространены, когда каждое «действие» не зависит от других.

---

Фактические реализации таблиц переходов принимают разные формы, в основном отличающиеся способом выполнения ключа для отображения индекса. В этом отображении используются такие термины, как «словарь» и «хэш-таблица», и эти методы можно использовать независимо от таблицы переходов. Утверждение, что некоторый код «использует таблицу переходов» само по себе не означает, что у вас есть поиск O (1).

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

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

Answer 2

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

Answer 3

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

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

...

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



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

Предположим, вы принимаете символ (из a-z) ввода от пользователя и запускаете 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'])();

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

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

Answer 4

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

Answer 5

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

int (*functions[10])(); /* Array of 10 Function Pointers */

Насколько я понимаю, это используется с оператором 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
        ...

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

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

Answer 6

Для дальнейшего уточнения ответ Джерри и другие

Дано:

int x=1;
switch (i) {
   case 1: x=6; break;
   case 2: x++;
   // Fall through
   case 3: x+=7; break;
}

у вас может быть что-то вроде следующего:

int f1() {return 6;}
int f2() {return 1+f3();}
int f3() {return 8;}

Компилятор может использовать таблицу переходов для индексации {f1, f2, f3}

Компилятор может делать встраивание при создании таблицы, в которой f1, f2, f3 устанавливает x непосредственно на 6,9,8

Но если вы написали функции и откатили свою собственную таблицу переходов, f1,f2,f3 может быть где угодно, но компилятор будет знать, чтобы поместить их близко к switch, создавая гораздо лучшую локальность кода, чем вы могли бы.

Обратите внимание, что во многих случаях компилятор генерирует защиту для проверки, находится ли i в диапазоне (или для обработки default), и если вы уверены, что это всегда один из случаев, вы можете пропустить это

Интересно то, что для небольшого числа случаев и для разных флагов компилятора (в зависимости от компилятора) switch не будет использовать таблицу, а будет просто делать if, аналогично:

if (i==1) x=f1();
else if (i==2) x=f2();
else if (i==3) x=f3();

или он может оптимизировать это (где простые тесты являются одной инструкцией) для:

x=(i==1) ? f1()
: (i==2) ? f2()
: (i==3) ? f3()
: x;

Лучший совет - взглянуть на сгенерированную сборку, чтобы увидеть, что компилятор сделал с вашим кодом в вашей архитектуре. G ++ в Linux / intel сгенерирует что-то вроде следующего, если есть таблица переходов

( примечание: мне нужно было перейти к 5 case операторам, чтобы вызвать таблицу переходов, она использовала, если значение меньше 10 * * операторов )

Обратите внимание, что в таблице переходов будут маленькие отверстия для выполнения default

int foo(int i)
{
   int x=1;
   switch (i) {
       case 1: x=6; break;
       case 2: x++;
        // Fall through
       case 3: x+=7; break;
       case 4: x+=2; break;
       case 5: x+=9; break;
    }
  return x;
}

сгенерирует следующий код сборки ( // комментарии мои ):

        cmp     edi, 5                     //make sure it is not over 5
        ja      .L2                        //jump to default case
        mov     edi, edi
        jmp     [QWORD PTR .L4[0+rdi*8]]   // use the jump table at label L4:
.L4:
        .quad   .L2                        // if i=0, set x=1 (default)
        .quad   .L9                        // f1() see below
        .quad   .L10                       // f2() see below
        .quad   .L6                        // f3() see below
        .quad   .L7                        // f4() see below
        .quad   .L8                        // f5() see below
.L10:
        mov     eax, 9                     // x=9
        ret
.L9:
        mov     eax, 6                     // x=6
        ret
.L8:
        mov     eax, 10                    // x=10
        ret
.L6:
        mov     eax, 8                     // x=8
        ret
.L7:
        mov     eax, 3                     // x=3
        ret
.L2:
        mov     eax, 1                     // default, x was 1, noop is: x=1
        ret