AOP_Tom1 (1021736), страница 55
Текст из файла (страница 55)
22. Проходы: (а) чстырехпроходный алгоритм и (Ь) однопроходный алгоритм. граммировать следующим образом. ООТ ЯТЗ ЯТА ООТХ ЗМР 1М ЯТЗ ЬОА 1МХ 3МР 1ИХ НОЬРА Сохранить А при выходе иэ 1И. ООТ1 ООТХ Н01.РА Восстановить А при выходе из ОПТ. 1М1 $ (4) Существует важная связь ма~иду сопрограммами и многопроходными алгариазмами. Например, описанный выше процесс преобразования можно выполнить за два отдельных прохода. Можно сначала выполнить только сопрограмму 1М, применяя ее ко всему вводу и записывая каждый символ с соответствующим числом повторений на магнитную ленту, а затем перемотать ленту в начало и выполнить только сопрограмму ООТ, выбирая символы с ленты группами по три.
Такой процесс называется двухпроходным. (На интуитивном уровне термин 'проход" воспринимается как полный просмотр входных данных. Это определение является неточным, и во многих алгоритмах совсем не очевидно, чему равно число выполненных проходов. Но, несмотря на некоторую неопределенность данного термина, полезно понять его на интуитивном уровне.) На рис.
22, (а) показан четырехпроходный процесс. Во многих случаях будет оказываться, что такой же процесс можно выполнить только за один проход, как показано в части (Ь) рисунка, если заменить сопрограммами А, В„С, О соответствующие проходы А, В, С, Р. Сопрограмма А вызывает В, после того как во время прохода А элемент выходных данных записан на ленту 1. Сопрограмма В вызывает А, после того как во время прохода В элемент входных данных считан с ленты 1.
Сопрограмма В вызывает С, после того как во время прохода В элемент выходных данных записан на ленту 2 и т. д. Пользователи ПМ1Ха узнают в этом "канал", который обозначается как ПроходА ~ ПроходВ ~ ПроходС ( Ороходр. Программы, соответствующие проходам В, С и О, иногда называются фильтрами. И наоборот, процесс, выполняемый и сопрограммами, часто можно преобразовать в и-проходный процесс. Именно из-за этого соответствия имеет смысл провести сравнительный анализ м(югопроходных и однопроходных алгоритмов.
а) Психологическое отличие Для одной и той же задачи, как правило, проще создать и понять многопроходный алгоритм, чем однопроходный. Процесс, разделенный на ряд небольших шагов, выполняющихся один после другого, понять намного легче, чем запутанную процедуру, в которой множество преобразований выполняется одновременно. Кроме того, если нужно написать большую серьезную программу, над которой будет совместно работать многочисленная группа разработчиков, то многопроходный алгоритм поможет естественным путем распределить работу между участниками проекта.
Но такие преимущества многопроходного алгоритма присущи и сопрограммам, так как каждую из них можно написать, по существу, отдельно от других, а связь межлу сопрограммами превратит явно многопроходный алгоритм в однопроходный процесс. Ь) Разница во времени выполнения. В однопроходном алгоритме не нужно тратить время на то, чтобы упаковать, записать, прочитать и распаковать промежуточные данные, которые передаются между проходами (например, информация на лентах на рис. 22). Поэтому однопроходный алгоритм выполняется быстрее.
с) Различие в обвеме памяши. Для однопроходного алгоритма необходимо хранить в памяти все программы одновременно, в то время квк для многопроходного алгоритма можно сохранять в памяти только по одной программе. Этот фактор может отразиться на скорости выполнения программы даже в большей степени, чем фактор, указанный в и. (Ь). Например, многие компьютеры имеют ограниченный объем "быстродействующей памяти" и болыпой объем "медленной памяти". Если каждый проход поместится в быстрой памяти, то вся программа выполнится значительно быстрее, чем в случае использования сопрограмм в одном проходе (так как при использовании сопрограмм большинство программ, скорее всего, будут помещены в "медленную память" либо будут много раз загружаться и выгружаться из быстрой памяти).
Иногда возникает необходимость в разработке алгоритмов сразу для нескольких компьютерных конфигураций, одни из которых имеют больший объем памяти, чем другие. В таких случаях можно написать программу в виде набора сопрограмм и поставить число проходов в зависимость от размера памяти: загрузить сразу столько сопрограмм, сколько поместится, а подачу данных по недостающим связям обеспечить с помощью подпрограмм ввода или вывода.
Несмотря на важность связи между сопрограммами и проходами, нужно иметь в виду, что программу, написанную в виде набора сопрограмм, не всегда можно представить в виде многопроходного алгоритма. Если сопрограмма В получает входные данные от А и отправляет обратно ключевую информацию сопрограмме А (как в приведенном выше примере программы игры в шахматы), то последовательность таких действий нельзя преобразовать в проход А, за которым следует проход в.
И наоборот, ясно, что некоторые многопроходные алгоритмы нельзя преобразовать в сопрограммы. Отдельные алгоритмы являются многопроходными по своей сути; например, для второго прохода может требоваться совокупная информация от первого прохода (скажем, общее число появлений некоторого слова во вводе). В этом отношении показательна следующая старая шутка. В авшобусс. Маленькая сгларушка: "Мальчик, ты не подскажешь мие, когда нужно выходить, чтобы попасть на Пасадена-Стрит?".
Мальчик; "Просто следите за мной и выходите за две остановки перед тем, как выйду я"'. (Шутка заключается в том, что мальчик предлагает старуш(се двухпроходный алгоритм.) Вот пока и все, что касается многопроходных алгоритмов, С другими примерами сопрограмм мы будем встречаться в различных разделах книги, например они будут частью буферных схем в разделе 1.4.4. Сопрограммы играют также важную роль в моделировании дискретных систем (см. раздел 2.2.5). Важная идея репликациомных сопрограмм обсуждается в главе 8, а некоторые интересные примеры применения этой идеи можно найти в главе 10.
УПРАЖНЕНИЯ 1. [10) Объясните, почему автору трудно найти небольшие простые примеры сопрограмм. 2. [ЕО) В программе, приведенной в тексте раздела, первой запускается сопрограмма ООТ. Что произойдет, если первой будет выполняться сопрограмма 1М, т. е. если в строке 60 поменять ?ОХР ООТ1" на "ЛХР 1М1"? 3. [20) Истинно ли утверждение "Все три команды "СХР1 РЕХ100" из программы ООТ можно опустить, и программа по-прежнему будет работать"? (Будьте внимательны.) 4.
[ЙО] Покажите, как связь между сопрограммами, аналогичную (1), можно реализовать на реальных компьютерах, которые вы хорошо знаете. 5. [15) Предположим, для обеих сопрограмм 1М и ООТ иужио, чтобы в промежутке между входом и выходом содержимое регистра А оставалось неизменным. Другими словами, предположим, что в каждом случае появления команды ?ОХР 1М" внутри сопрограммы ООТ содержимое регистра А должно оставаться неизменным до возврата управления следующей строке. Аналогичное предположение делается по отношению к команде ?ОХР ООТ" внутри сопрограммы 1М. Как в этом случае должна выглядеть связь между сопрограммами? (Ср.
с (4).) 6. [ЕЕ] Напишите команды связи между сопрограммами, аналогичные (1), для случая трех сопрограмм, А, В и С, каждая из которых может вызывать любую из двух других. (В каждом случае активизации сопрограммы выполнение начинается с того места, где оно закончилось в прошлый раз.) ° 7. [УО] Напишите программу для Х11, которая выполвяст преобразование, обратное тому, которое осуществляет программа из текста раздела, т. е, ваша программа должна получать на входе перфокарты типа (3), а на выходе выдавать перфокарты типа (2).
На выходе должна быть настолько короткая строка символов, насколько это возможно, поэтому нуль перед буквой 2 в (2) на этот раз не должен быть перенесен из (3). 1.4.3. Программы-интерпретаторы В этом разделе будет рассмотрен один из распространенных типов компьютерных программ — программы-инюерпрешаторы (которые для краткости называют просто иншерпретаторами). Интерпретатор — это компьютерная программа, которая выполняет команды другой программы, написанной на некотором машинно- ориентированном языке.
Под машинно-ориентированным языком подразумевается такой способ представления команд, который предполагает использование в командах кодов операций, адресов и т. д. (Это определение, как н большинство определений современных компьютерных терминов, не является точным, да оно и не должно быть таким; нельзя однозначно определить. какие программы являются интерпретаторами, а какие †н.) Исторически первые интерпретаторы являлись оболочками машинно-ориентированных языков, специально предназначенными для упрощения процесса программирования, Такими языками было гораздо легче пользоваться, чем настоящими машинными языками. Возникновение символических языков программирования привело к тому, что отпала необходимость в программах-интерпретаторах такого типа, но это никоим образом не означает, что интерпретаторы начали постепенно исчезать.
Наоборот, их продолжали применять и теперь применяют настолько широко, что эффективное использование программ-интерпретаторов можно считать одной из главных характеристик современного программирования. Новые сферы применения интерпретаторов появились, в основном, по следующим причинам; а) на машинно-ориентированном языке можно представить сложную последовательность решений и действий в компактном и удобном виде; Ь) такое представление обеспечивает прекрасный способ передачи информации между проходами в многопроходном процессе.
В подобных случаях разрабатываются машинно-ориентированные языки специального назначения для использования в конкретной программе и программы, написанные на этих языках, часто генерируются только компьютерами. (Современные квалифицированные программисты являются также хорошими разработчиками машин, поскольку они не только создают программу-интерпретатор, но и определяют виртуальную машину, язык которой необходимо интерпретировать.) Принцип интерпретирования имеет еще одно дополнительное преимущество, которое состоит в относительной независимости от машины, Это означает, что при переходе от одного компьютера к другому необходимо переписать только интерпретатор.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
