Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.
Результат. Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров.
Ограничения. ~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется.
Первое, что приходит на ум: 1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера. 2) в цикле читать файлы с 00 по 99, сортируя телефонные номера по возрастанию. После сортировки каждый раз дописывать результат в итоговый файл. Быстрый метод сортировки подсказать трудно, т.к. объем вычислений предугадать невозможно (от 1 до 1 000 000). Есть вопрос - могут ли номера телефонов начинаться с 0?
ЗЫ: На чем реализовывать будете?
--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
При объёме ОП в 1 Мб туда можно забросить ~ 250000 чисел. -> 1. исходный(текстовый) файл разбивать отдельные файлы и сортировать по символам т.к. числа записаны в файле в виде строк 2. Разбить на ~256 (если орентироваться по байтам) файлов и сортировать по-байтам а потом каждый отсортированный записывать в файл-результат
Цитата(Malice @ 11.12.2006 14:29)
Файл текстовый ? Может есть смысл переписать его в типизированный (file of longint), потом отсортировать любым способом и назад..
А это намного быстрее?
Цитата(hiv @ 11.12.2006 14:34)
Первое, что приходит на ум: 1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера.
ЗЫ: На чем реализовывать будете?
на Delphi во-во, а по-байтам сортировать может ли это быть быстрее?
Еще раз повторю - могут ли номера телефонов начинаться с 0? От этого зависит прийдется тебе работать с просто числами или со строками. Если есть ноль в начале, то - со строками. Если так, то количество цифр в номере всегда одно и тоже, тогда можно использовать не string, а массив из char (экономиться один байт - длина строки). Далее - сортировка не байтами! Чтобы хранить номер нужна либо строка (минимум 7байт) либо DWORD (4байта).
--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
Тогда номер телефона можно спокойно хранить в типе longint (Delphi) - 4байта и пользоваться динамическим массивом из 250 000 longint. Соответственно - 4 временных файла. Вопрос следующий - 1Мбайт ограничения только на данные связанные с номерами телефонов или на всю память, что программа будет занимать вместе с кодом? К стати longint сравниваются просто < > =
2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09
Сообщение отредактировано: hiv -
--------------------
Никогда не жадничай. Свои проблемы с любовью дари людям!
А вот если разбивать на 4 файла по 250000, тогда придётся отсортировав каждый, совмещать отсортированные -> наверное надо разбить на кратные (или 2 или 10) а, следовательно что может быть быстрее отсортированно и объединено 1000 файлов по 1000 или же 10 по 100000???
2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09
это, конечно, верно. Но в условии автор ясно сказал: "числа" - и при этом добавил, что нет равных. Следовательно, 09 и 9 не могут встретиться в одном файле. Но я уже понимаю, что автор на самом деле имел в виду все же телефонные номера, то есть строки символов, что есть абсолютно не числа, на самом-то деле.. Может, он думал, что искажая условие, облегчает задачу?..
Помимо прочего, тема абсолютно не на своем месте. Переношу в Алгоритмы.
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой
Проблема с ведущими нулями решается временным дописыванием перед номером одной цифры, равной его длине При этом, сравнивая числа во время сортировки, нужно это учитывать, а как именно - зависит от того, могут ли быть номера "09" и "0009", и если да, то как их сравнивать.
А дальше -
Цитата
и пользоваться динамическим массивом из 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) ненужность приведенных оценок Реально, делай q хоть 1000, хоть 10, для таких ограничений будет летать.
хм...нечего я не искажал. Файл текстовый-> номера там находящиеся явл строками. и всё же подскажите пож. как "правильнее" разбить данный файл и в каком формате обрабатывать?
Правила форума
Оптимизация
Тогда номер телефона можно спокойно хранить в типе longint (Delphi) - 4байта