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

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

Оптимизация

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

Сообщений в этой теме

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

« Предыдущая тема · Алгоритмы · Следующая тема »

2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)

Пользователей: 0