Очевидный вариант программы использует в качестве отправной точки сортировку слиянием общего вида, которая может быть затем оптимизирована с учетом того факта, что сортируются целые числа. Это сократит программу с двухсот до нескольких десятков строк и несколько ускорит ее выполнение. Однако на кодирование и отладку такой программы по-прежнему потребуется несколько дней.
Второй вариант решения учитывает детали конкретной задачи. Если мы отведем под каждое число семь байт, в доступном мегабайте оперативной памяти поместится 143 ООО номеров. Если использовать 32-битное представление целых чисел, в тот же мегабайт поместится уже 250 ООО номеров. Поэтому можно написать программу, которая будет считывать файл 40 раз. На первом проходе в память считываются все записи с порядковыми номерами от 0 до 249 999, которые затем сортируются и записываются в выходной файл. За второй проход сортируются записи с номерами от 250 ООО до 499 999, а за 40-й — от 9 750 000 до 9 999 999. Для сортировки можно использовать алгоритм быстрой сортировки (quicksort), который занимает всего 20 строк кода (см. главу 11). Вся программа, таким образом, займет всего лишь один или два экрана. Кроме того, нам больше не придется беспокоиться о временных файлах; к сожалению, цена за эти улучшения — сорок операций чтения/записи файла.
Сортировка слиянием считывает входной файл один раз, сортирует его с использованием временных файлов, которые считываются и записываются много раз, а затем записывает результат за один проход (рис. 1.1).
Алгоритм с сорока проходами осуществляет считывание входного файла 40 раз, записывая результат за один раз, не используя никаких временных файлов (рис. 1.2).
Оптимальной для нас была бы программа, работающая по следующей схеме, соединяющей преимущества предыдущих: входной файл считывается только один раз, и временные файлы не используются (рис. 1.3).
Реализовать это можно, лишь отобразив все числа из входного файла в доступный мегабайт оперативной памяти. Таким образом, задача сводится к отображению не более чем десяти миллионов отличающихся друг от друга целых чисел в приблизительно восемь миллионов доступных бит. Попробуйте придумать подходящее отображение.
Опубликовал vovan666
April 16 2013 23:34:02 ·
0 Комментариев ·
3907 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
