1. Многие системы подготовки документов позволяют избавиться от команд форматирования и оставить только текстовую часть файла. Когда я работал с программой поиска повторяющихся строк из раздела 15.2, я обнаружил, что она была очень чувствительна к форматированию текста. За 36 секунд она обработала 4 460 056 символов Библии короля Иакова, и самая длинная повторявшаяся строка была 269 символов длиной. Когда я убрал номера строф, чтобы длинные строки могли выходить за их границы, длина повторявшейся строки возросла до 563 символов, причем она была найдена за приблизительно то же время.
3. Поскольку при каждой операции вставки выполняется много операций поиска, па выделение памяти будет уходить лишь небольшая часть времени. Добавление специальной функции выделения памяти ускорило работу программы лишь на 0.06 с, то есть на 10% от фазы считывания, по лишь па 2% от всего времени работы программы.
5, Можно добавить еще одну таблицу шар к программе па C++, чтобы связать с каждым счетчиком последовательность слов. В программе па С мы могли бы упорядочить массив по полю счетчика, а затем перебрать его содержимое (поскольку некоторые слова будут повторяться очень много раз, этот массив должен оказаться намного меньше, чем входной файл). Для большинства документов можно использовать индексацию по ключу и хранить массив связанных списков для счетчиков в диапазоне 1..1000.
7. Учебники по теории алгоритмов предупреждают об опасности получения на входе файла из буквы «а», повторенной 1000 раз. Мне показалось проще испытать программу на файле, состоящем только пз переводов строки. На обработку 5000 таких символов было затрачено 2,09 с; па 10 000 — 8,9 с, а па 20 000 — 37,9 с. Время работы программы росло несколько быстрее, чем квадрат размера файла, возможно, из-за п log,)? сравнений, каждое пз которых выполнялось за время, пропорциональное п. Более реалистичную ситуацию с плохими данными можно имитировать, сделав один файл пз двух копий какого-либо большого файла.
Опубликовал vovan666
April 17 2013 00:07:16 ·
0 Комментариев ·
2866 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
