![]() |
![]() ![]() |
![]() |
Caranthir |
![]()
Сообщение
#1
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Подскажите плиз)
Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров. Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется. |
klem4 |
![]()
Сообщение
#2
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Эм ну ты бы показал свой вариант, а то что оптимизировать-то ? Да и глупо получится если кто-то сделает программу такую-же как у тебя ...
Или у тебя вообще мыслей нету никаких по поводу решения ? -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Malice |
![]()
Сообщение
#3
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: ![]() ![]() ![]() |
Файл текстовый ? Может есть смысл переписать его в типизированный (file of longint), потом отсортировать любым способом и назад..
|
hiv |
![]()
Сообщение
#4
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Первое, что приходит на ум:
1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера. 2) в цикле читать файлы с 00 по 99, сортируя телефонные номера по возрастанию. После сортировки каждый раз дописывать результат в итоговый файл. Быстрый метод сортировки подсказать трудно, т.к. объем вычислений предугадать невозможно (от 1 до 1 000 000). Есть вопрос - могут ли номера телефонов начинаться с 0? ЗЫ: На чем реализовывать будете? -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
![]()
Сообщение
#5
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Мысли:
При объёме ОП в 1 Мб туда можно забросить ~ 250000 чисел. -> 1. исходный(текстовый) файл разбивать отдельные файлы и сортировать по символам т.к. числа записаны в файле в виде строк 2. Разбить на ~256 (если орентироваться по байтам) файлов и сортировать по-байтам а потом каждый отсортированный записывать в файл-результат Файл текстовый ? Может есть смысл переписать его в типизированный (file of longint), потом отсортировать любым способом и назад.. А это намного быстрее? Первое, что приходит на ум: 1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера. ЗЫ: На чем реализовывать будете? на Delphi во-во, а по-байтам сортировать может ли это быть быстрее? |
hiv |
![]()
Сообщение
#6
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Еще раз повторю - могут ли номера телефонов начинаться с 0?
От этого зависит прийдется тебе работать с просто числами или со строками. Если есть ноль в начале, то - со строками. Если так, то количество цифр в номере всегда одно и тоже, тогда можно использовать не string, а массив из char (экономиться один байт - длина строки). Далее - сортировка не байтами! Чтобы хранить номер нужна либо строка (минимум 7байт) либо DWORD (4байта). -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
![]()
Сообщение
#7
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Неа, нулей нет
А если разбивать на файлы, тогда кол-во чисел в каждом оставит около 10.000, подскажите каккую лучше сортировку применить? Сообщение отредактировано: Caranthir - 11.12.2006 14:58 |
Lapp |
![]()
Сообщение
#8
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
От этого зависит прийдется тебе работать с просто числами или со строками. Не понимаю, что меняет наличие нулей в начале? число как число, только при выводе его нужно добить нулями слева.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
hiv |
![]()
Сообщение
#9
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
![]() и пользоваться динамическим массивом из 250 000 longint. Соответственно - 4 временных файла. Вопрос следующий - 1Мбайт ограничения только на данные связанные с номерами телефонов или на всю память, что программа будет занимать вместе с кодом? К стати longint сравниваются просто < > = ![]() 2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09 ![]() Сообщение отредактировано: hiv - 11.12.2006 15:05 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
![]()
Сообщение
#10
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
"для хранения данных в системе может быть выделено до 1 Мб"
|
hiv |
![]()
Сообщение
#11
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
-------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
![]()
Сообщение
#12
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
А вот если разбивать на 4 файла по 250000, тогда придётся отсортировав каждый, совмещать отсортированные
-> наверное надо разбить на кратные (или 2 или 10) а, следовательно что может быть быстрее отсортированно и объединено 1000 файлов по 1000 или же 10 по 100000??? Спс конечно за ссылку, но я уже её прочитал))) там нету на 1000000)) хм...и поразрядная что-то не компил( |
Lapp |
![]()
Сообщение
#13
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09 ![]() это, конечно, верно. Но в условии автор ясно сказал: "числа" - и при этом добавил, что нет равных. Следовательно, 09 и 9 не могут встретиться в одном файле. Но я уже понимаю, что автор на самом деле имел в виду все же телефонные номера, то есть строки символов, что есть абсолютно не числа, на самом-то деле.. Может, он думал, что искажая условие, облегчает задачу?.. Помимо прочего, тема абсолютно не на своем месте. Переношу в Алгоритмы. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Michael_Rybak |
![]()
Сообщение
#14
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Проблема с ведущими нулями решается временным дописыванием перед номером одной цифры, равной его длине
![]() А дальше - Цитата и пользоваться динамическим массивом из 250 000 longint. Соответственно - 4 временных файла. Даже если группировать по 100 000 лонгинтов (тогда и с кодом вместе легко впишемся в 1 МБ), получится 10 групп. Сортировка каждой из них в ОП - порядка 100 000 * log 100 000, слияние в один файл - 1 000 000 * 10 (можно и 1 000 000 * log 10, но зачем?). Должно работать за несколько секунд. Кстати, скорость может еще существенно зависеть от ввода-вывода. Например, в С++ ввод/вывод такого объема данных с помощью fstream (а не file) займет больше времени, чем собственно сортировка. Цитата следовательно что может быть быстрее отсортированно и объединено 1000 файлов по 1000 или же 10 по 100000??? Если мы разбиваем n чисел на группы по q чисел в каждой, то сортировка всех групп займет O(n/q * (q log q)) = O(n log q), слияние - O(n * log (n / q)) Итого имеем O(n log q) + O(n log (n / q)) = O(n max (log q, log (n / q))). Из этого следует, что оптимальнее всего выбирать q равным sqrt(n). НО! Это - с точки зрения асимптотики. С практической же точки зрения нужно еще учесть 1) время на работу с файлами 2) ненужность приведенных оценок ![]() Сообщение отредактировано: Michael_Rybak - 11.12.2006 15:31 |
Caranthir |
![]()
Сообщение
#15
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
хм...нечего я не искажал. Файл текстовый-> номера там находящиеся явл строками.
и всё же подскажите пож. как "правильнее" разбить данный файл и в каком формате обрабатывать? |
Caranthir |
![]()
Сообщение
#16
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Respeсt кто помогал))
|
klem4 |
![]()
Сообщение
#17
|
![]() Perl. Just code it! ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: ![]() ![]() ![]() |
Кстати не стоит забывать о том, что после разбиения то придется все это дело "сливать" ... не особо то это бытро будет
![]() -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
hiv |
![]()
Сообщение
#18
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
2klem4: При использовании буферного чтения записи во временных файлах (к стати их лучше тоже делать типа longint), это будет существенно быстро.
-------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
![]()
Сообщение
#19
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
не совсем понял..Поясни пжл как осуществить буферное чтение программно
|
Michael_Rybak |
![]()
Сообщение
#20
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Кстати не стоит забывать о том, что после разбиения то придется все это дело "сливать" ... не особо то это бытро будет ![]() Это будет не намного медленнее, чем считывать данные из входного файла. В пределах нескольких секунд. А буферное чтение тут, по-моему, не причем - нам же между собой номера из разных файлов все время сравнивать надо при слиянии. |
![]() ![]() |
![]() |
Текстовая версия | 21.06.2025 22:47 |