phrase = inputchars
for (wordsleft = 10000. wordsleft > 0. wordsleft--)
1 = -1 u = nword whi1e 1+1 !* u m = (1 + u) / 2
if wordncmp(word[m]. phrase) < 0
1 = m el se u = m
for (i = 0; wordncmp(phrase. word[u+i]) == 0. i++) if rand() % (i + 1) == 0 p = word[u+i] phrase = skip(p, 1) if strlen(skip(phrase. k-1)) == 0 break
print skip(phrase, k-1)
Глава 3 книги Кернигана и Пайка «Практика программирования» (о которой рассказывается в разделе 5.9 главы 5) посвящена общим вопросам «разработки и реализации». В качестве примера авторы приводят программу порождения случайного текста с помощью цепей Маркова на уровне слов, поскольку «это типично для большинства программ: какие-то данные поступают на вход, какие-то получаются на выходе, а в процессе обработки выполняются какие-то хитрые действия». В их книге рассказывается история этой задачи и приводятся примеры реализации программ на языках С, Java, C++, Awk и Perl.
Программа, написанная нами, оказывается в выигрыше при сравнении с их программой на С. Код примерно вдвое короче; представление фразы с помощью указателя на к последовательных слов эффективно с точки зрения экономии памяти
и легко в реализации. При объеме входных данных около 1 Мбайт программы работают с приблизительно одинаковой скоростью. Поскольку Керниган и Пайк используют структуру данных, занимающую несколько больший объем, и выделяют память с помощью малоэффективного оператора malloc, наша программа расходует приблизительно на порядок меньше памяти (на моем компьютере). Если оптимизировать ее с учетом решения задачи 14 и заменить двоичный поиск и сортировку таблицей хэширования, программа из этого раздела станет работать вдвое быстрее (но при этом объем используемой памяти увеличится примерно на 50%).
Опубликовал vovan666
April 17 2013 00:04:56 ·
0 Комментариев ·
4890 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
