 Оптимизация |
| Caranthir |
 11.12.2006 13:34
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация:  0   |
Подскажите плиз)
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется. |
   |
 
|
  |
Ответов
| Michael_Rybak |
14.12.2006 19:11
Сообщение
#2
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Вот битовой там, если не ошибаюсь, нет.
|
|
|
|
| hiv |
15.12.2006 11:45
Сообщение
#3
|
 Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Вот второй вариант сортировки (просто супер):
 1) Читаем исходный файл насколько влазиет в память, потом сортируем и сохраняем во временный файл, следующая итерация чтения исходного файла также сортируется и заносится в следующий временный файл. Т.о. чем меньше памяти на данные мы выделяем, тем больше временных файлов. Сортировка проводится методом "Быстрой сортировки" описанной в FAQ и взятой от туда  2) Сливаем все временные файлы в итоговый, каждый раз выбирая минимальное значение среди прочтенных из всех временных файлов. Также везде буферный ввод вывод. Спасибо Volvo за FAQ и Michael_Rybak за метод сортировки слияниями файлов. См. пост 26 Итого: Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров). Время работы 3,421 сек. Кто еще быстрее? cool.gif Максимум выделяемой динамической памяти на данные не превысил 970372 байт. Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров). Программа - 
telsort2.zip ( 2.98 килобайт )
Кол-во скачиваний: 402Параметры машины: теже ЗЫ: К стати обновил первую версию - теперь повторяющихся номеров в итоговом файле не будет, даже если они были в исходном. См. пост 35. Во втором методе повторяющиеся номера не удаляются. Цитата Что такое битовая сортировка? В принципе это то что говорил Altair в посте 32, только индексом является просто 1 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь Сообщение отредактировано: hiv - 15.12.2006 12:13 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
|
|
|
Сообщений в этой теме
Caranthir Оптимизация 11.12.2006 13:34
klem4 Эм ну ты бы показал свой вариант, а то что оптимиз... 11.12.2006 14:05 Malice Файл текстовый ? Может есть смысл переписать его в... 11.12.2006 14:29 hiv Первое, что приходит на ум:
1) Последовательно про... 11.12.2006 14:34 Caranthir Мысли:
При объёме ОП в 1 Мб туда можно забросить ... 11.12.2006 14:48 hiv Еще раз повторю - могут ли номера телефонов начина... 11.12.2006 14:51
Lapp
От этого зависит прийдется тебе работать с просто... 11.12.2006 15:03 Caranthir Неа, нулей нет
А если разбивать на файлы, тогда ... 11.12.2006 14:55 hiv :) Тогда номер телефона можно спокойно хранить в ... 11.12.2006 15:03 Lapp
2Lapp: Номера могут быть и разной длины... К стат... 11.12.2006 15:18 Caranthir "для хранения данных в системе может быть выд... 11.12.2006 15:07 hiv Методы сортировки 11.12.2006 15:10 Caranthir А вот если разбивать на 4 файла по 250000, тогда п... 11.12.2006 15:16 Michael_Rybak Проблема с ведущими нулями решается временным допи... 11.12.2006 15:27 Caranthir хм...нечего я не искажал. Файл текстовый-> номе... 11.12.2006 15:29 Caranthir Respeсt кто помогал)) 11.12.2006 15:42 klem4 Кстати не стоит забывать о том, что после разбиени... 11.12.2006 16:15 Michael_Rybak
Кстати не стоит забывать о том, что после разбиен... 11.12.2006 17:30 hiv Ну хорошо. Можно попробовать обоими способами и ср... 12.12.2006 9:09 Malice Вот вам генератор файлов для экспериментов:
proced... 12.12.2006 9:39 hiv Вот вам генератор файлов для экспериментов:
Входно... 12.12.2006 10:30 Malice
Входной формат файла - текстовый. Данные не должн... 12.12.2006 10:33 hiv 2klem4: При использовании буферного чтения записи ... 11.12.2006 16:32 Caranthir не совсем понял..Поясни пжл как осуществить буферн... 11.12.2006 16:47 Caranthir При сливании сравниваются только номера самих файл... 11.12.2006 17:55 Michael_Rybak А как ты разбросаешь по файлам, чтобы в первом фай... 11.12.2006 18:52 Caranthir прочитать весь массив, создать дополнительные фай... 11.12.2006 19:15 Michael_Rybak А если все номера начинаются на одни и те же две ц... 11.12.2006 22:09 Caranthir Хм...Ты прав.
Если одинаковых чисел >250000 бр... 11.12.2006 23:19 Michael_Rybak Чтобы работало в любом случае, надо
1) разбить п... 11.12.2006 23:38 Caranthir Интересно... попробую
Спасибо 12.12.2006 0:57 Altair ИМХО (по основной задаче)
Портируем текстовый фай... 12.12.2006 15:33 Michael_Rybak Круто, риспект :)
Только опять непонятно, как быт... 12.12.2006 16:12 Altair
А такие номера могут существовать?
Если да, допис... 12.12.2006 16:35 hiv Вот первый вариант.
Номера разбрасываются по 90 вр... 13.12.2006 12:15 Malice
Входной файл текстовый без повторяющихся номеров ... 13.12.2006 13:29 hiv
Т.е. Все числа выровнены и добиты в начале 0-ми ?... 13.12.2006 14:35 Michael_Rybak
Вот первый вариант.
Номера разбрасываются по 90 в... 13.12.2006 17:07 hiv
Еще можно попробовать поразрядную сортировку (т.е... 13.12.2006 17:41 Michael_Rybak
Есть т.н. ковшовая, или поразрядная сортировка.
... 13.12.2006 18:05 hiv Есть т.н. ковшовая, или поразрядная сортировка...
... 14.12.2006 9:54 Caranthir
Не стесняйся - программу в студию :)
Это я твою ... 14.12.2006 12:41 hiv Это я твою смотрел и так отсортировалось_)
Могу то... 14.12.2006 13:16 Michael_Rybak
А я думаю что не будет :)
Это когда сортируем... 14.12.2006 16:06 Caranthir блин....слабо пока, много получаетсся))
и....ээ...... 13.12.2006 22:32 klem4
Методы сортировок
:unsure: 14.12.2006 19:06 Michael_Rybak Круто, спасибо, что пробуешь :)
У меня еще вот ка... 15.12.2006 14:20 hiv 2Michael_Rybak
Стыдно что сам до этого не додумалс... 15.12.2006 16:30 Michael_Rybak Давай, ждем :) 15.12.2006 17:32 Caranthir немного переделал твою первую версию hiv:
(с) и ре... 17.12.2006 21:53 hiv немного переделал твою первую версию hiv:
Плохо пе... 18.12.2006 9:42 hiv В третьих: функция setlength() - не обнуляет масси... 18.12.2006 10:01 hiv Вот третий вариант сортировки (супер твикс): :blu... 18.12.2006 13:31 Michael_Rybak Прикольно :) 18.12.2006 14:57 hiv Вот четвертый вариант сортировки (всем по ковшу): ... 19.12.2006 17:13 Michael_Rybak
а просто считывал последовательно из 10 временных... 19.12.2006 17:22 hiv Спасибо! :biggrin: 19.12.2006 17:58 Caranthir [indent]Спасибо!!!
Всем кто развивал т... 21.12.2006 23:02 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.06.2025 21:49 |