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

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

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

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

  • Преобразование входных значений в:
    • индекс , для последующего разветвления или указатель поиска
    • имя программы, относительный номер подпрограммы , метка программы или смещение программы для изменения потока управления
  • Управление основным циклом в программировании, управляемом событиями, с помощью управляющей переменной для переходов между состояниями
  • Управление программным циклом для приложений обработки онлайн-транзакций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CT1

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

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

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

В этом первом примере не делается попыток оптимизировать поиск в коде, и вместо этого используется простой метод линейного поиска - исключительно для иллюстрации концепции и демонстрации меньшего количества строк исходного текста. Для обработки всех 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 иди завершить эту программу * ------------------ таблица управления ----------------------------- ------------ * * | этот столбец допустимых значений EBCDIC или ASCII проверяется '=' на переменную 'input1' * | | этот столбец - 3-байтовый адрес соответствующей подпрограммы * vv CT1 DC C'A ', AL3 (ADD) СТАРТ управляющей таблицы (длина записи 4 байта) DC C'S ', AL3 (ВЫЧИСЛЕНИЕ) DC C'M ', AL3 (НЕСКОЛЬКО) DC C'D ', AL3 (РАЗДЕЛИТЬ) N EQU (* -CT1) / 4 количество допустимых записей в таблице (общая длина / длина записи) DC C '?', AL3 (DEFAULT) запись по умолчанию - используется при перетаскивании, чтобы перехватить все Входная переменная INPUT1 DS C находится в этой переменной * ------------------ подпрограммы ---------------------------- -------------- * Подпрограмма ADD 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 Выполнение подпрограммы («ВЫЗОВ» и возврат или по умолчанию) B END иди завершить эту программу * --------------- дополнительная таблица перевода (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 (DEFAULT) index = 00 START of Control Table (4-байтовые адресные константы) PADD DC A (ADD) = 04 PSUB DC A (ВЫЧИСЛЕНИЕ) = 08 PMUL DC A (НЕСКОЛЬКО) = 12 PDIV DC A (РАЗДЕЛЕНИЕ) = 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) 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 (DEFAULT) index = 00 START of Control Table (4-байтовые адресные константы) PADD DC A (ADD) = 01 PSUB DC A (ВЫЧИСЛЕНИЕ) = 02 PMUL DC A (НЕСКОЛЬКО) = 03 PDIV DC A (РАЗДЕЛЕНИЕ) = 04 * остальная часть кода остается такой же, как во втором примере

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

 static  const  char  CT1 []  =  {  "A" ,  "S" ,  "M" ,  "D"  };  / * Разрешено входных значений * /  статический  константный  пустот  * CT1p []  =  {  && Добавить ,  && Вычесть ,  && Умножить ,  && Разделить ,  && По умолчанию };  / * метки для перехода и по умолчанию * /  for  ( int  i  =  0 ;  i  < sizeof (CT1 );  i ++ )  / * цикл по значениям ASCII * /  { if  ( x == CT1 [ i ])  goto  * CT1p [ i ];  }  / * найдено -> соответствующий ярлык * /  goto  * CT1p [ i + 1 ];  / * не найден -> метка по умолчанию * /

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

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

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

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

CT3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Необязательно:-

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

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

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

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

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

Котировки [ править ]

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

-  Дональд Кнут , Структурированное программирование с использованием операторов перехода к инструкциям

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

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

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

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

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

-  Дэвид А.А. SPULER, Генерация кода компилятора для выражений многосторонних переходов как задача статического поиска

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

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

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

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

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

  • Автоматное программирование
  • Архитектура, ориентированная на базу данных
  • Тестирование на основе данных
  • Таблица решений
  • Конечный автомат
  • Тестирование на основе ключевых слов
  • Указатель (компьютерное программирование)
  • Оператор переключения - многосторонний переход к одной из нескольких меток программы в зависимости от одной входной переменной
  • Резьбовой код
  • Распределение токенов

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

  1. ^ Программы из таблиц решений , Humby, E., 2007, Macdonald, 1973 ... Biggerstaff, Ted J. Englewood Cliffs, NJ: Prentice-Hall ISBN  0-444-19569-6
  2. ^ [1]
  3. ^ Конечный автомат UML # Иерархически вложенные состояния
  4. ^ Карл Райт, Уровень обслуживания Корпорация. (2002) Рейтинг на основе программного кода против рейтинга на основе таблицы против рейтинга на основе правил , выпуск № 12, 13 ноября 2002 ISSN 1532-1886 
  5. ↑ Брайан Э. Клаузер, Мелисса Дж. Марголис, Стивен Г. Клайман, Линетт П. Росс (1997) Разработка автоматизированных алгоритмов подсчета баллов для комплексных оценок успеваемости: сравнение двух подходов. Журнал образовательных измерений, Vol. 34, No. 2 (лето 1997 г.), стр. 141–161.

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

  • Методология на основе таблицы решений
  • Структурное программирование с ходом в отчетность по Дональду Кнутом
  • Генерация кода компилятора для операторов многостороннего ветвления как задача статического поиска 1I994, Дэвид А. Спулер

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

  • Оператор Switch в Windows PowerShell описывает расширения стандартного оператора switch (предоставляя некоторые аналогичные функции для управляющих таблиц)
  • Пример контрольной таблицы на языке «C» с использованием указателей , автор: Кристофер Сотелл, 1993 г., факультет компьютерных наук Оклендского университета
  • Дизайн на основе стола от Уэйна Канниворта из DataKinetics
  • От требований к таблицам до кода и тестов Джордж Брук
  • Некоторые комментарии по поводу использования таблиц неоднозначных решений и их преобразования в компьютерные программы сделаны PJH King и RG Johnson, Univ. Лондона, Лондона, Великобритании
  • Неоднозначность таблиц решений с ограниченным входом от PJH King
  • Преобразование таблиц решений в компьютерные программы с помощью методов маски правил PJH King
  • Анализ супероптимизатора генерации кода многосторонних ветвей раздел 3.9, стр. 16 сопоставление индексов
  • Переход к таблицам с помощью массивов указателей функций в C / C ++ Джонс, Найджел. "Массивы указателей на функции [3] " Программирование встроенных систем, май 1999 г.
  • Статистика просмотров этой статьи за декабрь 2009 г.

  • Программное обеспечение для моделирования с помощью конечных автоматов - практический подход
  • Таблицы конечных состояний для общих приложений компьютерного программирования, январь 1988 г., Марк Лейнингер
  • MSDN: обработка событий на основе триггеров
  • Контрольный стол на c2.com