Помощь - Поиск - Пользователи - Календарь
Полная версия: Оптимизация
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
Страницы: 1, 2
Michael_Rybak
Давай, ждем smile.gif
Caranthir
немного переделал твою первую версию hiv:
(с) и результат прилагается)
Нажмите для просмотра прикрепленного файла

PS/ самому плохо думается
hiv
Цитата(Caranthir @ 17.12.2006 21:53) *
немного переделал твою первую версию hiv:

Плохо переделал dry.gif
Во первых использование меток считается плохим тоном программирования на паскале и может вызывать кучу завуалированных ошибок.
В вторых теряется смысл битовой сортировки, ты по индексу [tel[k]-sdvig] массива rad производишь обычный подсчет количества дубликатов номера tel[k], а потом еще их распечатываешь в итоговом файле в том же дублированном количестве... А как же условие задачи?
Цитата
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.

Так что подумай на досуге yes2.gif
hiv
В третьих: функция setlength() - не обнуляет массив, в итоге у тебя могут появиться номера, которых в твоем исходном никогда небыло... (сравни размеры твоего исходного файла и файла с результатами сортировки - первый признак наличия ошибки).
hiv
Вот третий вариант сортировки (супер твикс): blum.gif
1) Определяем диапазон номеров которые будем читать и сразу сортировать битовой сортировкой.
2) Прочитываем весь файл и обрабатываем только те номера, которые входят в диапазон.
3) Сохраняем результат сортировки текущего диапазона в итоговый файл.
4) Берем следующий диапазон чисел и заново перечитываем исходный файл, т.е. переходим к пункту 2 smile.gif Заканчиваем тогда, когда диапазон рассматриваемых чисел выходит за максимальный номер, в данном случае 10^7.
Никаких временных файлов на диске не создается. В данной задаче исходный файл прочитывается всего два раза. Также везде буферный ввод вывод.
Спасибо Michael_Rybak за подсказку. См. пост 49

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,657 сек. Что почти догнало метод быстрой сортировки cool.gif
Максимум выделяемой динамической памяти на данные не превысил 978556 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Нажмите для просмотра прикрепленного файла
Параметры машины: теже
Michael_Rybak
Прикольно smile.gif
hiv
Вот четвертый вариант сортировки (всем по ковшу): blum.gif
Метод довольно подробно описан Michael_Rybak в этой теме (см. пост 40). Добавлю, что не использовал слитие номеров в общий ковш, как рассказывал Michael_Rybak, а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов. Потом на каждом шаге просто менял эти две группы временных файлов местами, т.е. то что записывал - начинал читать от туда и наоборот. 20 временных файлов - это не так много smile.gif
Также везде буферный ввод вывод.

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,765 сек. Что обогнало первый метод cool.gif я в шоке crazy.gif думал что медленнее будет.
Максимум выделяемой динамической памяти на данные не превысил 376 404 байт. (в принципе ничего кроме буферов чтения записи)
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Нажмите для просмотра прикрепленного файла
Параметры машины: теже

ЗЫ: Все я выдохся... Да и надоело уже...
Michael_Rybak
Цитата(hiv @ 19.12.2006 16:13) *

а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов


good.gif

Цитата(hiv @ 19.12.2006 16:13) *

ЗЫ: Все я выдохся... Да и надоело уже...


Ничего себе выдохся smile.gif Перепробовал столько smile.gif Супер!
hiv
Спасибо! biggrin.gif
Caranthir
Спасибо!!!

Всем кто развивал тему.

Особо признателен Michael_Rybak и hiv. Молодцы! pleasantry.gif applause.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.