 Оптимизация |
| Caranthir |
 11.12.2006 13:34
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация:  0   |
Подскажите плиз)
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется. |
   |
 
|
  |
Ответов
| Caranthir |
13.12.2006 22:32
Сообщение
#2
|
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0 |
блин....слабо пока, много получаетсся))
и....ээ...последние номера то не сортируются, кроме как по именам файлов, только первые 8971947 8962540 8916484 8912716 8941187 8915338 8971871 8923658 8938009 8929848 8910452 8982093 8940902 8941257 8942629 8961911 8985513 8948864 8976854 8953015 8960296 8933310 8987267 8987947 8982026 8912167 8950310 8938580 8982516 8981755 8987127 8936605 8994136 |
|
|
|
Сообщений в этой теме
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 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
|
Текстовая версия | 20.06.2025 22:16 |