Оптимизация Опции

[Caranthir]

Подскажите плиз)

Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.

Результат.
Упорядоченнный по возрастанию список целых чисел, каждое из которых не превышает 10^7. На выходе должен быть получен файл отсортированных по возрастанию номеров.

Ограничения.
~1Мб ОП. место на диске не ограничено. время выполнения не должно превышать нескольких минут, если оно будет сокращено до нескольких секунд, то дальнейшая оптимизация не требуется.

[klem4]

Эм ну ты бы показал свой вариант, а то что оптимизировать-то ? Да и глупо получится если кто-то сделает программу такую-же как у тебя ...

Или у тебя вообще мыслей нету никаких по поводу решения ?

[Malice]

Файл текстовый ? Может есть смысл переписать его в типизированный (file of longint), потом отсортировать любым способом и назад..

[hiv]

Первое, что приходит на ум:
1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера.
2) в цикле читать файлы с 00 по 99, сортируя телефонные номера по возрастанию. После сортировки каждый раз дописывать результат в итоговый файл. Быстрый метод сортировки подсказать трудно, т.к. объем вычислений предугадать невозможно (от 1 до 1 000 000).
Есть вопрос - могут ли номера телефонов начинаться с 0?

ЗЫ: На чем реализовывать будете?

[Caranthir]

Мысли:

При объёме ОП в 1 Мб туда можно забросить ~ 250000 чисел. ->
1. исходный(текстовый) файл разбивать отдельные файлы и сортировать по символам т.к. числа записаны в файле в виде строк
2. Разбить на ~256 (если орентироваться по байтам) файлов и сортировать по-байтам
а потом каждый отсортированный записывать в файл-результат

Файл текстовый ? Может есть смысл переписать его в типизированный (file of longint), потом отсортировать любым способом и назад..

А это намного быстрее?

Первое, что приходит на ум:
1) Последовательно прочесть исходный файл, при этом одновременно писать прочитанные данные во временные файлы с именами от 00 до 99 в соответствии с первыми двумя цифрами телефонного номера.

ЗЫ: На чем реализовывать будете?

на Delphi
во-во, а по-байтам сортировать может ли это быть быстрее?

[hiv]

Еще раз повторю - могут ли номера телефонов начинаться с 0?
От этого зависит прийдется тебе работать с просто числами или со строками. Если есть ноль в начале, то - со строками. Если так, то количество цифр в номере всегда одно и тоже, тогда можно использовать не string, а массив из char (экономиться один байт - длина строки).
Далее - сортировка не байтами! Чтобы хранить номер нужна либо строка (минимум 7байт) либо DWORD (4байта).

[Caranthir]

Неа, нулей нет


А если разбивать на файлы, тогда кол-во чисел в каждом оставит около 10.000, подскажите каккую лучше сортировку применить?

Сообщение отредактировано: Caranthir - 11.12.2006 14:58

[Lapp]

От этого зависит прийдется тебе работать с просто числами или со строками.

Не понимаю, что меняет наличие нулей в начале? число как число, только при выводе его нужно добить нулями слева..

[hiv]

Тогда номер телефона можно спокойно хранить в типе longint (Delphi) - 4байта
и пользоваться динамическим массивом из 250 000 longint. Соответственно - 4 временных файла.
Вопрос следующий - 1Мбайт ограничения только на данные связанные с номерами телефонов или на всю память, что программа будет занимать вместе с кодом?
К стати longint сравниваются просто < > =

2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09

Сообщение отредактировано: hiv - 11.12.2006 15:05

[Caranthir]

"для хранения данных в системе может быть выделено до 1 Мб"

[hiv]

Методы сортировки

[Caranthir]

А вот если разбивать на 4 файла по 250000, тогда придётся отсортировав каждый, совмещать отсортированные
-> наверное надо разбить на кратные (или 2 или 10)
а, следовательно что может быть быстрее отсортированно и объединено 1000 файлов по 1000 или же 10 по 100000???

Методы сортировки

Спс конечно за ссылку, но я уже её прочитал)))
там нету на 1000000))
хм...и поразрядная что-то не компил(

[Lapp]

2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09

это, конечно, верно. Но в условии автор ясно сказал: "числа" - и при этом добавил, что нет равных. Следовательно, 09 и 9 не могут встретиться в одном файле.
Но я уже понимаю, что автор на самом деле имел в виду все же телефонные номера, то есть строки символов, что есть абсолютно не числа, на самом-то деле.. Может, он думал, что искажая условие, облегчает задачу?..

Помимо прочего, тема абсолютно не на своем месте. Переношу в Алгоритмы.

[Michael_Rybak]

Проблема с ведущими нулями решается временным дописыванием перед номером одной цифры, равной его длине При этом, сравнивая числа во время сортировки, нужно это учитывать, а как именно - зависит от того, могут ли быть номера "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, для таких ограничений будет летать.

Сообщение отредактировано: Michael_Rybak - 11.12.2006 15:31

[Caranthir]

хм...нечего я не искажал. Файл текстовый-> номера там находящиеся явл строками.
и всё же подскажите пож. как "правильнее" разбить данный файл и в каком формате обрабатывать?

[Caranthir]

Respeсt кто помогал))

[klem4]

Кстати не стоит забывать о том, что после разбиения то придется все это дело "сливать" ... не особо то это бытро будет )

[hiv]

2klem4: При использовании буферного чтения записи во временных файлах (к стати их лучше тоже делать типа longint), это будет существенно быстро.

[Caranthir]

не совсем понял..Поясни пжл как осуществить буферное чтение программно

[Michael_Rybak]

Кстати не стоит забывать о том, что после разбиения то придется все это дело "сливать" ... не особо то это бытро будет )

Это будет не намного медленнее, чем считывать данные из входного файла. В пределах нескольких секунд.

А буферное чтение тут, по-моему, не причем - нам же между собой номера из разных файлов все время сравнивать надо при слиянии.