✖


Jump to content

Таблица управления

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

Управляющие таблицы — это таблицы , которые управляют потоком управления или играют важную роль в управлении программой. Не существует жестких правил относительно структуры или содержания управляющей таблицы — ее квалифицирующим атрибутом является ее способность каким-либо образом направлять поток управления посредством «выполнения» процессором или интерпретатором . Проектирование таких таблиц иногда называют проектированием на основе таблиц. [1] [2] (хотя обычно это относится к автоматической генерации кода из внешних таблиц, а не к прямым таблицам времени выполнения). В некоторых случаях управляющие таблицы могут быть конкретными реализациями конечных автоматов на основе автоматного программирования . Если существует несколько иерархических уровней управляющей таблицы, они могут вести себя аналогично конечным автоматам UML. [3]

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

В некоторых случаях обслуживание содержимого управляющих таблиц может быть поручено непрограммистам. Например, если введенная пользователем поисковая фраза содержит определенную фразу, URL-адрес (веб-адрес) может быть назначен в таблице, которая контролирует, куда попадает пользователь, осуществляющий поиск. Если фраза содержит слово «юбка», таблица может направить пользователя на страницу «www.shopping.example/catalogs/skirts», которая является страницей каталога товаров с юбками. (Пример URL-адреса на практике не работает). Вместо программистов такой таблицей могут управлять сотрудники отдела маркетинга.

Типичное использование [ править ]

Более продвинутое использование [ править ]

похоже на байт-код , но обычно с операциями, подразумеваемыми самой структурой таблицы

Структура таблицы [ править ]

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

Одномерные таблицы [ править ]

Возможно, в своей простейшей реализации управляющая таблица иногда может быть одномерной таблицей для непосредственной трансляции значения необработанных данных в соответствующее смещение , индекс или указатель подпрограммы с использованием значения необработанных данных либо непосредственно в качестве индекса массива, либо путем выполнения заранее выполнить некоторые базовые арифметические действия с данными. Этого можно добиться за постоянное время (без линейного поиска или двоичного поиска с использованием типичной справочной таблицы в ассоциативном массиве ). В большинстве архитектур это можно выполнить с помощью двух или трех машинных инструкций — без каких-либо сравнений или циклов. Этот метод известен как « тривиальная хэш-функция » или, при использовании специально для таблиц ветвей, « двойная диспетчеризация ». Чтобы это было осуществимо, диапазон всех возможных значений данных должен быть небольшим (например, значение символа ASCII или EBCDIC, которое имеет диапазон шестнадцатеричных значений «00» – «FF». Если фактический диапазон гарантированно будет меньше чем это, массив может быть усечен до размера менее 256 байт).

Таблица для перевода необработанных значений ASCII (A,D,M,S) в новый индекс подпрограммы (1,4,3,2) за постоянное время с использованием одномерного массива

(пробелы в диапазоне в этом примере показаны как «..», что означает «все шестнадцатеричные значения до следующей строки». Первые два столбца не являются частью массива)

ASCII-код Шестигранник Множество
нулевой 00 00
.. .. 00
@ 40 00
А 41 01
.. .. 00
Д 44 04
.. .. 00
М 4D 03
.. .. 00
С 53 02

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

Для двухбайтового значения необработанных данных потребуется минимальный размер таблицы в 65 536 байт – для обработки всех возможностей ввода – при этом допускается всего 256 различных выходных значений. Однако этот метод прямого перевода обеспечивает чрезвычайно быструю проверку и преобразование в (относительный) указатель подпрограммы, если эвристика вместе с достаточным объемом памяти быстрого доступа разрешает его использование.

Таблицы ответвлений [ править ]

Основная статья: Таблица ветвей

Таблица ветвей — это одномерный «массив» последовательных машинного кода инструкций ветвления/перехода , обеспечивающий многоходовой переход к метке программы при разветвлении непосредственно предшествующей и индексированной ветки. Иногда он генерируется оптимизирующим компилятором для выполнения оператора переключения – при условии, что входной диапазон небольшой и плотный, с небольшим количеством пробелов (как это было в предыдущем примере массива) [1] .

Хотя и довольно компактный – по сравнению с многократным эквивалентом If операторы — инструкции ветвления по-прежнему имеют некоторую избыточность, поскольку код операции ветвления и маска кода условия повторяются вместе со смещениями ветвления. Управляющие таблицы, содержащие только смещения меток программы, могут быть созданы для преодоления этой избыточности (по крайней мере, в языках ассемблера), но при этом требуют лишь незначительных затрат времени на выполнение по сравнению с обычной таблицей ветвей.

Многомерные таблицы [ править ]

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

Управляющая таблица может быть построена аналогично оператору переключения, зависящему от языка , но с добавленной возможностью проверки комбинаций входных значений (с использованием условий логических И / ИЛИ ) и потенциального вызова нескольких подпрограмм (вместо одного набора значений). и метки программы «перейти к программе»). (Конструкция оператора переключения в любом случае может быть недоступна или иметь разные реализации на языках высокого уровня ( HLL ). Концепция управляющей таблицы, напротив, не имеет внутренних языковых зависимостей, но, тем не менее, может быть реализована по-разному в зависимости от доступных особенности определения данных выбранного языка программирования.)

Содержимое таблицы [ править ]

Управляющая таблица по существу воплощает « суть » обычной программы, лишенную синтаксиса языка программирования и компонентов, зависящих от платформы (например, IF/THEN DO.., FOR.., DO WHILE.., SWITCH, GOTO, CALL) и ' сжато» до переменных (например, input1), значений (например, «A», «S», «M» и «D») и идентификаторов подпрограмм (например, «Сложить», «вычесть,..» или #1, # 2,..). Структура самой таблицы обычно подразумевает задействованные логические операции (по умолчанию), такие как «проверка на равенство», выполнение подпрограммы и «следующая операция» или следование последовательности по умолчанию (вместо того, чтобы они были явно указаны в операторах программы — по мере необходимости). в других парадигмах программирования ).

Многомерная управляющая таблица обычно, как минимум, содержит пары значение/действие и может дополнительно содержать операторы и информацию о типе, такую ​​как расположение, размер и формат входных или выходных данных, преобразование данных (или другие действия во время выполнения). нюансы обработки) требуется до или после обработки (если это еще не предусмотрено в самой функции). Таблица может содержать или не содержать индексы или относительные или абсолютные указатели на общие или индивидуальные примитивы или подпрограммы, которые должны выполняться в зависимости от других значений в «строке».

Таблица, показанная ниже, применима только к «входу 1», поскольку в таблице не указан конкретный вход.

условия и действия, подразумеваемые структурой

(подразумевается) ЕСЛИ = (подразумевается) выполнять
ценить действие
ценить действие

(Это параллельное сочетание значения и действия имеет сходство с конструкциями в программировании, управляемом событиями , а именно «обнаружение событий» и «обработка событий», но без (обязательно) асинхронной природы самого события)

Разнообразие значений, которые могут быть закодированы в управляющей таблице, во многом зависит от используемого компьютерного языка . Язык ассемблера предоставляет самый широкий диапазон типов данных , включая (для действий) возможность непосредственно исполняемого машинного кода . Обычно управляющая таблица содержит значения для каждого возможного соответствующего класса входных данных вместе с соответствующим указателем на подпрограмму действия. Некоторые языки утверждают, что не поддерживают указатели (напрямую), но, тем не менее, вместо этого могут поддерживать индекс , который можно использовать для представления «относительного номера подпрограммы» для выполнения условного выполнения, контролируемого значением в записи таблицы (например, для использования в оптимизированном SWITCH заявление – разработано с нулевыми пробелами (т.е. многоходовая ветвь )).

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

Расположение стола [ править ]

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

Интерпретатор и подпрограммы [ править ]

Интерпретатор может быть написан на любом подходящем языке программирования, включая язык высокого уровня . Подходяще спроектированный универсальный интерпретатор вместе с хорошо выбранным набором общих подпрограмм (способных обрабатывать наиболее часто встречающиеся примитивы ) потребует дополнительного традиционного кодирования только для новых пользовательских подпрограмм (в дополнение к указанию самой управляющей таблицы). Интерпретатор, опционально, может применяться только к некоторым четко определенным разделам полной прикладной программы (например, к основному контуру управления ), а не к другим, «менее условным» разделам (таким как инициализация программы, завершение и т. д.).

Интерпретатор не обязательно должен быть чрезмерно сложным или создан программистом с глубокими знаниями автора компилятора, и его можно написать так же, как и любую другую прикладную программу, за исключением того, что он обычно разрабатывается с учетом эффективности. Его основная функция — «выполнять» записи таблицы как набор «инструкций». Нет необходимости в синтаксическом анализе записей управляющей таблицы, и поэтому они должны быть спроектированы, насколько это возможно, «готовыми к выполнению», требующими только «подключения» переменных из соответствующих столбцов в уже скомпилированный общий код таблицы. переводчик. Программные инструкции теоретически бесконечно расширяемы и представляют собой (возможно, произвольные) значения внутри таблицы, которые имеют смысл только для интерпретатора. Поток управления интерпретатора обычно представляет собой последовательную обработку каждой строки таблицы, но может быть изменен с помощью определенных действий в записях таблицы.

Таким образом, эти произвольные значения могут быть разработаны с учетом эффективности — путем выбора значений, которые можно использовать в качестве прямых индексов данных или указателей на функции . Для определенных платформ/ языков они могут быть специально разработаны для минимизации длины пути инструкций с использованием значений таблицы ветвей или даже, в некоторых случаях, например, в JIT- » непосредственно исполняемого машинного кода компиляторах, состоять из « фрагментов (или указателей на них).

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

производительности Соображения ​ ​

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

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

Примеры управляющих таблиц [ править ]

Следующие примеры являются произвольными (и для простоты основаны только на одном вводе), однако цель состоит в том, чтобы просто продемонстрировать, как можно реализовать поток управления с помощью таблиц вместо обычных программных операторов. Должно быть ясно, что этот метод можно легко расширить для работы с несколькими входными данными, либо за счет увеличения количества столбцов, либо за счет использования нескольких записей таблицы (с необязательным оператором и/или). Аналогичным образом, используя (иерархические) «связанные» управляющие таблицы, структурное программирование можно осуществить (необязательно с использованием отступов, чтобы выделить подчиненные управляющие таблицы).

«CT1» — это пример управляющей таблицы, которая представляет собой простую таблицу поиска . Первый столбец представляет входное значение, подлежащее проверке (подразумеваемым «IF input1 = x»), и, если TRUE, соответствующий второй столбец («действие») содержит адрес подпрограммы, которую нужно выполнить путем вызова ( или перехода к – аналогично оператору SWITCH ). По сути, это многоходовая ветвь с возвратом (форма « динамической диспетчеризации »). Последняя запись — это случай по умолчанию, когда совпадение не найдено.

КТ1

вход 1 указатель
А -->Добавить
С --> Вычесть
М --> Умножить
Д --> Разделить
? --> По умолчанию

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

языка ассемблера Пример для IBM/360 (максимальный диапазон адресов 16 МБ) или Z/Architecture

В этом первом примере не предпринимается никаких попыток оптимизировать поиск в коде, вместо этого используется простая техника линейного поиска – исключительно для иллюстрации концепции и демонстрации меньшего количества строк исходного кода. Для обработки всех 256 различных входных значений потребуется примерно 265 строк исходного кода (в основном однострочные записи таблицы), тогда как для многократного сравнения и ветвления обычно требуется около 512 строк исходного кода (размер двоичного файла также уменьшается примерно вдвое, каждая запись таблицы требует всего 4 байта вместо примерно 8 байт для серии инструкций «немедленного сравнения»/перехода (для входных переменных большего размера экономия еще больше). 

  * ------------------ interpreter --------------------------------------------*
           LM     R14,R0,=A(4,CT1,N)               Set R14=4, R15 --> table, and R0 =no. of entries in table (N)
  TRY      CLC    INPUT1,0(R15)         *********  Found value in table entry ?
           BE     ACTION                * loop  *  YES, Load register pointer to sub-routine from table
           AR     R15,R14               *       *  NO, Point to next entry in CT1 by adding R14 (=4)
           BCT    R0,TRY                *********  Back until count exhausted, then drop through
  .             default action                          ... none of the values in table match, do something else
           LA     R15,4(R15)                       point to default entry (beyond table end)
  ACTION   L      R15,0(R15)                       get pointer into R15,from where R15 points
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return)
           B      END                              go terminate this program
  * ------------------ control table -----------------------------------------*
  *                 | this column of allowable EBCDIC or ASCII values is tested '=' against variable 'input1'
  *                 |      | this column is the 3-byte address of the appropriate subroutine
  *                 v      v
  CT1      DC     C'A',AL3(ADD)                    START of Control Table (4 byte entry length)
           DC     C'S',AL3(SUBTRACT)
           DC     C'M',AL3(MULTIPLY)
           DC     C'D',AL3(DIVIDE)
  N        EQU    (*-CT1)/4                        number of valid entries in table (total length / entry length)
           DC     C'?',AL3(DEFAULT)                default entry – used on drop through to catch all
  INPUT1   DS     C                                input variable is in this variable
  * ------------------ sub-routines ------------------------------------------*
  ADD      CSECT                                   sub-routine #1 (shown as separate CSECT here but might
  .                                                                alternatively be in-line code)
  .            instruction(s) to add
           BR     R14                              return
  SUBTRACT CSECT                                   sub-routine #2
  .            instruction(s) to subtract
           BR     R14                              return
  . etc..

улучшение производительности интерпретатора в приведенном выше примере

Чтобы сделать выбор в приведенном выше примере, средняя длина пути инструкции (исключая код подпрограммы) равна «4n/2 +3», но ее можно легко уменьшить, где n = 1 до 64, до постоянного времени. с длиной пути «5» и нулевым сравнением , если сначала используется таблица преобразования размером 256 байт для создания прямого индекса к CT1 из необработанных данных EBCDIC. Если n = 6, это будет эквивалентно всего трем последовательным инструкциям сравнения и ветвления. Однако если n<=64, в среднем потребуется примерно в 13 раз меньше инструкций, чем при использовании множественных сравнений. При n=1 до 256 в среднем будет использоваться примерно в 42 раза меньше инструкций – поскольку в этом случае потребуется одна дополнительная инструкция (чтобы умножить индекс на 4).

Улучшенный интерпретатор (в среднем до 26 раз меньше выполняемых инструкций , чем в приведенном выше примере, где n = от 1 до 64, и до 13 раз меньше, чем потребовалось бы при использовании множественных сравнений).

Для обработки 64 различных входных значений требуется примерно 85 строк исходного кода (или меньше) (в основном однострочные записи таблицы), тогда как для многократного сравнения и ветвления потребуется около 128 строк (размер двоичного файла также уменьшается почти вдвое – несмотря на дополнительная таблица размером 256 байт, необходимая для извлечения второго индекса). 

  * ------------------ interpreter --------------------------------------------*
           SR     R14,R14               *********  Set R14=0
  CALC     IC     R14,INPUT1            * calc  *  put EBCDIC byte into lo order bits (24–31) of R14
           IC     R14,CT1X(R14)         *       *  use EBCDIC value as index on table 'CT1X' to get new index
  FOUND    L      R15,CT1(R14)          *********  get pointer to subroutine using index (0,4, 8 etc.)
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return or Default)
           B      END                              go terminate this program
  * --------------- additional translate table (EBCDIC --> pointer table INDEX)  256 bytes----*
  CT1X     DC     12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)   12 identical sets of 16 bytes of x'00
  *                                                                        representing X'00 – x'BF'
           DC     AL1(00,04,00,00,16,00,00,00,00,00,00,00,00,00,00,00)      ..x'C0' – X'CF'
           DC     AL1(00,00,00,00,12,00,00,00,00,00,00,00,00,00,00,00)      ..x'D0' – X'DF'
           DC     AL1(00,00,08,00,00,00,00,00,00,00,00,00,00,00,00,00)      ..x'E0' – X'EF'
           DC     AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)      ..x'F0' – X'FF'
  * the assembler can be used to automatically calculate the index values and make the values more user friendly
  * (for e.g. '04' could be replaced with the symbolic expression 'PADD-CT1' in table CT1X above)
  * modified CT1 (added a default action when index = 00, single dimension, full 31 bit address)
  CT1      DC     A(DEFAULT)          index       =00      START of Control Table (4 byte address constants)
  PADD     DC     A(ADD)                          =04
  PSUB     DC     A(SUBTRACT)                     =08
  PMUL     DC     A(MULTIPLY)                     =12
  PDIV     DC     A(DIVIDE)                       =16
  * the rest of the code remains the same as first example

Дальнейшее улучшение интерпретатора (в среднем до 21 раза меньше выполняемых инструкций (где n>=64) , чем в первом примере, и до 42 раз меньше, чем потребовалось бы при множественном сравнении).

Для обработки 256 различных входных значений потребуется примерно 280 строк исходного кода или меньше (в основном однострочные записи таблицы), тогда как для многократного сравнения и ветвления потребуется около 512 строк (размер двоичного файла также уменьшается почти вдвое после одного раза). более). 

  * ------------------ interpreter --------------------------------------------*
           SR     R14,R14               *********  Set R14=0
  CALC     IC     R14,INPUT1            * calc  *  put EBCDIC byte into lo order bits (24–31) of R14
           IC     R14,CT1X(R14)         *       *  use EBCDIC value as index on table 'CT1X' to get new index
           SLL    R14,2                 *       *  multiply index by 4 (additional instruction)
  FOUND    L      R15,CT1(R14)          *********  get pointer to subroutine using index (0,4, 8 etc.)
           BALR   R14,R15                          Perform the sub-routine ("CALL" and return or Default)
           B      END                              go terminate this program
  * --------------- additional translate table (EBCDIC --> pointer table INDEX)  256 bytes----*
  CT1X     DC     12AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)   12 identical sets of 16 bytes of x'00'
  *                                                                        representing X'00 – x'BF'
           DC     AL1(00,01,00,00,04,00,00,00,00,00,00,00,00,00,00,00)      ..x'C0' – X'CF'
           DC     AL1(00,00,00,00,03,00,00,00,00,00,00,00,00,00,00,00)      ..x'D0' – X'DF'
           DC     AL1(00,00,02,00,00,00,00,00,00,00,00,00,00,00,00,00)      ..x'E0' – X'EF'
           DC     AL1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)      ..x'F0' – X'FF'
  * the assembler can be used to automatically calculate the index values and make the values more user friendly
  * (for e.g. '01' could be replaced with the symbolic expression 'PADD-CT1/4' in table CT1X above)
  * modified CT1 (index now based on 0,1,2,3,4  not 0,4,8,12,16 to allow all 256 variations)
  CT1      DC     A(DEFAULT)          index       =00      START of Control Table (4 byte address constants)
  PADD     DC     A(ADD)                          =01
  PSUB     DC     A(SUBTRACT)                     =02
  PMUL     DC     A(MULTIPLY)                     =03
  PDIV     DC     A(DIVIDE)                       =04
  * the rest of the code remains the same as the 2nd example

языка C Пример В этом примере на C используются две таблицы: первая (CT1) представляет собой одномерную справочную таблицу простого линейного поиска – для получения индекса путем сопоставления входных данных (x), а вторая, связанная таблица (CT1p), представляет собой таблицу адреса меток для перехода. 

 static const char  CT1[] = {  "A",   "S",        "M",        "D" };                          /* permitted input  values */
 static const void *CT1p[] = { &&Add, &&Subtract, &&Multiply, &&Divide, &&Default};           /* labels to goto & default*/
 for (int i = 0; i < sizeof(CT1); i++)      /* loop thru ASCII values                                                    */
   {if (x==CT1[i]) goto *CT1p[i]; }       /* found --> appropriate label                                               */
 goto *CT1p[i+1];                           /* not found --> default label                                               */

Это можно сделать более эффективным, если использовать таблицу размером 256 байт для преобразования необработанного значения ASCII (x) непосредственно в значение плотного последовательного индекса для использования при непосредственном обнаружении адреса ветки из CT1p (т. е. « отображение индекса » с помощью байтового значения индекса). множество). Затем он будет выполняться за постоянное время для всех возможных значений x (если бы CT1p содержал имена функций вместо меток, переход можно было бы заменить динамическим вызовом функции, устраняя переход, подобный переключению, но снижая производительность из-за дополнительных затрат). функции ведения домашнего хозяйства ). 

 static const void *CT1p[] = {&&Default, &&Add, &&Subtract, &&Multiply, &&Divide};
 /* the 256 byte table, below, holds values (1,2,3,4), in corresponding ASCII positions (A,S,M,D), all others set to 0x00 */
 static const char CT1x[]={
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x01', '\x00', '\x00', '\x04', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x03', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x02', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x03', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00',
             '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00', '\x00'};
 /* the following code will execute in constant time, irrespective of the value of the input character (x)                    */
 i = CT1x(x);            /* extract the correct subroutine index from table CT1x using its ASCII value as an index initially  */
 goto *CT1p[i];          /* goto (Switch to) the label corresponding to the index (0=default, 1=Add, 2=Subtract,.) - see CT1p */

Следующий пример ниже иллюстрирует, как аналогичный эффект может быть достигнут в языках, которые не поддерживают определения указателей в структурах данных, но поддерживают индексированное ветвление к подпрограмме, содержащейся в ( начиная с 0 массиве указателей подпрограмм ). Таблица (CT2) используется для извлечения индекса (из 2-го столбца) в массив указателей (CT2P). Если массивы указателей не поддерживаются, можно использовать оператор SWITCH или его эквивалент для изменения потока управления на одну из последовательностей программных меток (например: Case0, Case1, Case2, Case3, Case4), которые затем либо обрабатывают ввод напрямую, либо иначе выполните вызов (с возвратом) соответствующей подпрограммы (по умолчанию, Add, Subtract, Multiply или Divide,...), чтобы справиться с ней.

КТ2

вход 1 суббр #
А 1
С 2
М 3
Д 4
? 0

Как и в приведенных выше примерах, можно очень эффективно преобразовать потенциальные входные значения ASCII (A,S,M,D или неизвестные) в индекс массива указателей без фактического использования поиска в таблице, но здесь это показано в виде таблицы для согласованности с первый пример.

CT2P Массив указателей
указателей массив
--> по умолчанию
-->Добавить
--> Вычесть
--> Умножить
--> Разделить
-->?другое

Могут быть построены (т.е. настроены) многомерные управляющие таблицы, которые могут быть «более сложными», чем приведенные выше примеры, которые могут проверять наличие нескольких условий на нескольких входных данных или выполнять более одного «действия» на основе некоторых критериев соответствия. «Действие» может включать указатель на другую подчиненную управляющую таблицу. В приведенном ниже простом примере неявное условие «ИЛИ» включено в качестве дополнительного столбца (для обработки ввода в нижнем регистре, однако в данном случае это можно было бы также обработать, просто добавив дополнительную запись для каждого символа нижнего регистра, определяющего тот же идентификатор подпрограммы, что и символы верхнего регистра). Также включен дополнительный столбец для подсчета фактических событий времени выполнения для каждого входа по мере их возникновения.

КТ3

вход 1 альтернативный суббр # считать
А а 1 0
С с 2 0
М м 3 0
Д д 4 0
? ? 0 0

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

В таких таблицах, где ряд одинаковых записей таблицы определяет всю логику, номер записи таблицы или указатель может эффективно заменять программный счетчик в более традиционных программах и может быть сброшен с помощью «действия», также указанного в запись таблицы. В приведенном ниже примере (CT4) показано, как расширение предыдущей таблицы за счет включения «следующей» записи (и/или включения подпрограммы «изменения потока» ( прыжка )) может создать цикл (этот пример на самом деле не самый эффективный способ построить такую ​​таблицу управления, но, демонстрируя постепенную «эволюцию» из первых приведенных выше примеров, показывает, как можно использовать дополнительные столбцы для изменения поведения.) Пятый столбец демонстрирует, что с помощью одной записи таблицы можно инициировать более одного действия – в этом случае действие, которое должно быть выполнено после нормальной обработки каждой записи (значения «-» означают «нет условий» или «нет действия»).

Структурированное программирование или код «без перехода» (включающий эквивалент конструкций « DO WHILE » или « for Loop ») также может быть реализовано с помощью соответствующим образом спроектированных и «отступных» структур управляющих таблиц.

CT4 (полная «программа» для чтения ввода 1 и обработки, повторяющаяся до тех пор, пока не встретится буква «E»)

вход 1 альтернативный суббр # считать прыгать
- - 5 0 -
И и 7 0 -
А а 1 0 -
С с 2 0 -
М м 3 0 -
Д д 4 0 -
? ? 0 0 -
- - 6 0 1
CT4P Массив указателей
указателей массив
--> По умолчанию
-->Добавить
--> Вычесть
--> Умножить
--> Разделить
-->Читать ввод1
-->Изменить поток
--> Конец

Табличный рейтинг [ править ]

В специальной области рейтинга телекоммуникаций (связанной с определением стоимости конкретного звонка), Методы рейтингования на основе таблиц иллюстрируют использование контрольных таблиц в приложениях, где правила могут часто меняться из-за рыночных сил. Во многих случаях таблицы, определяющие расходы, могут быть изменены в кратчайшие сроки непрограммистами. [4] [5]

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

Таблицы [ править ]

Таблицу данных электронной таблицы можно рассматривать как двумерную управляющую таблицу, в которой непустые ячейки представляют данные для базовой программы работы с электронными таблицами (интерпретатора). Ячейки, содержащие формулу, обычно имеют префикс знака равенства и просто обозначают особый тип ввода данных, который определяет обработку других ячеек, на которые имеются ссылки, — путем изменения потока управления в интерпретаторе. Именно экстернализация формул из базового интерпретатора четко идентифицирует как электронные таблицы, так и приведенный выше пример «рейтинга на основе правил» как легко идентифицируемые случаи использования контрольных таблиц непрограммистами.

Парадигма программирования [ править ]

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

Аналогия с байт-кодом/набором инструкций виртуальной машины [ править ]

Многомерная управляющая таблица имеет некоторое концептуальное сходство с байт-кодом, работающим на виртуальной машине , в том смысле, что для фактического выполнения обычно требуется зависящая от платформы программа -интерпретатор (которая в значительной степени условно определяется содержимым таблицы). Есть также некоторые концептуальные сходства с недавним Common Intermediate Language (CIL) с целью создания общего промежуточного «набора инструкций», независимого от платформы (но, в отличие от CIL, нет претензий на использование в качестве общего ресурса для других языков). . P-код также можно считать похожей, но более ранней реализацией, возникшей еще в 1966 году.

Получение инструкции [ править ]

Когда многомерная управляющая таблица используется для определения хода программы, обычная «аппаратная» функция счетчика программ эффективно моделируется либо с помощью указателя на первую (или следующую) запись таблицы, либо с помощью индекса к ней. «Извлечение» инструкции включает декодирование данных в этой записи таблицы – без обязательного предварительного копирования всех или некоторых данных внутри записи. Языки программирования, которые могут использовать указатели, имеют двойное преимущество: требуется меньше накладных расходов как при доступе к содержимому, так и при перемещении счетчика так, чтобы он указывал на следующую запись таблицы после выполнения. Вычисление адреса следующей «инструкции» (т.е. записи таблицы) может даже выполняться как необязательное дополнительное действие для каждой отдельной записи таблицы, позволяющее выполнять циклы и/или инструкции перехода на любом этапе.

Мониторинг выполнения таблицы управления [ править ]

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

Преимущества [ править ]

  • ясность – информационные таблицы распространены повсеместно и по большей части понятны даже широкой публике (особенно таблицы диагностики неисправностей в руководствах по продуктам ).
  • переносимость - может быть на 100% независимым от языка (и платформы - за исключением интерпретатора)
  • гибкость – способность прозрачно выполнять примитивы или подпрограммы и индивидуально разрабатывать их для решения проблемы.
  • компактность – таблица обычно показывает пары условие/действие рядом (без обычных зависимостей реализации платформы/языка), что часто также приводит к
    • двоичный файл – уменьшен в размере за счет меньшего дублирования инструкций
    • исходный файл – уменьшен в размере за счет исключения нескольких условных операторов
    • улучшена скорость загрузки (или выгрузки) программы
  • удобство обслуживания — таблицы часто уменьшают количество строк исходного кода, которые необходимо поддерживать, по сравнению с множественными сравнениями.
  • локальность ссылки – компактные структуры таблиц приводят к тому, что таблицы остаются в кеше
  • повторное использование кода – «интерпретатор» обычно можно использовать повторно. Часто ее можно легко адаптировать к новым задачам программирования, используя точно такую ​​же технику, и она может расти «органически», становясь, по сути, стандартной библиотекой проверенных и проверенных подпрограмм , управляемых определениями таблиц.
  • эффективность – возможна общесистемная оптимизация. Любое улучшение производительности интерпретатора обычно улучшает все приложения, использующие его (см. примеры в разделе «CT1» выше).
  • расширяемый – можно добавлять новые «инструкции» – просто расширяя интерпретатор.
  • интерпретатор может быть написан как прикладная программа

Опционально:-

  • интерпретатор может быть интроспективным и « самооптимизироваться », используя метрики времени выполнения , собранные в самой таблице (см. CT3 и CT4 – с записями, которые можно периодически сортировать по убыванию количества). Интерпретатор также может дополнительно динамически выбирать наиболее эффективный метод поиска на основе показателей, собранных во время выполнения (например, размер массива, диапазон значений, отсортированных или несортированных).
  • динамическая диспетчеризация — общие функции могут быть предварительно загружены, а менее распространенные функции выбираются только при первом обнаружении, чтобы уменьшить использование памяти . в таблице . мемоизацию Для достижения этой цели можно использовать
  • Интерпретатор может иметь встроенные функции отладки, отслеживания и мониторинга, которые затем можно включать или отключать по желанию в зависимости от тестового или «живого» режима.
  • управляющие таблицы могут создаваться «на лету» (в соответствии с вводом пользователя или параметрами), а затем выполняться интерпретатором (без буквального создания кода).

Недостатки [ править ]

  • требование к обучению – прикладные программисты обычно не обучаются созданию универсальных решений.

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

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

Цитаты [ править ]

Многоходовое ветвление — важный метод программирования, который слишком часто заменяется неэффективной последовательностью проверок if. Питер Наур недавно написал мне, что считает использование таблиц для управления ходом выполнения программы основной идеей информатики, которая почти забыта; но он ожидает, что со дня на день оно созреет для повторного открытия. Это ключ к эффективности всех лучших компиляторов, которые я изучал.

— Дональд Кнут , Структурное программирование с переходом к операторам.

Есть еще один способ взглянуть на программу, написанную на интерпретативном языке. Его можно рассматривать как серию вызовов подпрограмм, идущих один за другим. Такая программа фактически может быть расширена до длинной последовательности вызовов подпрограмм, и, наоборот, такая последовательность обычно может быть упакована в закодированную форму, которая легко интерпретируется. Преимуществом методов интерпретации являются компактность представления, машинная независимость и расширенные диагностические возможности. Интерпретатор часто может быть написан так, что время, затрачиваемое на интерпретацию самого кода и переход к соответствующей процедуре, будет незначительным.

- Дональд Кнут , Искусство компьютерного программирования, том 1, 1997, стр. 202.

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

— Джон Бентли , «Написание эффективных программ»

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

— Дэвид А. SPULER, Генерация кода компилятора для операторов многопутевого ветвления как задача статического поиска

Программы должны быть написаны для того, чтобы их могли читать люди, и лишь вскользь для того, чтобы их могли выполнять машины.

- «Структура и интерпретация компьютерных программ», предисловие к первому изданию, Abelson & Sussman.

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

— «Мифический человеко-месяц: очерки по разработке программного обеспечения», Фред Брукс

См. также [ править ]

Примечания [ править ]

  1. ^ Программы на основе таблиц решений , Хамби, Э., 2007, Макдональд, 1973 ... Биггерстафф, Тед Дж. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл ISBN   0-444-19569-6
  2. ^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 10 июня 2016 года . Проверено 17 мая 2016 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
  3. ^ Конечный автомат UML#Иерархически вложенные состояния
  4. ^ Карл Райт, Service Level Corpo. (2002) Рейтинг программ на основе кода, таблиц и правил , рейтинг имеет значение, выпуск n. 12, 13 ноября 2002 г. ISSN   1532-1886
  5. ^ Брайан Э. Клаузер, Мелисса Дж. Марголис, Стивен Г. Клайман, Линетт П. Росс (1997) Разработка автоматизированных алгоритмов оценки для комплексной оценки производительности: сравнение двух подходов. Журнал образовательных измерений, Vol. 34, № 2 (лето 1997 г.), стр. 141–161.

Ссылки [ править ]

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Control_table&oldid=1191259213"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 5a32689944f1d3aaf71a717647494528__1703238720
URL1:https://arc.ask3.ru/arc/aa/5a/28/5a32689944f1d3aaf71a717647494528.html
Заголовок, (Title) документа по адресу, URL1:
Control table - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)