Уроки
Программа markov имеет длинную историю. Первая версия была написана Доном Митчелом, адаптирована Брюсом Эллисом и применялась для разнообразной забавной деконструктивистской деятельности на протяжении 1980-х годов. Она не имела никакого развития до тех пор, пока мы не решили использовать ее для иллюстрации университетского курса по проектированию программ. Однако и мы, вместо того чтобы сдуть пыль с оригинала, заново переписали ее на С, чтобы живее прочувствовать связанные с ней проблемы. После этого мы написали ее на ряде других языков, в каждом случае используя присущие тому или иному языку идиомы для выражения одной и той же основной идеи. После прочтения курса мы не раз еще переписывали программу, добиваясь предельной ясности и идеального вида.
Однако на протяжении всего этого времени основа проекта оставалась неизменной. Самые первые версии использовали такой же подход, что и версии, представленные здесь, разве что появилась вторая хэш-таблица для хранения отдельных слов. Если бы нам сейчас пришлось переписать все еще раз, мы бы вряд ли многое изменили. Архитектура программы коренится в принципиальной структуре данных. Структуры данных, конечно, не определяют каждую деталь, но формируют общее решение.
Переходы между некоторыми структурами данных вносят совсем немного различий, например переход от списков к расширяемым массивам. Некоторые реализации решают проблему в менее общем виде, например код на Awk или Perl может быть запросто изменен для обработки префиксов из одного или трех слов, но попытка реализации параметрического выбора размера префикса будет просто ужасна. Большое преимущество программ на объектно-ориентированных языках вроде C++ или Java состоит в том, что, внеся в них совсем незначительные изменения, можно создать структуры данных, подходящие для новых объектов: вместо английского текста можно использовать, например, программы (где пробелы будут уже значимыми символами), или музыкальные ноты, или даже щелчки мыши и выборы пунктов меню для генерации тестовых последовательностей.
Конечно, несмотря на то что структуры данных различаются слабо, программы на разных языках достаточно сильно отличаются друг от друга по размеру исходного кода и быстродействию. Грубо говоря, программы, написанные на языках высокого уровня, будут более медленными, чем программы на языках низкого уровня, хотя оценку можно дать только качественную, но не количественную. Использование больших строительных блоков, таких как STL в C++ или ассоциативные массивы и обработка строк в скриптовых языках, приводит к более компактному коду и серьезно сокращает время на создание приложения. Как мы уже отмечали, за удобство приходится платить, хотя проблемы с быстродействием не имеют большого значения для программ типа рассмотренной, поскольку выполняется она всего несколько секунд.
Менее понятно, однако, как оценить ослабление контроля над программой и понимания происходящего со стороны программиста, когда размер "заимствованного" кода становится настолько большим, что отследить все нюансы становится невозможно. STL-версия – это как раз тот самый случай: ее производительность непредсказуема, и нет простых способов как-то с этим разобраться. Немногие из нас обладают достаточным запасом сил и энергии, чтобы разыскать источник трудностей и исправить ошибки.
Это всеобщая и все растущая проблема программного обеспечения – по мере того как библиотеки, интерфейсы и инструменты все более усложняются, они становятся все менее понятными и менее управляемыми. Когда все работает, среда программирования, имеющая много вспомогательных средств, может быть весьма продуктивна, но когда эти средства отказывают, трудно найти спасение. Действительно, если проблемы связаны с быстродействием или с трудноуловимыми логическими ошибками, то мы можем даже не понять, что что-то идет не так, как надо.
Проектирование и реализация этой программы дали нам несколько уроков, которые стоит усвоить перед тем, как браться за большие программы. Первый – это важность выбора простых алгоритмов и структур данных: самых простых из всех, что смогут выполнить задачу, уложившись во все ограничения (по времени, размеру и т. п.). Если кто-то уже описал эти структуры или алгоритмы и создал библиотеку, то нам это только на руку; наша C++ версия выигрывала как раз за счет этого.
Следуя совету Брукса, мы считаем, что лучше всего начинать детальное проектирование со структур данных, руководствуясь знаниями о том, какие алгоритмы могут быть использованы; после того как структуры данных определены, код проектируется и пишется гораздо проще.
Трудно сначала спроектировать программу целиком, а потом уже писать; создание реальных программ всегда включает в себя повторения и эксперименты. Процесс непосредственного написания программы вынуждает программиста уточнять решения, которые до этого существовали лишь в общем виде. Для нашей программы это весьма актуально – она претерпела множество изменений в деталях. Изо всех сил старайтесь начинать с чего-нибудь простого, внося улучшения, диктуемые опытом. Если бы нашей целью было просто реализовать алгоритм цепей Маркова для развлечения – тексты бывают довольно забавными, – мы практически наверняка написали бы его на Awk или Perl, причем даже не позаботившись навести глянец, который мы вам продемонстрировали, – и на этом успокоились бы.
Однако код для настоящего промышленного приложения требует гораздо больших затрат, чем код прототипа. Если к представленным здесь программам относиться как к промышленной реализации (поскольку они были отлажены и тщательно оттестированы), то усилия на создание промышленной версии будут на один-два порядка больше, чем при написании программы для собственного использования.
Упражнение 3.8
Мы видели множество версий этой программы, написанных на различных языках программирования, включая Scheme, Tel, Prolog, Python, Generic Java, ML и Haskell; у каждой есть свои преимущества и свои недостатки. Реализуйте программу на своем любимом языке и оцените ее быстродействие и размеры кода.