IPB
ЛогинПароль:

> Оптимизация
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 48
Пол: Мужской

Репутация: -  0  +


Подскажите плиз)

Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.

Результат.
Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров.

Ограничения.
~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Вот первый вариант.
Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера.
Везде буферный ввод вывод.
Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал).
Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 4,157 сек. Кто быстрее? cool.gif
Максимум выделяемой динамической памяти на данные не превысил 742900 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Прикрепленный файл  telsort1.zip ( 2.61 килобайт ) Кол-во скачиваний: 333
(обновлена)

Параметры машины:
ОС - WinXP
Процессор - Pentium4 1.8ГГц
ОЗУ - 512 Мб
Винт - 40Гб 7200об/мин

ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak.
Если у кого есть предложения по оптимизации готового кода - буду рад smile.gif

Сообщение отредактировано: hiv -


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(hiv @ 13.12.2006 11:15) *

Вот первый вариант.
Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера.
Везде буферный ввод вывод.
Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал).
Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 4,157 сек. Кто быстрее? cool.gif
Максимум выделяемой динамической памяти на данные не превысил 742900 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа -

Параметры машины:
ОС - WinXP
Процессор - Pentium4 1.8ГГц
ОЗУ - 512 Мб
Винт - 40Гб 7200об/мин

ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak.
Если у кого есть предложения по оптимизации готового кода - буду рад smile.gif


Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 660
Пол: Мужской
Реальное имя: Михаил

Репутация: -  11  +


Цитата(Michael_Rybak @ 13.12.2006 17:07) *

Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь?

Поподробнее, а то твоя моя не понимай... smile.gif

Подумал на счет твоих постов 14 и 20 - с битовой сортировкой не получится:
7-мизначка = 9 000 000 номеров
делим на 8 бит = 1125000 байт
что больше 1Мбайта sad.gif
А использовать пузырек - не поможет (по объему около 40 сек выйдет).


--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Поподробнее, а то твоя моя не понимай... smile.gif


Есть т.н. ковшовая, или поразрядная сортировка.
Ковши = файлы.

Есть 1 исходный ковш (большой), и 10 малых, пронумерованных от 0 до 9.

Идем по большому ковшу, разбрасываем по малым все числа, в зависимости от последней цифры (младшего разряда).

Потом сливаем малые ковши в порядке возрастания в большой ковш.

Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8.

Цитата
Подумал на счет твоих постов 14 и 20 - с битовой сортировкой не получится:
7-мизначка = 9 000 000 номеров
делим на 8 бит = 1125000 байт
что больше 1Мбайта sad.gif
А использовать пузырек - не поможет (по объему около 40 сек выйдет).


А вот тут уже моя твоя smile.gif
Что такое битовая сортировка?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Caranthir   Оптимизация   11.12.2006 17:34
klem4   Эм ну ты бы показал свой вариант, а то что оптимиз…   11.12.2006 18:05
Malice   Файл текстовый ? Может есть смысл переписать его в…   11.12.2006 18:29
hiv   Первое, что приходит на ум: 1) Последовательно про…   11.12.2006 18:34
Caranthir   Мысли: При объёме ОП в 1 Мб туда можно забросить …   11.12.2006 18:48
hiv   Еще раз повторю - могут ли номера телефонов начина…   11.12.2006 18:51
Lapp   От этого зависит прийдется тебе работать с просто…   11.12.2006 19:03
Caranthir   Неа, нулей нет А если разбивать на файлы, тогда …   11.12.2006 18:55
hiv   :) Тогда номер телефона можно спокойно хранить в …   11.12.2006 19:03
Lapp   2Lapp: Номера могут быть и разной длины... К стат…   11.12.2006 19:18
Caranthir   "для хранения данных в системе может быть выд…   11.12.2006 19:07
hiv   Методы сортировки   11.12.2006 19:10
Caranthir   А вот если разбивать на 4 файла по 250000, тогда п…   11.12.2006 19:16
Michael_Rybak   Проблема с ведущими нулями решается временным допи…   11.12.2006 19:27
Caranthir   хм...нечего я не искажал. Файл текстовый-> номе…   11.12.2006 19:29
Caranthir   Respeсt кто помогал))   11.12.2006 19:42
klem4   Кстати не стоит забывать о том, что после разбиени…   11.12.2006 20:15
Michael_Rybak   Кстати не стоит забывать о том, что после разбиен…   11.12.2006 21:30
hiv   Ну хорошо. Можно попробовать обоими способами и ср…   12.12.2006 13:09
Malice   Вот вам генератор файлов для экспериментов: proced…   12.12.2006 13:39
hiv   Вот вам генератор файлов для экспериментов: Входно…   12.12.2006 14:30
Malice   Входной формат файла - текстовый. Данные не должн…   12.12.2006 14:33
hiv   2klem4: При использовании буферного чтения записи …   11.12.2006 20:32
Caranthir   не совсем понял..Поясни пжл как осуществить буферн…   11.12.2006 20:47
Caranthir   При сливании сравниваются только номера самих файл…   11.12.2006 21:55
Michael_Rybak   А как ты разбросаешь по файлам, чтобы в первом фай…   11.12.2006 22:52
Caranthir   прочитать весь массив, создать дополнительные фай…   11.12.2006 23:15
Michael_Rybak   А если все номера начинаются на одни и те же две ц…   12.12.2006 2:09
Caranthir   Хм...Ты прав. Если одинаковых чисел >250000 бр…   12.12.2006 3:19
Michael_Rybak   Чтобы работало в любом случае, надо 1) разбить п…   12.12.2006 3:38
Caranthir   Интересно... попробую Спасибо   12.12.2006 4:57
Altair   ИМХО (по основной задаче) Портируем текстовый фай…   12.12.2006 19:33
Michael_Rybak   Круто, риспект :) Только опять непонятно, как быт…   12.12.2006 20:12
Altair   А такие номера могут существовать? Если да, допис…   12.12.2006 20:35
hiv   Вот первый вариант. Номера разбрасываются по 90 вр…   13.12.2006 16:15
Malice   Входной файл текстовый без повторяющихся номеров …   13.12.2006 17:29
hiv   Т.е. Все числа выровнены и добиты в начале 0-ми ?…   13.12.2006 18:35
Michael_Rybak   Вот первый вариант. Номера разбрасываются по 90 в…   13.12.2006 21:07
hiv   Еще можно попробовать поразрядную сортировку (т.е…   13.12.2006 21:41
Michael_Rybak   Есть т.н. ковшовая, или поразрядная сортировка. …   13.12.2006 22:05
hiv   Есть т.н. ковшовая, или поразрядная сортировка... …   14.12.2006 13:54
Caranthir   Не стесняйся - программу в студию :) Это я твою …   14.12.2006 16:41
hiv   Это я твою смотрел и так отсортировалось_) Могу то…   14.12.2006 17:16
Michael_Rybak   А я думаю что не будет :) Это когда сортируем…   14.12.2006 20:06
Caranthir   блин....слабо пока, много получаетсся)) и....ээ...…   14.12.2006 2:32
klem4   Методы сортировок :unsure:   14.12.2006 23:06
Michael_Rybak   Вот битовой там, если не ошибаюсь, нет.   14.12.2006 23:11
hiv   Вот второй вариант сортировки (просто супер): :bl…   15.12.2006 15:45
Michael_Rybak   Круто, спасибо, что пробуешь :) У меня еще вот ка…   15.12.2006 18:20
hiv   2Michael_Rybak Стыдно что сам до этого не додумалс…   15.12.2006 20:30
Michael_Rybak   Давай, ждем :)   15.12.2006 21:32
Caranthir   немного переделал твою первую версию hiv: (с) и ре…   18.12.2006 1:53
hiv   немного переделал твою первую версию hiv: Плохо пе…   18.12.2006 13:42
hiv   В третьих: функция setlength() - не обнуляет масси…   18.12.2006 14:01
hiv   Вот третий вариант сортировки (супер твикс): :blu…   18.12.2006 17:31
Michael_Rybak   Прикольно :)   18.12.2006 18:57
hiv   Вот четвертый вариант сортировки (всем по ковшу): …   19.12.2006 21:13
Michael_Rybak   а просто считывал последовательно из 10 временных…   19.12.2006 21:22
hiv   Спасибо! :biggrin:   19.12.2006 21:58
Caranthir   [indent]Спасибо!!! Всем кто развивал т…   22.12.2006 3:02


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 5.12.2021 6:32
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name