Пособие по практике программирования
         

Проектирование и реализация

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

Фредерик П. Брукс-мл. Мифический человекомесяц

Согласно приведенной цитате из классической книги Брукса, проектирование структур данных — центральный момент в создании программы. После того как структуры данных определены, алгоритмы, как правило, стремятся сами встать на свое место, и кодирование становится относительно простым делом.

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

Одним из аспектов этой точки зрения является то, что выбор конкретного


языка программирования оказывается сравнительно неважным для общего проектирования. Мы сначала спроектируем программу абстрактно, а потом реализуем ее на С, Java, C++, Awk и Perl. Сравнив реализации, мы увидим, как тот или иной язык может облегчать или, наоборот, затруднять кодирование и в каких аспектах выбор языка не является важным. Выбранный для реализации язык может, конечно, чем-то украсить программу, но не доминирует в ее разработке.

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

В данном конкретном случае мы собираемся генерировать случайный английский текст, который был бы читабелен. Если мы будем выдавать просто случайным образом выбранные буквы или слова, получится, естественно, полная чепуха. Программа, случайным образом выбирающая буквы (и пробелы — для разделения "слов"), выдавала бы что-нибудь вроде

 xptmxgn xusaja afqnzgxl Ihidlwcd rjdjuvpydrlwnjy

что, естественно, не слишком нас устраивает. Если присвоить буквам вес, соответствующий частоте их появления в нормальном тексте, мы получим что-нибудь такое:

 idtefoae tcs trder jcii ofdslnqetacp t ola

что звучит не лучше. Набор слов, выбранных случайным образом из словаря, тоже не будет иметь особого смысла:

 polydactyl equatorial splashily jowl verandah circumscribe

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

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

Алгоритм цепей Маркова

Элегантный способ выполнить подобную обработку - использовать технику, известную как алгоритм цепей Маркова. Ввод можно представить себе как последовательность перекрывающихся фраз; алгоритм разделяет каждую фразу на две части: префикс, состоящий из нескольких слов, и следующее за ним слово — суффикс (или окончание). Алгоритм цепей Маркова создает выходные фразы, выбирая случайным образом суффикс, следующий за префиксом; все это в соответствии со статистикой текста-оригинала (в нашем случае). Хорошо выглядят фразы из трех слов, когда префикс из двух слов используется для подбора слова-суффикса:

присвоить w, и w2 значения двух первых слов текста
печатать W-, и w2
цикл:
случайным образом выбрать w3 из слов,
следующих за префиксом w, w2 в тексте
печатать w3
заменить да/ и w2 на w2 и w-s
повторить цикл

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

 Show your flowcharts and conceal your tables and I will be mystified.
Show your tables and your flowcharts will be obvious, (end)


Вот несколько пар слов, взятых из этого отрывка, и слова, которые следуют за ними:


Обработка этого текста по предлагаемому алгоритму markov' начинается с того, что будет напечатано Show your, после чего случайным образом будет выбрано или flowcharts, или tables. Если будет выбрано первое слово, то текущим префиксом станет your flowcharts, а следующим словом будет выбра+9но and или will. Если же выбранным окажется tables, то после него последует слово and. Так будет продолжаться до тех пор, пока не будет сгенерирована фраза заданного размера или в качестве суффикса не будет выбрано слово-метка конца ввода (end).

Наша программа прочтет отрывок английского текста и использует алгоритм markov для генерации нового текста, основываясь на частотах вхождения фраз фиксированной длины. Количество слов в префиксе, которое в разобранном примере равно двум, в нашей программе будет параметром. Если префикс укоротить, текст будет менее логичным, если длину префикса увеличить, наше творение будет походить на дословный пересказ вводимого текста. Для английского текста использование двух слов для выбора третьего дает разумный компромисс: сохраняется стиль прототипа и привносится достаточно своеобразия.

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

Исходя из выбранного метода можно сказать, что все слова, фразы из двух слов и фразы из трех слов должны присутствовать во вводимом тексте, но появятся новые фразы из четырех и более слов. Ниже приведены несколько предложений, сгенерированных программой, разработке которой посвящена данная глава, полученных на основе текста седьмой главы книги "И восходит солнце" Эрнеста Хемингуэя:

As I started up the undershirt onto his chest black, and big stomach
muscles bulging under the light. "You see them?" Below the line
where his ribs stopped were two raised whate welts. "See on the forehead.""Oh,
Brett, I love you.""Let's not talk. Talking's all bailge. I'm
going away tomorrow"."Tomorrow?""Yes. Didn't I say
so?I am". " Let's have a drink, them."

Здесь нам повезло - пунктуация оказалась корректной, но этого могло и не случиться.


Варианты структуры данных

На какой размер вводимого текста мы должны рассчитывать? Насколько быстро должна работать программа? Представляется логичным, чтобы программа была в состоянии считать целую книгу, так что нам надо быть готовыми к размеру ввода в п = 100 000 слов и более. Вывод должен составлять сотни, а возможно, и тысячи слов, а работать программа должна несколько секунд, но отнюдь не минут. Имея 100 000 слов вводимого текста, надо признать, что п получается достаточно большим, так что для того, чтобы программа работала действительно быстро, алгоритм придется писать довольно сложный.

Для того чтобы начать генерировать текст, алгоритм markov должен сначала просмотреть весе введенный фрагмент, поэтому исходный текст нам придется каким-то образом сохранять. Первая возможность — ввести полностью исходный текст и сохранить его как длинную строку, но нам явно нужно разбить его на отдельные слова. Если сохранить его как массив указателей на слова, генерация вывода будет происходить просто: для выбора нового слова надо просканировать введенный текст и посмотреть, какие существуют слова-суффиксы для только что введенного префикса, и выбрать из них случайным образом одно. Однако это будет означать сканирование всех 100 000 слов ввода для генерации каждого нового слова; при размере выводимого текста в 1000 слов необходимо осуществить сотни миллионов сравнений строк, а это вовсе не быстро.

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

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

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

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

Что делать, если фраза встречается более одного раза? Например, фраза "может появиться дважды" может появиться дважды, а фраза "может появиться единожды" — только единожды. В таком случае можно поместить слово "дважды" два раза в список суффиксов для префикса "может появиться" или один раз, но при этом установить соответствующий суффиксу счетчик в 2. Мы попробовали и со счетчиками, и без них; без счетчиков проще, поскольку при добавлении суффикса не надо проверять, нет ли его уже в списке. Эксперименты показали, что разница в скорости при обоих способах практически незаметна.

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

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


Создание структуры данных в языке С

Начнем с реализации на С. Для начала надо задать некоторые константы:


В этом описании определяются количество слов в префиксе (NPREF), размер массива хэш-таблицы (NHASH) и верхний предел количества генерируемых слов (MAXGEN). Если NPREF — константа времени компиляции, а не переменная времени исполнения, то управление хранением упрощается. Мы задали очень большой размер массива, поскольку программа должна быть способна воспринимать очень большие документы, возможно, даже целые книги. Мы выбрали NHASH = 4093, так что если во введенном . тексте имеется 10 000 различных префиксов (то есть пар слов), то среднестатистическая цепочка будет весьма короткой — два или три префикса. Чем больше размер, тем короче будет ожидаемая длина цепи и, следовательно, тем быстрее будет осуществляться поиск. Эта программа создается для развлечения, поэтому производительность ее не критична, однако если мы сделаем слишком маленький массив, то программа не сможет обработать текст ожидаемого размера за разумное время; если же сделать его слишком большим,'он может не уложиться в имеющуюся память.

Префикс можно хранить как массив слов. Элементы хэш-таблицы будут представлены как тип данных State, ассоциирующий список Suffix с префиксом:


Графически структура данных выглядит так:


Нам потребуется хэш-функция для префиксов, которые являются массивами строк. Нетрудно преобразовать хэш-функцию из главы 2, сделав цикл по строкам в массиве, таким образом хэшируя конкатенацию этих строк:



Выполнив схожим образом модификацию алгоритма lookup, мы завершим реализацию хэш-таблицы:



Обратите внимание на то, что lookup не создает копии входящей строки при создании нового состояния, просто в sp->pref [ ] 'сохраняются указатели. Те, кто использует вызов lookup, должны гарантировать, что впоследствии данные изменены не будут. Например, если строки находятся в буфере ввода-вывода, то перед тем, как вызвать lookup, надо сделать их копию; в противном случае следующие куски вводимого текста могут перезаписать данные, на которые ссылается хэш-таблица. Необходимость решать, кто же владеет совместно используемыми ресурсами, возникает достаточно часто. Эту тему мы подробно рассмотрим в следующей главе.

Теперь нам надо прочитать файл и создать хэш-таблицу:


Необычный вызов sprintf связан с досадной проблемой, присущей f scant, — если бы не эта проблема, функция f scanf идеально подошла бы для нашего случая. Все дело в том, что вызов fscanf с форматом %s считывает следующее ограниченное пробелами слово из файла в буфер, но без проверки его длины: слишком длинное слово может переполнить входной буфер, что приведет к разрушительным последствиям. Если буфер имеет размер 100 байтов (что гораздо больше того, что ожидаешь встретить в нормальном тексте), мы можем использовать формат %99s (оставляя один байт на заключительный ' \0'), что будет означать для fscanf приказ остановиться после 99 байт. Тогда длинное слово окажется разбитым на части, что некстати, но вполне безопасно. Мы могли бы написать 

? enum { BUFSIZE = 100 };
? char fmtrj = "%99s"; /1 BUFSIZE-1 ./

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

Аргументы build — массив prefix, содержащий предыдущие NPREF введенных слов и указатель FILE. Массив prefix и копия введенного слова передаются в add, которая добавляет новый элемент в хэш-таблицу и обновляет префикс:


Вызов memmove — идиоматический способ удаления из массива. В префиксе элементы с 1 по NPREF-1 сдвигаются вниз на позиции с 0 по NPREF-2, удаляя первое слово и освобождая место для нового слова в конце.
Функция addsuf fix добавляет новый суффикс:



Мы разделили процесс обновления состояния на две функции — add просто добавляет суффикс к префиксу, тогда как addsuffix выполняет тесно связанное с реализацией действие — добавляет слово в список суффиксов. Функция add вызывается из build, но addsuffix используется только изнутри add — это та часть кода, которая может быть впоследствии изменена, поэтому лучше выделить ее в отдельную функцию, даже если вызываться она будет лишь из одного места.


Генерация вывода

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

build(prefix, stdin); 
add(prefix, NONWORD);

В этом фрагменте NONWORD — некоторое значение, которое точно никогда не встретится в тексте. Поскольку по нашему определению слова разделяются пробелами, на роль завершителя подойдет "слово", равносильное пробелу, но отличное от него, например символ перевода строки:

char NONWORD[] = "\n"; /* никогда не встретится */

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

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

На случай, если генерируемый текст окажется непредсказуемо большого размера, можно встроить ограничитель — прерывать алгоритм после вывода заданного количества слов или при появлении NONWORD в качестве суффикса.

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

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

Функция generate использует алгоритм, который мы только что описали в общих словах. Она генерирует текст по слову в строке; эти слова можно группировать в более длинные строки при помощи любого текстового редактора — в главе 9 будет показано простое средство для такого форматирования — процедура f mt.

Благодаря использованию в начале и в конце строк NONWORD, generate начинает и заканчивает работу без проблем:


Обратите внимание на алгоритм случайного выбора элемента, когда число всех элементов нам неизвестно. В переменной nmatch подсчитывается количество совпадений при сканировании списка. Выражение

 rand()
 ++nmatch == 0

увеличивает nmatch и является истинным с вероятностью 1/nmatch. Таким образом, первый подходящий элемент будет выбран с вероятностью 1, второй заменит его с вероятностью 1/2, третий заменит выбранный из предыдущих с вероятностью 1/3 и т. п. В каждый момент времени каждый из k просмотренных элементов будет выбран с вероятностью i/k.

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

Если выбранный суффикс оказывается NONWORD, то все заканчивается, поскольку это означает, что мы достигли состояния, относящегося к концу введенного текста. Если суффикс не NONWORD, то мы его печатаем, а далее с помощью вызова memmove удаляем первое слово из префикса и делаем суффикс вторым словом нового префикса, после чего цикл повторяется.

Теперь все написанное можно свести воедино в функцию main, которая читает стандартный ввод и генерирует не более заданного количества слов:


На этом разработка программы на С завершена. В конце главы мы сравним программы, написанные на разных языках. Главные достоинства С состоят в том, что он предоставляет программисту возможность полного управления реализацией и что программы, написанные на С, работают, как правило, весьма быстро. Расплачиваться за это приходится тем, что программист вынужден выполнять большую работ}»;: он сам должен выделять и освобождать память, создавать хэш-таблицы\1 связные списки и т. п. С — инструмент с остротой бритвы: с его помощью можно создать и элегантную программу, и кровавое месиво.

Упражнение 3-1

Алгоритм случайного выбора элемента из списка неизвестной длины зависит от качества генератора случайных чисел. Спроектируйте и осуществите эксперименты для проверки метода на практике.

Упражнение 3-2

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

Упражнение 3-3

Удалите выражения, которые помещают сигнальные метки NONWORD в начало и конец данных, и измените generate так, чтобы она нормально запускалась и останавливалась без их использования. Убедитесь, что вывод корректен для О, 1, 2, 3 и 4 слов. Сравните код с использованием сигнальных меток и код без них.


Java

Вторую реализацию алгоритма markov мы создадим на языке Java. Объектно-ориентированные языки вроде Java заставляют нас обращать особое внимание на взаимодействие между компонентами программы. Эти компоненты инкапсулируются в независимые элементы данных, называемые объектами или классами; с ними ассоциированы функции, называемые методами.

Java имеет более богатую библиотеку, чем С. В частности, эта библиотека включает в себя набор классов-контейнеров (container classes) для группировки существующих объектов различными способами. В качестве примера можно привести класс Vector, который представляет собой динамически растущий массив, где могут храниться любые объекты типа Object. Другой пример— класс Hashtable, с помощью которого можно сохранять и получать значения одного типа, используя объекты другого типа в качестве ключей.

В нашем приложении экземпляры класса Vector со строками в качестве объектов — самый естественный способ хранения префиксов и суффиксов. Так же естественно использовать и класс Hashtable, ключами в котором будут векторы префиксов, а значениями — векторы суффиксов. Конструкции подобного рода называются отображениями (тар) префиксов на суффиксы; в Java нам не потребуется в явном виде задавать тип State, поскольку Hashtable неявным образом сопоставляет префиксы и суффиксы. Этот дизайн отличается от версии С, где мы создавали структуры State, в которых соединялись префиксы и списки суффиксов, а для получения структуры State использовали хэширование префикса.

Hashtable предоставляет в наше распоряжение метод put для хранения пар ключ-значение и метод get для получения значения по заданному ключу:


В нашей реализации будут три класса. Первый класс, Prefix, содер,-жит слова префиксов:


Второй класс, Chain, считывает ввод, строит хэш-таблицу и генерирует вывод; переменные класса выглядят так:



Третий класс — общедоступный интерфейс; в нем содержится функция main и происходит начальная инициализация класса Chain:


После того как создан экземпляр класса Chain, он в свою очередь создает хэш-таблицу и устанавливает начальное значение префикса, состоящее из NPREF -констант NONWORD. Функция build использует библиотечную функцию StreamTokenizer для разбора вводимого текста на слова, разделенные пробелами. Первые три вызова перед основным циклом устанавливают значения этой функции, соответствующие нашему определению термина "слово":

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


Обратите внимание на то, что если suf равен null, то add добавляет в хэш-таблицу префикс как новый объект класса Pref ix, а не собственно pref ix. Это сделано потому, что класс Hashtable хранит объекты по ссылкам, и если мы не сделаем копию, то можем перезаписать данные в таблице. Собственно говоря, с этой проблемой мы уже встречались при написании программы на С.

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



Два конструктора Prefix создают новые экземпляры класса в зависимости от передаваемых параметров. В первом случае копируется существующее значение типа Prefix, а во втором префикс создается из п копий строки; этот конструктор используется для создания NPREF копий NONWORD при инициализации префикса:


Класс P refix имеет также два метода, hashCode и equals, которые неявно вызываются из Hashtable для индексации и поиска по табллце. Нам пришлось сделать Prefix полноценным классом как раз из-за этих двух методов, которых требует Hashtable, иначе для него можно было бы использовать Vector, как мы сделали с суффиксом.

Метод hashCode создает отдельно взятое хэш-значение, комбинируя набор значений hashCode для элементов вектора:



Метод equals осуществляет поэлементное сравнение слов в двух npeфиксах:

Программа на Java гораздо меньше, чем ее аналог на С, при этом больше деталей проработано в самом языке — очевидными примерами являются классы Vector и Hashtable. В общем и целом управление хранением данных получилось более простым, поскольку вектора растут, когда' нужно, а сборщик мусора (garbage collector — специальный автоматический механизм виртуальной машины Java) сам заботится об освобождении неиспользуемой памяти. Однако для того, чтобы использовать класс Hashtable, нам пришлось-таки самим писать функции hashCode и equals, так что нельзя сказать, что язык Java заботился бы обо всех деталях.

Сравнивая способы, которыми программы на С и Java представляют < и обрабатывают одни и те же структуры данных, следует отметить, что в версии на Java лучше разделены функциональные обязанности. При таком подходе нам, например, не составит большого труда перейти от использования класса Vector к использованию массивов. В версии С каждый блок связан с другими блоками: хэш-таблица работает с массивами, которые обрабатываются в различных местах; функция lookup четко ориентирована на конкретное представление структур State и Suffix; размер массива префиксов вообще употребляется практически всюду.

Пропустив эту программу с исходным (химическим) текстом и форматируя сгенерированный текст с помощью процедуры f mt, мы получили следующее:

 % Java Markov <j r^cheinistry. txt | fmt Wash the blackboard. 
Watch it dry. The water goes into the air. When water goes
 into the air it evaporates. Tie a damp clotTf to one end of a 
solid or liquid. Look around. What are the solid things? 
Chemical changes take place when something burns. If
the burning material has .liquids, they are stable and the sponge rise.
It looked like dough, but it is burning. Break up the lump of sugar into
small pieces and put them together again in the bottom of a liquid.


Упражнение 3-4

Перепишите Java-версию markov так, чтобы использовать массив вместо класса Vector для префикса в классе Prefix.


C++

Третий вариант программы мы напишем на C++. Поскольку C+ + является почти что расширением С, на нем можно писать как на С (с некоторыми новыми удобствами в обозначениях), а наша изначальная С-версия будет вполне нормальной программой и для C++. Однако при использовании C++ было бы более естественно определить классы для объектов программы — что-то вроде того, что мы сделали на Java — это позволит скрыть некоторые детали реализации. Мы решили пойти даже дальше и использовать библиотеку стандартных шаблонов STL (Standard Template Library), поскольку в ней есть некоторые встроенные механизмы, которые могут выполнить значительную часть необходимой работы. ISO-стандарт C++ включает в себя STL как часть описания языка.

STL предоставляет такие контейнеры, как векторы, списки и множества, а также ряд основных алгоритмов для поиска, сортировки, добавления и удаления элементов данных. Благодаря использованию шаблонов C++ каждый алгоритм STL работает со всевозможными видами контейнеров, включая как типы, описанные пользователем, так и встроенные типы данных. Контейнеры реализованы как шаблоны C++, которые инстанцируются для конкретных типов данных; например, контейнер vector может использоваться для создания конкретных типов vector<int> или vector<string>. Все операции, описанные в библиотеке для vector, включая стандартные алгоритмы сортировки, можно использовать для таких "производных" типов данных.

В дополнение к контейнеру vector, который схож с Vector в Java, STL предоставляет контейнер deque (дек, гибрид очереди и стека). Дек — это двусторонняя очередь, которая как раз подходит нам для работы с пре-_ фиксами: в ней содержится NPREF элементов, и мы можем выкидывать первый элемент и добавлять в конец новый, обе операции — за время О(1). Дек STL — более общая структура, чем требуется нам, поскольку она позволяет выкидывать и добавлять элементы с обоих концов, но характеристики производительности указывают на то, что нам следует использовать именно ее.

В STL существует также в явном виде и основанный на сбалансированных деревьях контейнер тар, который хранит пары ключ-значение и осуществляет поиск значения, ассоциированного с любым ключом, за 0(log n). Отображения, возможно, не столь эффективны, как О(1) кэш-таблицы, но приятно то, что для их использования не надо писать вообще никакого кода. (Некоторые библиотеки, не входящие в стандарт C++, содержат контейнеры hash или hash_map — они бы подошли просто идеально.)

Кроме всего прочего, мы будем использовать и встроенные функции сравнения, в данном случае они будут сравнивать строки, используя отдельные строки префикса (в которых мы храним отдельные слова!).

Имея в своем распоряжении все перечисленные компоненты, мы пишем код совсем гладко. Вот как выглядят объявления:

 typedef deque<string> Prefix;
map<Prefix, vector<string> > statetab;// prefix-> suffixes

Как мы уже говорили, STL предоставляет шаблон дека; запись deque<string> обозначает дек, элементами которого являются строки. Поскольку этот тип встретится в программе несколько раз, мы использовали typedef для присвоения ему осмысленного имени Prefix. А вот тип тар, хранящий префиксы и суффиксы, появится лишь единожды, так что мы не стали давать ему уникального имени; объявление тар описывает переменную statetab, которая является отображением префиксов на векторы строк. Это более удобно, чем в С или Java, поскольку нам не потребуется писать хэш-функцию или метод equals.

В основном блоке инициализируется префикс, считывается вводимый текст (из стандартного потока ввода, который в библиотеке C++ lost ream называется cin), добавляется метка конца ввода и генерируется выходной текст — совсем как в предыдущих версиях:




Функция build использует библиотеку lost ream для ввода слов по одному:


Строка buf будет расти по мере надобности, чтобы в ней помещались вводимые слова произвольной длины.

В функции add более явно видны преимущества использования STL:


Как вы видите, выражения выглядят совсем не сложно; происходящее "за кулисами" тоже вполне доступно пониманию простого смертного. Контейнер тар переопределяет доступ по индексу (операцию[ ]) для того, чтобы он работал как операция поиска. Выражение statetab[prefix] осуществляет поиск в statetab по ключу prefix и возвращает ссылку на искомое значение; если вектора еще не существует, то создается новый. Функция push_back — такая функция-член класса имеется и в vector, и в deque — добавляет новую строку в конец вектора или дека; pop^f ront удаляет ("выталкивает") первый элемент из дека.

Генерация результирующего текста осуществляется практически так же, как и в предыдущих версиях:



Итак, в результате именно эта версия выглядит наиболее понятно и элегантно — код компактен, структура данных ясно видна, а алгоритм абсолютно прозрачен. Но, как и за все хорошее в жизни, за это надо платить — данная версия работает гораздо медленнее, чем версия, написанная на С; правда, это все же не самый медленный вариант. Вопросы измерения производительности мы вскоре обсудим.

Упражнение 3-5

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

Упражнение 3-6

Перепишите программу на C++ так, чтобы в ней использовались только классы и тип данных string — без каких-либо дополнительных библиотечных средств. Сравните то, что у вас получится, по стилю кода и скорости работы с нашей STL-версией.


AWK и PERL

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

Ассоциативный массив (associative array) — это подходящий контейнер для кэш-таблицы; он выглядит как простой массив, но его индексами являются произвольные строки, или числа, или наборы таких элементов, разделенных запятыми. Это разновидность отображения данных одного типа в данные другого типа. В Awk все массивы являются ассоциативными; в Perl есть как массивы, индексируемые стандартным образом, целочисленными индексами, так и ассоциативные массивы, которые называются "хэшами" (hashes), — из их названия сразу становится ясен способ их внутренней реализации.

Предлагаемые версии на Awk и Perl рассчитаны только на работу с префиксами длиной в два слова.




Awk — язык, функционирующий по принципу "образец-действие": входной поток читается по строке за раз, каждая строка сравнивается с образцом, для каждого совпадения выполняется соответствующее дей-Ствие. Существуют два специальных образца-— BEGIN и END, которые вызываются, соответственно, перед первой строкой ввода и после последней.

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

Следующий блок не имеет образца, поэтому он по умолчанию вызывается для каждой новой строки ввода. Awk автоматически разделяет каждую вводимую строку на поля (ограниченные пробелами слова), имеющие имена от $1 до $NF; переменная NF — это количество полей. Выражение

Statetab[w1,w2,++nsuffix[w1,w2]] = $i

создает отображение префиксов в суффиксы. Массив nsuffix считает суффиксы, а элемент nsuf f ix[w1, w2] считает количество суффиксов, ассоциированных с префиксом. Сами суффиксы хранятся в элементах массива statetab[w1,w2, 1], statetab[w1, w2, 2] и т. д.

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

Версия Perl выглядит похожим образом, но в ней для хранения суффиксов используется безымянный массив, а не третий индекс; для обновления же префикса используется множественное присваивание. В Perl для обозначения типов переменных применяются специальные символы: $ обозначает скаляр, @ — индексированный массив, квадратные скобки [ ] используются для индексации массивов, а фигурные скобки { } — для индексации хэшей.

Как и в предыдущей программе, отображение хранится при помощи переменной statetab. Центральным моментом программы является выражение

 push(@{$statetab{$w1}{$w2}}, $_);

которое дописывает новый суффикс в конец (безымянного) массива, хранящегося в statetab{$w1}{$w2). На этапе генерации $statetab{$w1}{$w2} является ссылкой на массив суффиксов, a$suf->[$r] указывает на суффикс, хранящийся под номером r.

Программы и на Awk, и на Perl гораздо короче, чем любая из трех предыдущих версий, но их тяжелее адаптировать для обработки префиксов, состоящих из произвольного количества слов. Ядро программ на С и C++ (функции add и generate) имеет сравнимую длину, но выглядит более понятно. Тем не менее языки скриптов нередко являются хорошим выбором для экспериментального программирования, для создания прототипов и даже для производственного использования в случаях, когда время счета не играет большой роли.

Упражнение 3-7

Попробуйте преобразовать приложения на Awk и Perl так, чтобы они могли обрабатывать префиксы произвольной длины. Попробуйте определить, как это скажется на быстродействии программ.


Производительность

Теперь можно сравнить несколько вариантов программы. Мы засекали время счета на библейской Книге Псалмов (версия перевода King James Bible), в которой содержится 42 685 слов (5238 уникальных слов, 22 482 префикса). В тексте довольно много повторяющихся фраз ("Blessed is the..."), так что есть списки суффиксов, имеющие более 400 элементов, и несколько сотен цепей с десятками суффиксов, и это хороший набор данных для теста.

Blessed is the man of the net. Turn thee unto me, and raise me up, that
I may tell all my fears. They looked unto him, he heard. My praise shall
be blessed. Wealth and riches shall be saved. Thou hast dealt well with
thy hid treasure: they are cast into a standing water, the flint into
a standing water, and dry ground into watersprings.

Приведенная таблица показывает время в секундах, затрачиваемое на j генерацию 10 000 слов; тестирование проводилось на машине 250 MHz MIPS R10000 с операционной системой Irix 6.4 и на машине Pentium II 400 MHz со 128 мегабайтами памяти под Windows NT. Время выполнeния почти целиком определяется объемом вводимого текста; генерация происходит несравненно быстрее. В таблице приведен также примерный размер программы в строках исходного кода.

  250 MHz RlOOOO(c) 400 MHz Pentium II (c) Строки исходного кода
С 0.36 0.30 150
Java 4.9 9.2 105
C++/STL/deque 2.6 11.2 70
C++/STL/list 1.7 1.5 70
Awk 2.2 2.1 20
Perl 1.8 1.0 18

Версии С и C++ компилировались с включенной оптимизацией, а программы Java запускались с включенным JIT-компилятором (Just-In-Time, "своевременная" компиляция). Время, указанное для версий С и C++ под Irix, — лучшее врейя из трех возможных компиляторов; сходные результаты были получены и для машин Sun SPARC и DEC Alpha.

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

Что-то явно не так с версией STL/deque под Windows. Эксперименты показали, что дек, представляющий префиксы, поедает практически все время выполнения, хотя в нем никогда не содержится более двух элементов; казалось бы, большая часть времени должна уходить на основную структуру — отображение. Переход с дека на список (в STL это двухсвязный список) кардинальным образом улучшает время. Переход же с отображения (тар) на (нестандартный) контейнер hash под Irix не приносит никаких изменений (на машине с Windows у нас не было реализации hash). В пользу замечательного принципа проектирования библиотеки STL говорит тот факт, что для внесения этих изменений нам было достаточно заменить слово list на слово deque, а слово hash на слово тар в двух местах и скомпилировать программу заново. Мы пришли к выводу, что STL, которая является новым компонентом C++, все еще страдает некоторыми недоделками в реализации части своих элементов. Производительность при выборе различных версий STL или изменении используемых структур данных меняется непредсказуемым образом. То же самое можно отнести и к Java, где реализации также быстро меняются.

В тестировании программы, которая выдает в качестве результата что-то объемное, да к тому же выбранное случайным образом, есть доля творческого вызова. Как узнать, правильно ли программа работает? Всегд; ли она работает правильно? В главе 6, посвященной тестированию, м: дадим ряд советов на этот счет и расскажем, как мы тестировали наш; программу.

Программа markov имеет длинную историю.

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

Дополнительная литература

Библиотека стандартных шаблонов описана во множестве книг, включая "Генерацию программ и STL" Мэтью Остерна (Matthew Austern. Generic Programming and the STL. Addison-Wesley, 1998).

Для изучения самого языка C++ лучшим пособием является "Язык программирования C++" Бьёрна Страуструпа (Bjarne Stroustrup. The C++ Programming Language. 3rd ed. Addison-Wesley, 1997)2, для изучения Java — "Язык программирования Java" Кена Арнольда и Джеймса Гос-линга (Ken Arnold and James Gosling. The Java Programming Language. 2mt ed. Addison-Wesley, 1998). Лучшее, на наш взгляд, описание Perl при- • ведено в "Программировании на Perl" Ларри Уолла, Тома Кристиансена и Рэндала Шварца (Larry Wall, Tom Christiansen and Randal Schwartz. Programming Perl. 2nd ed. O'Reilly, 1996).

В принципе, можно говорить о существовании неких шаблонов проектирования (design patterns) — действительно, в большинстве программ используется лишь ограниченное количество принципиальных проектировочных решений — точно так же, как существует лишь несколько базовых структур данных; с некоторой натяжкой можно сказать, что это аналог идиоматического кода, о котором мы говорили в первой главе. Эта идея лежит в основе книги Эриха Гаммы, Ричарда Хелма, Ральфа Джонсона и Джона Влиссайдеса "Разработка шаблонов: элементы по-вторноиспользуемого объектно-ориентированного программного обеспечения" (Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995).

Авантюрные приключения программы markov (которая изначально называлась shaney) были описаны в разделе "Computing Recreations" журнала Scientific American за ию^ь 1989 года. Статья была перепечатана в книге Дьюдни "Магическая машина" (А. К. Dewdney. The Magic Machine. W. H. Freeman, 1990).