Контрольный стол - Control table - Wikipedia

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

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

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

Типичное использование

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

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

Структура таблицы

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

Одномерные таблицы

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

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

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

ASCIIHexМножество
ноль0000
....00
@4000
А4101
....00
D4404
....00
M4D03
....00
S5302

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

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

Столы ответвления

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

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

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

Многомерные таблицы

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

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

Содержание таблицы

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

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

Приведенная ниже таблица применима только к 'input1', поскольку в таблице не указан конкретный вход.

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

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

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

Разнообразие значений, которые могут быть закодированный в таблице управления во многом зависит от компьютерный язык использовал. язык ассемблера предоставляет широчайшие возможности для типы данных в том числе (для действий) возможность напрямую исполняемого Машинный код. Обычно управляющая таблица будет содержать значения для каждого возможного совпадающего класса ввода вместе с соответствующим указателем на подпрограмму действия. Некоторые языки утверждают, что не поддерживают указатели (напрямую), но, тем не менее, может вместо этого поддерживать индекс который может использоваться для представления «относительного номера подпрограммы» для выполнения условного выполнения, управляемого значением в записи таблицы (например, для использования в оптимизированном ВЫКЛЮЧАТЕЛЬ заявление - разработано с нулевыми пробелами (т.е. разветвленная ветка ) ).

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

Расположение стола

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

Интерпретатор и подпрограммы

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

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

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

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

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

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

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

Примеры контрольных таблиц

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

"CT1" - это пример контрольной таблицы, которая является простой Справочная таблица. Первый столбец представляет входное значение, которое необходимо проверить (подразумевается «IF input1 = x»), и, если TRUE, соответствующий 2-й столбец («действие») содержит адрес подпрограммы, которую должен выполнить вызов (или же Прыгать к - аналогично ВЫКЛЮЧАТЕЛЬ утверждение). По сути, это разветвленная ветка с возвратом (форма "динамическая отправка "). Последняя запись - это случай по умолчанию, когда совпадений не найдено.

CT1

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

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

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

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

  * ------------------ устный переводчик ------------------------------ -------------- * LM R14, R0, = A (4, CT1, N) Установите R14 = 4, R15 -> таблица и R0 = no. записей в таблице (N) TRY CLC INPUT1,0 (R15) ********* Найдено значение в записи таблицы? BE ACTION * loop * YES, загрузить указатель регистра на подпрограмму из таблицы AR R15, R14 * * NO, указать на следующую запись в CT1, добавив R14 (= 4) BCT R0, TRY ********* Вернитесь, пока счет не иссякнет, затем пройдите. действие по умолчанию ... ни одно из значений в таблице не соответствует, сделайте что-нибудь еще LA R15,4 (R15) указывает на запись по умолчанию (за пределами конца таблицы) ACTION L R15,0 (R15) получить указатель на R15, откуда R15 указывает BALR R14, R15 Выполнить подпрограмму («ВЫЗОВ» и возврат) B END go завершить эту программу * ------------------ таблица управления -------- --------------------------------- * * | этот столбец допустимых значений EBCDIC или ASCII проверяется '=' на переменную 'input1' * | | этот столбец - 3-байтовый адрес соответствующей подпрограммы * v v CT1      DC C'A ', AL3 (ADD) НАЧАЛО управляющей таблицы (длина записи 4 байта) DC C'S', AL3 (SUBTRACT) DC C'M ', AL3 (MULTIPLY) DC C'D', AL3 (DIVIDE) N EQU (* -CT1) / 4 количество допустимых записей в таблице (общая длина / длина записи) DC C '?', AL3 (DEFAULT) запись по умолчанию - используется при перетаскивании для перехвата всех входных переменных INPUT1 DS C в этой переменной * ------------------ подпрограммы ----------------------------- ------------- * ДОБАВИТЬ подпрограмму CSECT # 1 (здесь показана как отдельный CSECT, но в качестве альтернативы может быть встроенным кодом). инструкция (и) для добавления BR R14 возвращает подпрограмму SUBTRACT CSECT # 2. инструкция (и) на вычитание возврата BR R14. так далее..

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

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

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

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

  * ------------------ устный переводчик ------------------------------ -------------- * SR R14, R14 ********* Установить R14 = 0 CALC IC R14, INPUT1 * calc * поместить байт EBCDIC в биты нижнего порядка (24– 31) R14 IC R14, CT1X (R14) * * использовать значение EBCDIC в качестве индекса для таблицы CT1X, чтобы получить новый индекс НАЙДЕН L R15, CT1 (R14) ********* получить указатель на подпрограмму с использованием индекса (0,4, 8 и т. Д.) BALR R14, R15 Выполнение подпрограммы («CALL» и возврат или по умолчанию) B END go завершить эту программу * --------------- дополнительно преобразовать таблицу (EBCDIC -> указатель таблицы INDEX) 256 байт ---- * CT1X DC 12AL1 (00,00,00,00,00,00,00,00,00,00,00,00,00,00, 00,00) 12 идентичных наборов по 16 байтов x'00 *, представляющих 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' * ассемблер может использоваться для автоматического вычисления значений индекса и создания значений более удобный * (например, '04' можно заменить символьным выражением 'PADD-CT1' в таблице CT1X выше) * изменен CT1 (добавлено действие по умолчанию, когда индекс = 00, одномерное измерение, полный 31-битный адрес) CT1      DC A (ПО УМОЛЧАНИЮ) index = 00 Начало таблицы управления (4-байтовые адресные константы) PADD DC A (ADD) = 04 PSUB DC A (SUBTRACT) = 08 PMUL DC A (MULTIPLY) = 12 PDIV DC A (DIVIDE) = 16 * остальная часть кода остается такой же, как в первом примере

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

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

  * ------------------ устный переводчик ------------------------------ -------------- * SR R14, R14 ********* Установить R14 = 0 CALC IC R14, INPUT1 * calc * поместить байт EBCDIC в биты нижнего порядка (24– 31) R14 IC R14, CT1X (R14) * * используйте значение EBCDIC в качестве индекса в таблице CT1X, чтобы получить новый индекс SLL R14,2 * * умножить индекс на 4 (дополнительная инструкция)  НАЙДЕН L R15, CT1 (R14) ********* получить указатель на подпрограмму с использованием индекса (0,4, 8 и т.д.) BALR R14, R15 Выполнить подпрограмму («ВЫЗОВ» и возврат или по умолчанию) B END и завершите эту программу * --------------- дополнительная таблица преобразования (EBCDIC -> указатель таблицы INDEX) 256 байт ---- * CT1X DC 12AL1 (00,00,00 , 00,00,00,00,00,00,00,00,00,00,00,00,00,00) 12 идентичных наборов по 16 байтов x'00 '*, представляющих 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' * ассемблер может использоваться для автоматического вычисления значений индекса и создания значений более удобный * (например, '01' можно заменить символическим выражением 'PADD-CT1 / 4' в таблице CT1X выше) * изменен CT1 (индекс теперь основан на 0,1,2,3,4, а не на 0,4 , 8,12,16, чтобы разрешить все 256 вариантов) CT1      DC A (ПО УМОЛЧАНИЮ) index = 00 Начало таблицы управления (4-байтовые адресные константы) PADD DC A (ADD) = 01 PSUB DC A (SUBTRACT) = 02 PMUL DC A (MULTIPLY) = 03 PDIV DC A (DIVIDE) = 04 * остальная часть кода остается такой же, как во втором примере

Язык C примерЭтот пример в C использует две таблицы, первая (CT1) простая линейный поиск одномерная таблица поиска - для получения индекса путем сопоставления ввода (x), а вторая, связанная таблица (CT1p), представляет собой таблицу адресов меток, к которым нужно перейти.

 статический const char  CT1[] = {  "А",   "S",        "М",        "D" };                          / * допустимые входные значения * / статический const пустота *CT1p[] = { &&Добавлять, &&Вычесть, &&Умножить, &&Разделять, &&Дефолт};           / * метки для перехода и по умолчанию * / за (int я = 0; я < размер(CT1); я++)      / * цикл по значениям ASCII * /   {если (Икс==CT1[я]) идти к *CT1p[я]; }       / * найдено -> соответствующий ярлык * / идти к *CT1p[я+1];                           / * не найден -> метка по умолчанию * /

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

 статический const пустота *CT1p[] = {&&Дефолт, &&Добавлять, &&Вычесть, &&Умножить, &&Разделять}; / * 256-байтовая таблица, приведенная ниже, содержит значения (1,2,3,4) в соответствующих позициях ASCII (A, S, M, D), все остальные установлены в 0x00 * / статический 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'}; / * следующий код будет выполняться за постоянное время, независимо от значения входного символа (x) * / я = CT1x(Икс);            / * извлекаем правильный индекс подпрограммы из таблицы CT1x, используя его значение ASCII в качестве индекса изначально * / идти к *CT1p[я];          / * перейти к метке, соответствующей индексу (0 = по умолчанию, 1 = Добавить, 2 = Вычесть ,.) - см. CT1p * /

В следующем примере показано, как подобный эффект может быть достигнут на языках, которые нет поддерживать определения указателей в структурах данных, но делать поддержка индексированного перехода к подпрограмме - содержится в (0 на основе ) массив указателей подпрограмм. Таблица (CT2) используется для извлечения индекса (из 2-го столбца) в массив указателей (CT2P). Если массивы указателей нет поддерживается, оператор SWITCH или его эквивалент может использоваться для изменения потока управления на одну из последовательности программных меток (например: case0, case1, case2, case3, case4), которые затем либо обрабатывают ввод напрямую, либо выполняют вызов ( с возвратом) в соответствующую подпрограмму (по умолчанию, сложение, вычитание, умножение или деление, ..), чтобы справиться с этим.

CT2

вход 1subr #
А1
S2
M3
D4
?0

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

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

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

CT3

вход 1чередоватьsubr #считать
Аа10
Ss20
Mм30
Dd40
??00

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

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

Структурированное программирование или же Код "без перехода", (включая эквивалент 'ДЕЛАТЬ ПОКА ' или же 'для цикла 'constructs), также могут быть приспособлены к соответствующим образом спроектированным структурам управляющих таблиц с "отступом".

CT4 (полная 'программа' для чтения input1 и обработки, повторяется до тех пор, пока не встретится 'E')

вход 1чередоватьsubr #считатьПрыгать
--50-
Eе70-
Аа10-
Ss20-
Mм30-
Dd40-
??00-
--601
CT4P массив указателей
указатель множество
-> По умолчанию
-> Добавить
-> Вычесть
-> Умножить
-> Разделить
-> Прочитать Input1
-> Изменить поток
-> Конец

Рейтинг на основе таблицы

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

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

Таблицы

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

Парадигма программирования

Если бы можно было сказать, что техника контрольных таблиц принадлежит какому-то конкретному парадигма программирования, ближайшей аналогией может быть Программирование на основе автоматов или же "отражающий" (форма метапрограммирование - поскольку можно сказать, что записи таблицы «изменяют» поведение интерпретатора). The interpreter itself however, and the subroutines, can be programmed using any one of the available paradigms or even a mixture. The table itself can be essentially a collection of "необработанные данные " values that do not even need to be compiled and could be read in from an external source (except in specific, platform dependent, implementations using memory pointers directly for greater efficiency).

Analogy to bytecode / virtual machine instruction set

A multi-dimensional control table has some conceptual similarities to байт-код operating on a виртуальная машина, in that a platform dependent "устный переводчик" program is usually required to perform the actual execution (that is largely conditionally determined by the tables content). There are also some conceptual similarities to the recent Общий промежуточный язык (CIL) in the aim of creating a common intermediate 'instruction set' that is independent of platform (but unlike CIL, no pretensions to be used as a common resource for other languages). P-код can also be considered a similar but earlier implementation with origins as far back as 1966.

Получение инструкции

When a multi-dimensional control table is used to determine program flow, the normal "hardware" Счетчик команд function is effectively simulated with either a указатель to the first (or next) table entry or else an индекс к нему. "Fetching" the instruction involves decoding the данные in that table entry – without necessarily copying all or some of the data within the entry first. Programming languages that are able to use указатели have the dual advantage that less накладные расходы is involved, both in accessing the contents and also advancing the counter to point to the next table entry after execution. Calculating the next 'instruction' address (i.e. table entry) can even be performed as an optional additional action of every individual table entry allowing петли и или Прыгать instructions at any stage.

Monitoring control table execution

The interpreter program can optionally save the program counter (and other relevant details depending upon instruction type) at each stage to record a full or partial trace of the actual program flow for отладка цели, горячая точка обнаружение покрытие кода анализ и анализ производительности (see examples CT3 & CT4 above).

Преимущества

  • clarity – Information tables находятся вездесущий и в основном по своей сути понял even by the широкая публика (особенно fault diagnostic tables in product guides )
  • portability – can be designed to be 100% language independent (and platform independent – except for the interpreter)
  • flexibility – ability to execute either примитивы или же подпрограммы transparently and be custom designed to suit the problem
  • compactness – table usually shows condition/action pairing side-by-side (without the usual platform/language implementation dependencies), often also resulting in
    • двоичный файл – reduced in size through less duplication of instructions
    • источник file – reduced in size through elimination of multiple conditional statements
    • improved program load (or download) speeds
  • maintainability – tables often reduce the number of source lines needed to be maintained v. multiple compares
  • locality of reference – compact tables structures result in tables remaining in тайник
  • code re-use – the "interpreter" is usually reusable. Frequently it can be easily adapted to new programming tasks using precisely the same technique and can grow 'organically' becoming, in effect, a стандартная библиотека of tried and tested подпрограммы, controlled by the table definitions.
  • эффективность – systemwide optimization possible. Any performance improvement to the interpreter usually improves все applications using it (see examples in 'CT1' above).
  • extensible – new 'instructions' can be added – simply by extending the interpreter
  • interpreter can be written like an application program

Optionally:-

  • the interpreter can be интроспективный and "self оптимизировать " using runtime метрики collected within the table itself (see CT3 and CT4 – with entries that could be periodically sorted by descending count). The interpreter can also optionally choose the most efficient lookup technique dynamically from metrics gathered at run-time (e.g. size of array, range of values, sorted or unsorted)
  • динамическая отправка – common functions can be pre-loaded and less common functions fetched only on first encounter to reduce объем памяти использование. In-table мемоизация can be employed to achieve this.
  • The interpreter can have debugging, trace and monitor features built-in – that can then be switched on or off at will according to test or 'live' mode
  • control tables can be built 'on-the-fly' (according to some user input or from parameters) and then executed by the interpreter (without building code literally).

Недостатки

  • training requirement – application programmers are not usually trained to produce generic solutions

The following mainly apply to their use in multi-dimensional tables, not the one-dimensional tables discussed earlier.

  • накладные расходы – some increase because of extra level of indirection caused by virtual instructions having to be 'interpreted' (this however can usually be more than offset by a well designed generic interpreter taking full advantage of efficient direct translate, search and conditional testing techniques that may not otherwise have been utilized)
  • Сложный выражения cannot always be used напрямую in data table entries for comparison purposes
(these 'intermediate values' can however be calculated beforehand instead within a subroutine and their values referred to in the conditional table entries. Alternatively, a subroutine can perform the complete complex conditional test (as an unconditional 'action') and, by setting a truth flag as its result, it can then be tested in the next table entry. Видеть Теорема о структурированной программе )

Котировки

Multiway branching is an important programming technique which is all too often replaced by an inefficient sequence of if tests. Питер Наур recently wrote me that he considers the use of tables to control program flow as a basic idea of computer science that has been nearly forgotten; but he expects it will be ripe for rediscovery any day now. It is the key to efficiency in all the best compilers I have studied.

— Дональд Кнут, Structured Programming with go to Statements

There is another way to look at a program written in interpretative language. It may be regarded as a series of subroutine calls, one after another. Such a program may in fact be expanded into a long sequence of calls on subroutines, and, conversely, such a sequence can usually be packed into a coded form that is readily interpreted. The advantage of interpretive techniques are the compactness of representation, the machine independence, and the increased diagnostic capability. An interpreter can often be written so that the amount of time spent in interpretation of the code itself and branching to the appropriate routine is negligible

— Дональд Кнут, Искусство программирования Volume 1, 1997, page 202

The space required to represent a program can often be decreased by the use of interpreters in which common sequences of operations are represented compactly. A typical example is the use of a finite-state machine to encode a complex protocol or lexical format into a small table

— Джон Бентли, Writing Efficient Programs

Jump tables can be especially efficient if the range tests can be omitted. For example, if the control value is an enumerated type (or a character) then it can only contain a small fixed range of values and a range test is redundant provided the jump table is large enough to handle all possible values

— David.A. SPULER, Compiler Code Generation for Multiway Branch Statements as a Static Search Problem

Programs must be written for people to read, and only incidentally for machines to execute.

— "Structure and Interpretation of Computer Programs", preface to the first edition, Abelson & Sussman

Show me your flowchart and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won't usually need your flowchart; it'll be obvious.

— "The Mythical Man-Month: Essays on Software Engineering", Фред Брукс

Смотрите также

Примечания

  1. ^ Programs from decision tables, Humby, E., 2007,Macdonald, 1973 ... Biggerstaff, Ted J. Englewood Cliffs, NJ : Prentice-Hall ISBN  0-444-19569-6
  2. ^ [1]
  3. ^ UML state machine#Hierarchically nested states
  4. ^ Carl Wright, Service Level Corpo. (2002) Program Code Based vs. Table-driven vs. Rule-Based Rating, Rating Matters issue n. 12, 13 November 2002 ISSN  1532-1886
  5. ^ Brian E. Clauser, Melissa J. Margolis, Stephen G. Clyman, Linette P. Ross (1997) Development of Automated Scoring Algorithms for Complex Performance Assessments: A Comparison of Two Approaches Journal of Educational Measurement, Vol. 34, No. 2 (Summer, 1997), pp. 141–161

Рекомендации

внешняя ссылка