Перейти к началу страницы

Ответ 1

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

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

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

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

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

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

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

Ответ 3

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

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

...

void fz() { 
 printf("it 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'])();

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

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

Ответ 4

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

Ответ 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, это не будет хорошим методом, и упомянутые вами хеш-таблицы/словарные методы могут вступить в игру.

Ответ 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}

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

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

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

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

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, чтобы заставить таблицу перехода, она использовала ifs ниже этого числа операторов case)

Обратите внимание, что маленькие отверстия будут в таблице перехода, чтобы сделать 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