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

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

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

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

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

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

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

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

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

Мысли:

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




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



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

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

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


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

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

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

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

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

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

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




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

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

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

Проблема с ведущими нулями решается временным дописыванием перед номером одной цифры, равной его длине При этом, сравнивая числа во время сортировки, нужно это учитывать, а как именно - зависит от того, могут ли быть номера "09" и "0009", и если да, то как их сравнивать.

А дальше -



Даже если группировать по 100 000 лонгинтов (тогда и с кодом вместе легко впишемся в 1 МБ), получится 10 групп. Сортировка каждой из них в ОП - порядка 100 000 * log 100 000, слияние в один файл - 1 000 000 * 10 (можно и 1 000 000 * log 10, но зачем?). Должно работать за несколько секунд.

Кстати, скорость может еще существенно зависеть от ввода-вывода. Например, в С++ ввод/вывод такого объема данных с помощью fstream (а не file) займет больше времени, чем собственно сортировка.



Если мы разбиваем 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, для таких ограничений будет летать.

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

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

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

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

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

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

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

При сливании сравниваются только номера самих файлов.
Возможный вариант:
в каждом файле иммется упорядоченный массив из чисел, таких как <само число>-<номер файла>, а в файл-результат записываются последовательно все числа из файлов +номер файла в порядке прочтения файла

А как ты разбросаешь по файлам, чтобы в первом файле шли подряд с первого по q-й, во втором - с q+1 по 2q-й и так далее?

прочитать весь массив, создать дополнительные файлы и разбрасать по ним числа(в процессе чтения), различающиеся первыми 2 цифрами
а читать с 1 по 2500000 и тд

А если все номера начинаются на одни и те же две цифры? Не, если номера случайные, тогда конечно. Я говорю про решение, работающее в худшем случае.

Хм...Ты прав.
Если одинаковых чисел >250000 брать эти чсла с меньшими разрядами))

Чтобы работало в любом случае, надо

1) разбить просто подряд: первые q номеров - в первую группу, следующие q - во вторую и т.д.
2) по очереди каждую группу отсортировать и записать в файл
3) идти по файлам одновременно, выбирая на каждом шагу наименьший из текущих номеров в файлах

Это похоже на сортировку слияниями (точнее, это и есть сортировка слияниями), только сливаем мы не два списка, а больше.

Интересно... попробую

Спасибо

Ну хорошо. Можно попробовать обоими способами и сравнить результаты

Вот вам генератор файлов для экспериментов:

procedure generate;
var f:file of longint;
f2:text;
i,q,w,e,r:longint;
s:string;
function rnd(i:longint):longint;
var x:longint;
begin x:=longint(random($ffff))+longint(random($ff))*$ffff; rnd:=x mod i; end;
begin
assign (f,'test1.dat'); rewrite(f);
randomize;
for i:=1 to 1000000 do write(f,i);
close(f); reset(f);
for i:=0 to 1000000-1 do begin
w:=rnd(1000000);
seek(f,i); read(f,e); seek(f,w); read(f,r);
seek(f,i); write(f,r); seek(f,w); write(f,e);
end;
reset(f);
assign (f2,'test1.txt'); rewrite(f2);
repeat
read(f,i);
str(i,s);
writeln(f2,s);
until eof (f);
close(f); close(f2);
writeln(1);
close(f);
end;

Входной формат файла - текстовый. Данные не должны повторяться.
Я сам уже нагенерил файло, конечно

У меня так и есть, результат в 'test1.txt', .dat промежуточный, там перемешивается все просто..

ИМХО (по основной задаче)

Портируем текстовый файл в типизированный из longint'ов. (10^7 вместит), причем "на лету".
(в памяти есть longint переменная, куда суммируем каждый раз текущую цифру * на 10 в соотв. степени, и обнуляем этот long при переходе через разделитель, записывая его при этом в long file)
Никаких сортировок не производим!
В момент сбрасывания очередного longint в типизированный файл, скидываем его, позиционировав указатель (seek) на его номер! (для этого заранее стоит выделить место под файл, это - 1 действие)
Далее просто тупо копируем типизированный файл в текстовый, причем если место пусто, то пропускаем номер.

Данный метод позволит получить результат без сортировки вообще.

Метод применяют при ограниченных вычислительных способностях и больших объемах памяти (в нашем случае внешняя память доступна)

Кратко я показал данный алгоритм на схеме:
Нажмите для просмотра прикрепленного файла

Круто, риспект

Только опять непонятно, как быть с номерами "009" и "000009"

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

А такие номера могут существовать?
Если да, дописывать после них 0 а не до!
Я точно знаю, что 100 и 1000000 это один номер (проверял )
АТС работает "посимвольно" как только номер совпал - ура, соединили!
Так что 100 и 100xxxx это одно!

Вот первый вариант.
Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера.
Везде буферный ввод вывод.
Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал).
Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 4,157 сек. Кто быстрее?
Максимум выделяемой динамической памяти на данные не превысил 742900 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Нажмите для просмотра прикрепленного файла (обновлена)

Параметры машины:
ОС - WinXP
Процессор - Pentium4 1.8ГГц
ОЗУ - 512 Мб
Винт - 40Гб 7200об/мин

ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak.
Если у кого есть предложения по оптимизации готового кода - буду рад

Т.е. Все числа выровнены и добиты в начале 0-ми ? А как же пожарные/милиция ? Тогда это типизированный файл получается..

Неа см. пост7
А на самом деле в телефонии нумерация символьная, и "добивать" слева нулями нельзя - тогда разные номера получаться. 01 и 001 - разные. Да и справа тоже нехорошо. На одной станции можно такой номер прописать 0101, а на другой 01010 - это тоже разное. Так что сказано 7-значка без нулей в начале, так и сделано.

Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь?

Поподробнее, а то твоя моя не понимай...

Подумал на счет твоих постов 14 и 20 - с битовой сортировкой не получится:
7-мизначка = 9 000 000 номеров
делим на 8 бит = 1125000 байт
что больше 1Мбайта
А использовать пузырек - не поможет (по объему около 40 сек выйдет).

Есть т.н. ковшовая, или поразрядная сортировка.
Ковши = файлы.

Есть 1 исходный ковш (большой), и 10 малых, пронумерованных от 0 до 9.

Идем по большому ковшу, разбрасываем по малым все числа, в зависимости от последней цифры (младшего разряда).

Потом сливаем малые ковши в порядке возрастания в большой ковш.

Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8.



А вот тут уже моя твоя
Что такое битовая сортировка?

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


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

Думаю, что наверняка это будет долго.
Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.


Не стесняйся - программу в студию

Это я твою смотрел и так отсортировалось_)

Могу только на С++ показать, на Pascal пока никак

Так так... значит у тебя дубликаты номеров есть... Тогда переделай код так: замени count на j

    // запись результата сортировки в итоговый файл
    ps:=pbuff;
    pe:=pbuff+buff_count;
    for k:=0 to count-1 do
    begin

на

    // запись результата сортировки в итоговый файл
    ps:=pbuff;
    pe:=pbuff+buff_count;
    for k:=0 to j-1 do
    begin

и будет счастье

А я думаю что не будет



Угу, понятно. Прикольно.

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

Вот битовой там, если не ошибаюсь, нет.

Вот второй вариант сортировки (просто супер):
1) Читаем исходный файл насколько влазиет в память, потом сортируем и сохраняем во временный файл, следующая итерация чтения исходного файла также сортируется и заносится в следующий временный файл. Т.о. чем меньше памяти на данные мы выделяем, тем больше временных файлов. Сортировка проводится методом "Быстрой сортировки" описанной в FAQ и взятой от туда
2) Сливаем все временные файлы в итоговый, каждый раз выбирая минимальное значение среди прочтенных из всех временных файлов.
Также везде буферный ввод вывод.
Спасибо Volvo за FAQ и Michael_Rybak за метод сортировки слияниями файлов. См. пост 26

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,421 сек. Кто еще быстрее? cool.gif
Максимум выделяемой динамической памяти на данные не превысил 970372 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Нажмите для просмотра прикрепленного файла
Параметры машины: теже

ЗЫ: К стати обновил первую версию - теперь повторяющихся номеров в итоговом файле не будет, даже если они были в исходном. См. пост 35.
Во втором методе повторяющиеся номера не удаляются.
В принципе это то что говорил Altair в посте 32, только индексом является просто 1 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь

Круто, спасибо, что пробуешь

У меня еще вот какая идея возникла: можно твою битовую модифицировать, чтобы в память влезло. У тебя получилось (10^7)/8=1 250 000, что немного больше позволенного. Тогда можно пройтись по входному файлу два раза: первый раз обрабатывая только числа, меньшие 10^7/2, а остальные пропуская, а второй раз - наоборот; памяти тогда понадобится в 2 раза меньше.

2Michael_Rybak
Стыдно что сам до этого не додумался... Конечно попробую сделать этот вариант. Ну и ковшовую тоже попробуем