 Оптимизация |
| Caranthir |
 11.12.2006 13:34
Сообщение
#1
|
 Новичок  Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация:  0   |
Подскажите плиз)
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется. |
   |
 
|
  |
Ответов
| Michael_Rybak |
18.12.2006 14:57
Сообщение
#2
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Прикольно
 |
|
|
|
| hiv |
19.12.2006 17:13
Сообщение
#3
|
 Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Вот четвертый вариант сортировки (всем по ковшу):
 Метод довольно подробно описан Michael_Rybak в этой теме (см. пост 40). Добавлю, что не использовал слитие номеров в общий ковш, как рассказывал Michael_Rybak, а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов. Потом на каждом шаге просто менял эти две группы временных файлов местами, т.е. то что записывал - начинал читать от туда и наоборот. 20 временных файлов - это не так много Также везде буферный ввод вывод. Итого: Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров). Время работы 3,765 сек. Что обогнало первый метод  я в шоке  думал что медленнее будет.Максимум выделяемой динамической памяти на данные не превысил 376 404 байт. (в принципе ничего кроме буферов чтения записи) Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров). Программа - 
telsort4.zip ( 2.67 килобайт )
Кол-во скачиваний: 354Параметры машины: теже ЗЫ: Все я выдохся... Да и надоело уже... -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
|
|
|
| Michael_Rybak |
19.12.2006 17:22
Сообщение
#4
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата(hiv @ 19.12.2006 16:13)  а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов  Цитата(hiv @ 19.12.2006 16: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 Вот битовой там, если не ошибаюсь, нет. 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 hiv Спасибо! :biggrin: 19.12.2006 17:58 Caranthir [indent]Спасибо!!!
Всем кто развивал т... 21.12.2006 23:02 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 8.12.2025 22:12 |