Оптимизация - Форум «Всё о Паскале»

Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++

Оптимизация

Caranthir	11.12.2006 17:34 Сообщение #1
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0	Подскажите плиз) Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется.

Ответов

Caranthir	14.12.2006 2: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 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