 Оптимизация |
| Caranthir |
 11.12.2006 13:34
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация:  0   |
Подскажите плиз)
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется. |
   |
 
|
  |
Ответов
| hiv |
11.12.2006 14:34
Сообщение
#2
|
 Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Первое, что приходит на ум:
1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера. 2) в цикле читать файлы с 00 по 99, сортируя телефонные номера по возрастанию. После сортировки каждый раз дописывать результат в итоговый файл. Быстрый метод сортировки подсказать трудно, т.к. объем вычислений предугадать невозможно (от 1 до 1 000 000). Есть вопрос - могут ли номера телефонов начинаться с 0? ЗЫ: На чем реализовывать будете? -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
|
|
|
Сообщений в этой теме
Caranthir Оптимизация 11.12.2006 13:34
klem4 Эм ну ты бы показал свой вариант, а то что оптимиз... 11.12.2006 14:05 Malice Файл текстовый ? Может есть смысл переписать его в... 11.12.2006 14:29 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 Вот битовой там, если не ошибаюсь, нет. 14.12.2006 19:11 hiv Вот второй вариант сортировки (просто супер): :bl... 15.12.2006 11:45 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
|
Текстовая версия | 12.08.2025 1:34 |