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