Центральный момент в создании программы
Покажите мне свои блок-схемы и спрячьте таблицы, и я ничего не пойму.
Покажите мне таблицы, и блок-схемы мне не понадобятся – все будет очевидно и так.
Фредерик П. Брукс-мл.
Мифический человекомесяц
Согласно приведенной цитате из классической книги Брукса, проектирование структур данных – центральный момент в создании программы. После того как структуры данных определены, алгоритмы, как правило, стремятся сами встать на свое место, и кодирование становится относительно простым делом.
Это, конечно, слишком упрощенный, но тем не менее верный взгляд. В предыдущей главе мы разобрали основные структуры данных; они являются строительными блоками для большинства программ. В этой главе мы скомбинируем рассмотренные структуры, спроектировав и реализовав небольшую программу. Мы покажем, насколько решаемая проблема влияет на структуры данных и насколько очевидным становится написание кода после того, как определены используемые структуры данных.
Одним из аспектов этой точки зрения является то, что выбор конкретного языка программирования оказывается сравнительно неважным для общего проектирования. Мы сначала спроектируем программу абстрактно, а потом реализуем ее на С, Java, C++, Awk и Perl. Сравнив реализации, мы увидим, как тот или иной язык может облегчать или, наоборот, затруднять кодирование и в каких аспектах выбор языка не является важным. Выбранный для реализации язык может, конечно, чем-то украсить программу, но не доминирует в ее разработке.
Проблема, которую мы будем решать, необычна, однако в общем виде она типична для большинства программ: некие данные поступают в программу, некие данные программа выдает на выходе, а обработка данных требует некоторого мастерства.
В данном конкретном случае мы собираемся генерировать случайный английский текст, который был бы читабелен. Если мы будем выдавать просто случайным образом выбранные буквы или слова, получится, естественно, полная чепуха. Программа, случайным образом выбирающая буквы (и пробелы – для разделения "слов"), выдавала бы что-нибудь вроде:
xptmxgn xusaja afqnzgxl Ihidlwcd rjdjuvpydrlwnjy
Что, естественно, не слишком нас устраивает. Если присвоить буквам вес, соответствующий частоте их появления в нормальном тексте, мы получим что-нибудь такое:
idtefoae tcs trder jcii ofdslnqetacp t ola
Что звучит не лучше. Набор слов, выбранных случайным образом из словаря, тоже не будет иметь особого смысла:
polydactyl equatorial splashily jowl verandah circumscribe
Для того чтобы получить более сносный результат, нам нужна статистическая модель с более утонченной структурой. Например, можно рассматривать частоту вхождения целых фраз. Но где нам взять такую статистику?
Мы могли бы взять большой отрывок английского текста и детально изучить его, но есть более простой и более занимательный способ. Главная суть его состоит в том, что мы можем использовать любой кусок текста для построения статистической модели языка, используемого в этом тексте, и генерировать случайный текст, имеющий статистику, схожую с оригиналом.