花弁

Доброкодер 03 December 2012 (Mon) 00:55 No.27674

Добрач, у меня задача на Паскале (Борланд или Фришечка). Нужно отсортировать числа в вводном файл и сохранить в другой файл. Количество чисел не ограничено. Я правильно понял, что это можно сделать только заведя промежуточный файл и проводить сортировку переключаясь между двумя файлами? Или есть какой-то более удобный способ?
И какой посоветуешь алгоритм сортировки в данном случае?

Доброкодер 03 December 2012 (Mon) 02:34 No.27675

>>27674
Без дополнительного файла можно сделать сортировку вставками не напрягаясь.

> Борланд или Фришечка

Память ограничена сектором 64к?
Еще предположение: может то, что количество чисел не ограничено, относится к алгоритму? Просто оно хоть размером диска, да ограничено.
В общем случае для больших объемов данных можно воспользоваться B-деревьями enwiki://B-tree

>>	Доброкодер 03 December 2012 (Mon) 03:50 No.27677 >>27674 Ну тык ж, ограничь их. И нагло утверждай, что они не ограничены (всё равно это не проверить).

>>	Доброкодер 03 December 2012 (Mon) 06:11 No.27683 >>27675 Может просто имеется ввиду, что алгоритм должен уметь работать с любым количеством чисел.

>>	Доброкодер 03 December 2012 (Mon) 12:56 No.27687 Для файлов вроде как удачной считается natural merge - работает за nlogn и не подразумевает перескоков по индексу, т.н. ленточная.

Доброкодер 03 December 2012 (Mon) 16:19 No.27688

>>27674

> Я правильно понял, что это можно сделать только заведя промежуточный файл и проводить сортировку переключаясь между двумя файлами?

Нет. Можно, например, пройти по файлу N раз, каждый раз находя минимальное число и записывая в выходной файл, а в памяти держать минимальное число с прошлой итерации.

> Количество чисел не ограничено.

Наверняка это означает, что нельзя в программе заводить массив фиксированного размера, в который читать числа из файла. С несколько меньшей вероятностью это означает, что читать весь файл в память вообще нельзя.

>>	Доброкодер 03 December 2012 (Mon) 16:22 No.27689 >>27688 > Нет. Можно, например, пройти по файлу N раз, каждый раз находя минимальное число и записывая в выходной файл, а в памяти держать минимальное число с прошлой итерации. Сортировать файлы за О(N^2)?! Это же несерьёзно!

Доброкодер 03 December 2012 (Mon) 16:29 No.27690

>>27688

> С несколько меньшей вероятностью это означает, что читать весь файл в память вообще нельзя.

Алсо, это тоже звучит несерьёзно на мой взгляд. Файлы они большие же. Я думаю, нужно городить сортировку, чтобы информация из файла черпалась буферами, то есть частями определённого размера. Весь файл же всю оперативу съест. Фильмы вон вообще больше 4ГБ весят нередко.

>>	Доброкодер 03 December 2012 (Mon) 19:30 No.27691 >>27689 Зато памяти нужно 64 байта всего.

>>	Доброкодер 03 December 2012 (Mon) 19:35 No.27692 >>27690 Ну хорошо. Есть блю-рей рип на 12 гигов. Режем на куски по 4 байта - получается 3 миллиарда чисел. Допустим, в одном буфере 1024 числа. Вот ты черпаешь инфу буферами. Получилось 3 миллиона буферов отсортированных чисел. Дальше что?

>>	Доброкодер 03 December 2012 (Mon) 19:40 No.27695 >>27692 Буфер-то всегда один. Считал, обработал, очистил память.

>>	Доброкодер 03 December 2012 (Mon) 19:42 No.27696 >>27695 Я у тебя спрашиваю, как ты 3 миллиона буферов собираешься объединить в отсортированный массив из 4-х миллиардов чисел и записать в выходной файл, если в памяти будет только 1024 элемента?

Доброкодер 03 December 2012 (Mon) 19:44 No.27697

>>27692
Я не говорю сортировать буферы, я говорю делать сортировку, которая использует считывание буферами. Хотя не знаю, стоит ли буферами... Что-то я засомневался. В любом случае незачем весь файл в оперативу помещать. Natural merge так или иначе можно использовать.

>>	Доброкодер 03 December 2012 (Mon) 19:58 No.27698 >>27696 Любой внешней сортировкой.

Доброкодер 03 December 2012 (Mon) 20:01 No.27699

File: NMSPic_2.jpg
Jpg, 141.76 KB, 349×784 - Click the image to expand

>>27697

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

Это может ускорить ввод-вывод, но на сложности алгоритма точно не скажется тогда.

> В любом случае незачем весь файл в оперативу помещать.

Это подразумевалось.

> Natural merge так или иначе можно использовать.

Вот, смотри какую классную картинку я нашёл в гугле. Это пример натуральной сортировки слиянием. А теперь объясни мне, как ты собираешься ею воспользоваться при условии, что не все сортируемые числа могут быть одновременно загружены в память, а также без создания промежуточных файлов (как просил ОП).

Доброкодер 03 December 2012 (Mon) 20:08 No.27701

>>27699

> а также без создания промежуточных файлов (как просил ОП).

ОП этого прямо не просил. Он дал туманный реквест и я решил, что лучше советовать самое подходящее с моей точки зрения. Я подразумевал именно что промежуточные файлы. Они же лечше чем съесть всю оперативу или делать за N^2, так?

Доброкодер 03 December 2012 (Mon) 20:19 No.27702

>>27701
Ну а я на вопрос опа "можно ли сделать без промежуточных файлов" сказал "да" и подтвердил концептом самого простого из подходящих вариантов (и, возможно, единственного, хехе).

Кстати, если оп не в состоянии самостоятельно нагуглить решение своим студентопроблемам, то программы с O(N^2) будут выглядеть менее подозрительно для преподавателя. Я, кстати, одно время вёл лабораторки по программированию и когда некто, кого ты считаешь тупым как пробка лентяем, приносит тебе императивную дристню с хитровыебанными оптимизациями, то становится очевидно, что писал он её не сам. Несколько вопросов по устройству коду и товарищ идёт нахуй. Такие дела.

>>	Доброкодер 03 December 2012 (Mon) 20:31 No.27703 >>27702 В нашем универе или ты приносишь всё чтобы хитровыебано было, так как должно быть, или идёшь нахуй и это правильно.

Доброкодер 03 December 2012 (Mon) 21:58 No.27705

Спасибо за ответы, няши. В общем, делаю с промежуточными файлами. Деревья не годятся, так как и там есть ограничения на количество элементов.
Осваиваю сортировку слиянием, так как, вроде, во-первых, она быстрее и удобнее, во-вторых, я её не знаю, надо бы научится.
>>27703
У нас надо чтобы хотя бы чисто теоретически работало (факториала 20000 от моей предыдущей программки так и не дождались, но посмотрели, что на меньших числах работает хорошо и код годный, и зачли), чтобы код был по-человечески оформлен, с лесенкой, комментариями и осмысленными именами переменных и, чтобы, конечно, мы сами могли разобраться в собственном коде.

Доброкодер 03 December 2012 (Mon) 23:10 No.27708

Тогда, заодно вопрос по сортировке слиянием. В чём её суть я понял, теперь смотрю пример реализации в викиучебнике: http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8[...]B2.29
Зачем нужно

If (kol div 2) mod s<>0 then

               begin
                 tmp:=kol div 2;
                 While tmp mod s<>0 do
                   begin
                     Read(f,a1);
                     Write(f1,a1,' ');
                     inc(tmp);
                   End;
               End;

Почему необходимо, чтобы количество чисел в f1 делилось нацело на s?

>>	Доброкодер 03 December 2012 (Mon) 23:17 No.27709 File: Capture.PNG Png, 46.75 KB, 487×1105 - Click the image to expand >>27708 О мой бог. Чем с этой императивной дристнёй разбираться, лучше уж нагуглить описание на естественном языке.

>>	Доброкодер 04 December 2012 (Tue) 06:10 No.27718 >>27709 > дристнёй Два чаю. Автор этого высера явно не может в декомпозицию.

>>	Доброкодер 04 December 2012 (Tue) 14:45 No.27728 >>27709 > лучше уж нагуглить описание на естественном языке. Можно еще танец посмотреть, лол YouTube: Merge-sort with Transylvanian-saxon (German) folk dance

>>	Доброкодер 04 December 2012 (Tue) 14:48 No.27729 И еще всякие визуализации есть http://rain.ifmo.ru/cat/view.php/vis/sorts

Доброкодер 04 December 2012 (Tue) 15:13 No.27731

>>27690

> Весь файл же всю оперативу съест.

Можно отобразить файл в память через http://www.kernel.org/doc/man-pages/online/pages/man2/mmap.2.html или http://msdn.microsoft.com/en-us/library/aa366537.aspx в зависимости от используемой ОС
Это можно из паскаля вызывать

>>	Доброкодер 04 December 2012 (Tue) 15:59 No.27733 >>27731 Это для чего? Как поменяется суть?

>>	Доброкодер 04 December 2012 (Tue) 16:21 No.27734 >>27733 > Это для чего? Чтоб не записывать весь файл в оперативку > Как поменяется суть? Файл будет читаться с жесткого диска по мере надобности

>>	Доброкодер 05 December 2012 (Wed) 12:45 No.27772 >>27718 Будто императивная дрисня может в декомпозицию.

>>	Доброкодер 05 December 2012 (Wed) 13:01 No.27773 >>27772 вообще может. На этой штуке можно писать в функциональном стиле даже

>>	Доброкодер 05 December 2012 (Wed) 21:10 No.27787 >>27718 > Автор этого высера явно не может в декомпозицию. Да это же просто обфусцированный код.

>>	Доброкодер 06 December 2012 (Thu) 00:55 No.27790 File: 1339473920753.png Png, 328.44 KB, 631×543 - Click the image to expand >>27674 Какой еще промежуточный файл? Уж не упорот ли ты? Сортированный список запили и добавляй в него. Заполнишь почти за n и выльешь его в файл за n.

>>	Доброкодер 06 December 2012 (Thu) 01:14 No.27792 >>27790 Предположим, у нас есть файл на 160ГБ (массив на 40 миллиардов интов) и 4ГБ оперативной памяти.

>>	Доброкодер 06 December 2012 (Thu) 01:14 No.27793 >>27790 > количество чисел не ограничено

>>	Доброкодер 06 December 2012 (Thu) 18:12 No.27796 >>27792 Подключить кондуиты, делов-то.

Доброкодер 06 December 2012 (Thu) 20:58 No.27807

File: 1345801940849.jpg
Jpg, 87.79 KB, 1024×576

File: Capture.PNG
Png, 1.04 KB, 132×22

>>27792
Если ты ОП, то поясни за область науки за которую ты так впрягаешься. А еще за то, почему ты не можешь заюзать местный суперкомпьютер минут на 20.

>>27793
Нужно понимать, что надпись "не ограничено" в формулировке вообще ничего не значит без уточнения ибо суть может варьироваться от "не создавать массив на n элементов и применять пузырек" до "подсчитать число атомов во вселенной"

С другой стороны если тут имеет место это ваше олимпиадное погромирование, то флаг в руки.