Помощь - Поиск - Пользователи - Календарь
Полная версия: Оптимизация
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
Страницы: 1, 2
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 (если орентироваться по байтам) файлов и сортировать по-байтам
а потом каждый отсортированный записывать в файл-результат


Цитата(Malice @ 11.12.2006 14:29) *

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


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

Цитата(hiv @ 11.12.2006 14:34) *

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

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


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


А если разбивать на файлы, тогда кол-во чисел в каждом оставит около 10.000, подскажите каккую лучше сортировку применить?
Lapp
Цитата(hiv @ 11.12.2006 15:51) *

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

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

2Lapp: Номера могут быть и разной длины... К стати тоже вопрос - позвоните 09 smile.gif
Caranthir
"для хранения данных в системе может быть выделено до 1 Мб"
hiv
Методы сортировки
Caranthir
А вот если разбивать на 4 файла по 250000, тогда придётся отсортировав каждый, совмещать отсортированные
-> наверное надо разбить на кратные (или 2 или 10)
а, следовательно что может быть быстрее отсортированно и объединено 1000 файлов по 1000 или же 10 по 100000???

Цитата(hiv @ 11.12.2006 15:10) *



Спс конечно за ссылку, но я уже её прочитал)))
там нету на 1000000))
хм...и поразрядная что-то не компил(
Lapp
Цитата(hiv @ 11.12.2006 16:03) *

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

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

Помимо прочего, тема абсолютно не на своем месте. Переношу в Алгоритмы.
Michael_Rybak
Проблема с ведущими нулями решается временным дописыванием перед номером одной цифры, равной его длине smile.gif При этом, сравнивая числа во время сортировки, нужно это учитывать, а как именно - зависит от того, могут ли быть номера "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) ненужность приведенных оценок smile.gif Реально, делай q хоть 1000, хоть 10, для таких ограничений будет летать.
Caranthir
хм...нечего я не искажал. Файл текстовый-> номера там находящиеся явл строками.
и всё же подскажите пож. как "правильнее" разбить данный файл и в каком формате обрабатывать?
Caranthir
Respeсt кто помогал))
klem4
Кстати не стоит забывать о том, что после разбиения то придется все это дело "сливать" ... не особо то это бытро будет smile.gif)
hiv
2klem4: При использовании буферного чтения записи во временных файлах (к стати их лучше тоже делать типа longint), это будет существенно быстро.
Caranthir
не совсем понял..Поясни пжл как осуществить буферное чтение программно
Michael_Rybak
Цитата(klem4 @ 11.12.2006 15:15) *

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


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

А буферное чтение тут, по-моему, не причем - нам же между собой номера из разных файлов все время сравнивать надо при слиянии.
Caranthir
При сливании сравниваются только номера самих файлов.
Возможный вариант:
в каждом файле иммется упорядоченный массив из чисел, таких как <само число>-<номер файла>, а в файл-результат записываются последовательно все числа из файлов +номер файла в порядке прочтения файла
Michael_Rybak
А как ты разбросаешь по файлам, чтобы в первом файле шли подряд с первого по q-й, во втором - с q+1 по 2q-й и так далее?
Caranthir
прочитать весь массив, создать дополнительные файлы и разбрасать по ним числа(в процессе чтения), различающиеся первыми 2 цифрами
а читать с 1 по 2500000 и тд
Michael_Rybak
А если все номера начинаются на одни и те же две цифры? Не, если номера случайные, тогда конечно. Я говорю про решение, работающее в худшем случае.
Caranthir
Хм...Ты прав.
Если одинаковых чисел >250000 брать эти чсла с меньшими разрядами))
Michael_Rybak
Чтобы работало в любом случае, надо

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

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

Спасибо
hiv
Ну хорошо. Можно попробовать обоими способами и сравнить результаты smile.gif
Malice
Вот вам генератор файлов для экспериментов:
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;


hiv
Цитата(Malice @ 12.12.2006 9:39) *
Вот вам генератор файлов для экспериментов:

Входной формат файла - текстовый. Данные не должны повторяться.
Я сам уже нагенерил файло, конечно smile.gif
Malice
Цитата(hiv @ 12.12.2006 10:30) *

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

У меня так и есть, результат в 'test1.txt', .dat промежуточный, там перемешивается все просто..
Altair
ИМХО (по основной задаче)

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

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

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

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

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

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

А такие номера могут существовать?
Если да, дописывать после них 0 а не до!
Я точно знаю, что 100 и 1000000 это один номер (проверял smile.gif )
АТС работает "посимвольно" как только номер совпал - ура, соединили!
Так что 100 и 100xxxx это одно!
hiv
Вот первый вариант.
Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера.
Везде буферный ввод вывод.
Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал).
Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 4,157 сек. Кто быстрее? cool.gif
Максимум выделяемой динамической памяти на данные не превысил 742900 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа - Нажмите для просмотра прикрепленного файла (обновлена)

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

ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak.
Если у кого есть предложения по оптимизации готового кода - буду рад smile.gif
Malice
Цитата(hiv @ 13.12.2006 12:15) *

Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).

Т.е. Все числа выровнены и добиты в начале 0-ми ? А как же пожарные/милиция ? smile.gif Тогда это типизированный файл получается..
hiv
Цитата(Malice @ 13.12.2006 13:29) *

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

Неа no1.gif см. пост7
А на самом деле в телефонии нумерация символьная, и "добивать" слева нулями нельзя - тогда разные номера получаться. 01 и 001 - разные. Да и справа тоже нехорошо. На одной станции можно такой номер прописать 0101, а на другой 01010 - это тоже разное. Так что сказано 7-значка без нулей в начале, так и сделано.
Michael_Rybak
Цитата(hiv @ 13.12.2006 11:15) *

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

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

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


Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь?
hiv
Цитата(Michael_Rybak @ 13.12.2006 17:07) *

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

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

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


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

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

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

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

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

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


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


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
hiv
Цитата(Michael_Rybak @ 13.12.2006 18:05) *
Есть т.н. ковшовая, или поразрядная сортировка...
Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8.
Думаю, что наверняка это будет долго.
Цитата(Michael_Rybak @ 13.12.2006 18:05) *
А вот тут уже моя твоя smile.gif
Что такое битовая сортировка?
Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.


Цитата(Caranthir @ 13.12.2006 22:32) *
...8942629
8961911
8985513
8948864...
Не стесняйся - программу в студию smile.gif
Caranthir
Цитата(hiv @ 14.12.2006 9:54) *

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

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

Могу только на С++ показать, на Pascal пока никак smile.gif
hiv
Цитата(Caranthir @ 14.12.2006 12:41) *
Это я твою смотрел и так отсортировалось_)
Могу только на С++ показать, на Pascal пока никак smile.gif
Так так... smile.gif значит у тебя дубликаты номеров есть... Тогда переделай код так: замени 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


и будет счастье blum.gif
Michael_Rybak
Цитата
Думаю, что наверняка это будет долго.


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

Цитата(hiv @ 14.12.2006 8:54) *

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


Угу, понятно. Прикольно.
klem4
Цитата
Что такое битовая сортировка?


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

unsure.gif
Michael_Rybak
Вот битовой там, если не ошибаюсь, нет.
hiv
Вот второй вариант сортировки (просто супер): blum.gif
1) Читаем исходный файл насколько влазиет в память, потом сортируем и сохраняем во временный файл, следующая итерация чтения исходного файла также сортируется и заносится в следующий временный файл. Т.о. чем меньше памяти на данные мы выделяем, тем больше временных файлов. Сортировка проводится методом "Быстрой сортировки" описанной в FAQ и взятой от туда smile.gif
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 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь smile.gif
Michael_Rybak
Круто, спасибо, что пробуешь smile.gif

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