ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->1.6. Практика программирования

Алгоритмы структуры данных

1.6. Практика программирования

 

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

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

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

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

4.    Станьте "кузнецом" инструментов. На языке программистов инструмент (tool) — это программа с широким спектром применения. При создании программы подумайте, нельзя ли ее каким-либо образом обобщить, т.е. сделать более универсальной (конечно, с минимальными программистскими усилиями). Например, предположим, что вам необходимо написать программу, составляющую расписание экзаменов. Вместо заказанной программы можно написать программу-инструмент, раскрашивающий вершины обычного графа (по возможности минимальным количеством цветов) таким образом, чтобы любые две вершины, соединенные ребром, были закрашены в разные цвета. В контексте расписания экзаменов вершины графа — это классы, цвета — время проведения экзаменов, а ребра, соединяющие две вершины-класса, обозначают, что в этих классах экзамены принимает одна и та же экзаменационная комиссия. Такая программа раскраски графа вместе с подпрограммой перевода списка классов в множество вершин графа и цветов в заданные временные интервалы проведения экзаменов составит расписание экзаменов. Программу раскраски можно использовать для решения задач, совсем не связанных с составлением расписаний, например для задания режимов работы светофоров на сложном перекрестке, как было показано в разделе 1.1.

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

 

 Пример 1.11. В качестве примера рассмотрим программу spell, написанную Джонсоном (S.G. Johnson) с использованием команд UNIX . На вход этой программы поступает файл f1 состоящий из текста на английском языке, на выходе получаем все слова из f1, не совпадающие со словами из небольшого словаря. Эта программа воспринимает имена и правильно написанные слова, которых нет в словаре, как орфографические ошибки. Но обычно выходной список ошибок достаточно короткий, поэтому его можно быстро пробежать глазами и определить, какие слова в нем не являются ошибками.

Первый фильтр, используемый программой spell, — это команда translate, которая имеет соответствующие параметры и заменяет прописные буквы на строчные, пробелы — на начало новых строк, а остальные символы оставляет без изменений. На выходе этой команды мы получаем файл f2, состоящий из тех же слов, что и файл f1, но каждое слово расположено в отдельной строке. Далее выполняется команда sort, упорядочивающая строки входного файла в алфавитном порядке. Результатом выполнения этой команды является файл f3, содержащий отсортированный список (возможно, с повторениями) слов из файла f2. Затем командa unique удаляет повторяющиеся строки в своем входном файле f3, создавая выходной файл f4, содержащий слова из исходного файла (без прописных букв и повторений), упорядоченные в алфавитном порядке. Наконец, к файлу f4 применяется команда diff, имеющая параметр, который указывает на файл f5, содержащий в алфавитном порядке слова из словаря, расположенные по одному в строке. Результатом этой команды будет список слов из файла f4, которые не совпадают со словами из файла f5, т.е. те слова из исходного списка, которых нет в словаре. Программа spell состоит из следующей последовательности команд: .

spell:       translate  [A-Z]   →  [a-z],   пробел → новая строка

 sort

 unique

 diff словарь

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

 

 

15