Проектирование и реализация
Центральный момент в создании программы
Покажите мне свои блок-схемы и спрячьте таблицы, и я ничего не пойму. | Покажите мне таблицы, и блок-схемы мне не понадобятся – все будет очевидно и так. | Фредерик П. Брукс-мл. | Мифический человекомесяц | Согласно приведенной цитате из классической книги Брукса, проектирование структур данных – центральный момент в создании программы.Алгоритм цепей Маркова
Элегантный способ выполнить подобную обработку – использовать технику, известную как алгоритм цепей Маркова. Ввод можно представить себе как последовательность перекрывающихся фраз; алгоритм разделяет каждую фразу на две части: префикс, состоящий из нескольких слов, и следующее за ним слово – суффикс (или окончание).Варианты структуры данных
На какой размер вводимого текста мы должны рассчитывать? Насколько быстро должна работать программа? Представляется логичным, чтобы программа была в состоянии считать целую книгу, так что нам надо быть готовыми к размеру ввода в n = 100 000 слов и более.Создание структуры данных в языке С
Начнем с реализации на С. Для начала надо задать некоторые константы: | В этом описании определяются количество слов в префиксе (NPREF), размер массива хэш-таблицы (NHASH) и верхний предел количества генерируемых слов (MAXGEN).Генерация вывода
Теперь, когда структура данных построена, пора переходить к следующему шагу – генерации нового текста. Основная идея остается неизменной: у нас есть префикс, мы случайным образом выбираем один из возможных для него суффиксов, печатаем его, затем обновляем префикс. Это повторяющаяся часть обработки;Объектно-ориентированный язык Java
Вторую реализацию алгоритма markov мы создадим на языке Java. Объектно-ориентированные языки вроде Java заставляют нас обращать особое внимание на взаимодействие между компонентами программы. Эти компоненты инкапсулируются в независимые элементы данных, называемые объектами или классами;C++
Третий вариант программы мы напишем на C++. Поскольку C+ + является почти что расширением С, на нем можно писать как на С (с некоторыми новыми удобствами в обозначениях), а наша изначальная С-версия будет вполне нормальной программой и для C++.Языки скриптов AWK и PERL
Чтобы завершить наши упражнения, мы написали программу еще и на двух популярных языках скриптов – Awk и Perl. В них есть возможности, необходимые для нашего приложения, – ассоциативные массивы и методы обработки строк.Производительность
Теперь можно сравнить несколько вариантов программы. Мы засекали время счета на библейской Книге Псалмов (версия перевода King James Bible), в которой содержится 42 685 слов (5238 уникальных слов, 22 482 префикса).Уроки
Программа markov имеет длинную историю. Первая версия была написана Доном Митчелом, адаптирована Брюсом Эллисом и применялась для разнообразной забавной деконструктивистской деятельности на протяжении 1980-х годов.Дополнительная литература
Библиотека стандартных шаблонов описана во множестве книг, включая "Генерацию программ и STL" Мэтью Остерна (Matthew Austern. Generic Programming and the STL. Addison-Wesley, 1998). | Для изучения самого языка C++ лучшим пособием является "Язык программирования C++" Бьерна Страуструпа (Bjarne Stroustrup. The C++ Programming Language. 3rd ed.