Иллюстрированный самоучитель по практике программирования

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

• Центральный момент в создании программы

  Покажите мне свои блок-схемы и спрячьте таблицы, и я ничего не пойму. | Покажите мне таблицы, и блок-схемы мне не понадобятся – все будет очевидно и так. | Фредерик П. Брукс-мл. | Мифический человекомесяц | Согласно приведенной цитате из классической книги Брукса, проектирование структур данных – центральный момент в создании программы.

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

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

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

  На какой размер вводимого текста мы должны рассчитывать? Насколько быстро должна работать программа? Представляется логичным, чтобы программа была в состоянии считать целую книгу, так что нам надо быть готовыми к размеру ввода в 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.