Генерация вывода
Обратите внимание на алгоритм случайного выбора элемента, когда число всех элементов нам неизвестно. В переменной nmatch подсчитывается количество совпадений при сканировании списка. Выражение Увеличивает nmatch и является истинным с вероятностью 1/nmatch:
rand() ++nmatch == 0
Таким образом, первый подходящий элемент будет выбран с вероятностью 1, второй заменит его с вероятностью 1/2, третий заменит выбранный из предыдущих с вероятностью 1/3 и т. п. В каждый момент времени каждый из k просмотренных элементов будет выбран с вероятностью i/k.
Вначале мы устанавливаем prefix в стартовое значение, которое с гарантией присутствует в хэш-таблице. Первые найденные значения Suffix будут первыми словами документа, поскольку только они следуют за стартовым префиксом. После этого суффикс выбирается случайным образом. В цикле вызывается lookup для поиска в хэш-таблице элемента (множества суффиксов), соответствующего данному префиксу; после этого случайным образом выбирается один из суффиксов, он печатается, а префикс обновляется.
Если выбранный суффикс оказывается NONWORD, то все заканчивается, поскольку это означает, что мы достигли состояния, относящегося к концу введенного текста. Если суффикс не NONWORD, то мы его печатаем, а далее с помощью вызова memmove удаляем первое слово из префикса и делаем суффикс вторым словом нового префикса, после чего цикл повторяется.
Теперь все написанное можно свести воедино в функцию main, которая читает стандартный ввод и генерирует не более заданного количества слов:
На этом разработка программы на С завершена.
В конце главы мы сравним программы, написанные на разных языках. Главные достоинства С состоят в том, что он предоставляет программисту возможность полного управления реализацией и что программы, написанные на С, работают, как правило, весьма быстро. Расплачиваться за это приходится тем, что программист вынужден выполнять большую работу: он сам должен выделять и освобождать память, создавать хэш-таблицы, связные списки и т. п. С – инструмент с остротой бритвы: с его помощью можно создать и элегантную программу, и кровавое месиво.
Упражнение 3.1
Алгоритм случайного выбора элемента из списка неизвестной длины зависит от качества генератора случайных чисел. Спроектируйте и осуществите эксперименты для проверки метода на практике.
Упражнение 3.2
Если вводимые слова хранятся в отдельной хэш-таблице, то каждое слово окажется записанным лишь единожды, следовательно – экономится место. Оцените, сколько именно – измерьте какие-нибудь фрагменты текста. Подобная организация позволит нам сравнивать указатели, а не строки в хэш-цепочках префиксов, что выполняется быстрее. Реализуйте этот вариант и оцените изменения в быстродействии и размере используемой памяти.
Упражнение 3.3
Удалите выражения, которые помещают сигнальные метки NONWORD в начало и конец данных, и измените generate так, чтобы она нормально запускалась и останавливалась без их использования. Убедитесь, что вывод корректен для 0, 1, 2, 3 и 4 слов. Сравните код с использованием сигнальных меток и код без них.