[с++]внешняя сортировка файла

Чем отличается от обычной сортировки массива?

Было бы ничем, если бы не лексикографически по строкам. Я так понимаю нужно: 0) завести буфер buf[size] 1) пройтись по файлу и посмотреть где начинаются строки( позиции строк) 2) снова пройтись по файлу и поместить туда первые символы строк 3) отсортировать массив из этих символов и записать перестановки символов. 4) Составить композицию перестановок, пройтись по файлу и выполнить перестановки строк в соответствии с полученной композицией перестановок. Я правильно понимаю?

может завести массив строк.

Может нужно сортировать так

вход:

aaa,aca,aba,lfs,abi,abg

выход:

aaa,aba,abg,abi,aca,lfs

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

Нет. Это не вариант. А если файл 2 Гб?

Скажем так. СТЛ незя мне применять, а только <cnamelibstd...> Но это не важно. Гораздо важнее сам алгоритм в мельчайших подробностях. Можно даже на псевдоязыке. Те я не прошу алгоритм, а скорее предложения.

А можно ли еще создавать файлы?

> А если файл 2 Гб?

А если файл 2 GB и все строки в нём односимвольные? Если уж внешнюю делать, так внешнюю. Читать файл при этом вполне можно так, как выше предложено (сколько влезет), не делая индексацию.

Нет. Это былобы слишком просто. А мы не ищем легких путей.

Еще какой вариант.

В любом случае придется прочитать и записать все два гигабайта и еще достаточно много по ним побегать. можно, конечно, написать сложный велосипед, который пытается делать все на диске и экономить память, а можно положиться на операционку и своп. Во втором случае результат будет, как ни странно, не сильно хуже, чем в первом.

И вообще, если вам нужно держать 2ГБ отсортированных строк, то стоит смотреть в сторону баз данных, придуманных специально для этих целей, а не изобретать велосипеды.

> Гораздо важнее сам алгоритм в мельчайших подробностях.

Читаем файл, сколько память позволяет. Сортируем std::sort'ом (можно навелосипедить свой sort, если std прям совсем уж низзя). Выплёвываем в отдельный временный файл. Повторяем, пока не кончится входной файл. Потом открываем все временные файлы, и, читая оттуда по одной строчке, делаем слияние.

Созадвать временные файлы нельзя. Критичны: 1) оперативная память оптимизировать нужно как-то чтобы диск туда-сюда поменьше крутить. те по количеству операций с диском.

1) можно ли предположить, что файл целиком помещается в памяти?

2) что конкретно вас интересует? какой-нибудь алгоритм сортировки массива, или что-то другое?

если временные файлы нельзя создавать - то тогда ищи в сторону inplace external merge, у меня даже была где-то статья, если надо поищу. Но там сложность будет O(N^2) где N - количество отсортированых чанков, если же можно создавать временные файлы то будет O(N). Ну а идея простая : разбиваем файл на N чанков, каждый сортируем, а потом сливаем в один.

В общем я тут покрутил и придумал такую штуку. файл - «abc\nkdaaa\nsdddmmmmk\ndie\n\n»
1) берем первые символы строк и составляем строку (a,k,s,d)
2) Соритируем файл.
2.1)Делаем перестановки пока не отсортируется строка( ну или там выполняем любым известным алгоритмом сортировки, но на выходе должен быть массив перестановок):
1.
(0,1,2,3)
(0,3,2,1)
(a,d,s,k)
2.
(0,3,2,1)
(0,3,1,2)
(a,d,k,s)
Допустим у нас есть функция sort(char* str,vector<int>& perm), тогда в переменной perm должно оказаться :
(0,1,2,3)
(0,3,1,2)
3) Продолжаем начиная со второго символа. в каждой строке. Если в какой-то строке символы закончились , продолжаем с оставшимися строками.
В итоге получится перестановка которая нам нужна для сортировки строк. Нам останется лишь поменять строки в соответствии с перестановкой.

Да ёпт.

Читаешь из файла по строчке же, строишь простое бинарное дерево. Только вместо самих строк туда засовываешь индекс строки в файле. Вернее, не индекс, а offset и длину. Потом обходишь дерево второй раз, читаешь из файла соответствующие куски, записываешь в новый файл. Либо строишь там свой массив перестановок или что хочешь.

Значит так. Такая задача. Наверно я не сформулировал ее достаточно четко 1) Имеется текстовый файл разделенный на строки символом перевода строки - '\n'. 2) Необходимо отсортировать строки в файле в лексикографическом порядке. 3) Нельзя использовать временный файл. 4) Полностью файл загрузить нельзя. 5) Можно использовать буфер размера szbuf.

Разве можно создавать новый файл?

Да можно и статью если можно.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.1155&rep=rep1&typ... вот в этой статье авторы предлагают inplace за линейное время, но я его не пробовал, за квардатичное время - найду чуть позже

> Чем отличается от обычной сортировки массива?

Файл - не массив. Классические сортировки типа Хоара, Шелла и пирамиды тут сливают, потому что время доступа к рандомным элементам совсем уж нелинейное.

Если в файле только аскишные символы, можно будет сделать сортировку подсчётом. Она будет довольно редко дёргать диск. Имхо.

Кстати, есть сортировка слиянием (даже несколько её вариаций), которая задумывалась для сортировки данных на лентах. Насчёт её применимости к HDD - нужно долго думать.

Берем Кнута, том третий (сортировка и поиск), читаем. Берем любой из алгоритмов, не содержащих обратного чтения, реализуем. И что тут еще обсуждать? :-)

> сортировку подсчётом.

ой, фигню сказал. там строки >_<

> Кстати, есть сортировка слиянием (даже несколько её вариаций)

Почти все внешние сортировки имеют требование к диску «не менее 2*N» где N - размер файла, и почти все внешние сортировки базируются на сортировке слиянием - берем файл, делим его на небольшие фрагменты, каждый из которых умещается в памяти, сортируем любым из привычных алгоритмов. Потом каждый из кусков записываем во временный файл, и дальше слиянием. Есть варианты алгоритмов слияния, в которых число файлов заранее задано и ограничено. Второй курс.

> Разве можно создавать новый файл?

Во внешней сортировке не получится без нового файла :-)

> inplace за линейное время

На текстовом файле с неивестной длиной элемента??? Ой-ей, сомневаюсь :-)

почему сомневаетесь?

Может так: Взять первые n-строк из файла. Взять следующую сторку. Если она лучше чем какая-либо то вставить перед ней, а последнюю удалить(хранить можно в л. списке, размер : доступный объём памяти) Если хуже последней, то пропустить. Когда все строки пройдены сливать в новый файл. И так в цикле пока все строки не закончатся. В первый проход записать все длины и позиции строк. Те строки, которые слили в файл в последующей сортировке не участвуют.

+1

В статье написано «Мы используем O(корень квадратный из n) блоков, каждый из которых размера O(корен квадратный из n) ... это позволяет пользователю использовать один блок как внутренний буфер» и так далее. А в тестовом файле, где элемент можеть иметь длину от 0 до сколь-угодно-много символов, получатся плавающие размеры блоков, и запись в середину файла становится невозможна (либо потребует значительных затрат), так что алгоритм надо будет сильно перерабатывать (вплоть до «почти писать с нуля»), как мне кажется. Классические алгоритмы тем и хороши, что им плевать на размер каждого элемента.

Извращение какое :-) Лучше оцените такое: читаем из файла по m строк, каждый блок сортируем и записываем во временный файл, запоминая начало блока. Открываем временный файл в разные FILE* столько раз, сколько получилось блоков, позиционируясь каждый раз в начало очередного блока. Потом обычным слиянием читаем параллельно с нескольки мест файла, как будто это разные фалы (не забывая подсчитать сколько записей из очередного блока считано, и как только блок завершился, закрываем соответствующий ему FILE*) и пишем в оригинальный файл. Итого 2*n чтений, 2*n записей (не лучший вариант), один временный файл, гарантированная работоспособность и простота алгоритма.

классические ТС не подходят, надо без дополнительного файла. Тогда есть гарантированно работающий алгоритм без доп памяти, но за N^2 чтений, что вобщем-то довольно плохо.

Также здесь : http://video.google.com/videoplay?docid=-978892635109400080 есть хорошая видео лекция по внешней сортировке. Правда там только классические алгоритмы (N-way merge) и для inplace они не годятся(хотя лектор при их описании говорит обратное, почему - я так и не понял, может здесь мне объяснят?)

«надо без дополнительного файла», «внешние» и «текстовый файл» воедино не сведутся, увы

Все бы так и делали. Но временный файл создать нельзя. Может ТС создал себе проблему на пустом месте и теперь хочет героически её решить :)

Не выйдет у него ничего. Пусть я буду ведьмой, стервой и вороной - но не выйдет :-)

Check this out http://www.di.unipi.it/~grossi/PAPERS/icalp05.pdf

Внешняя сортировка. Данные не помещаются в памяти. Алгоритм хорош для абстрактных коней в RAM, а у нас дорогие read/write (доступ к элементу), и безумно дорогой seek :-(

Бинарное дерево, offset + hash Сортировать по хэшам -> список перестановок -> переставляем элементы Хэшировать вроде еще никто не предлагал:))

Имхо заммапить файл в память и сортировать квиксортом.

Керниган и Ричи -> готовый пример по сортировке файла по строкам -> переписываем на плюсы -> готово. А если хочется попроще - то сделать как предлагает Legioner (все равно редко встречаются гигабайтные текстовые файлы). Можно, кстати не ммапить, а кинуть в разделяемую память, отсортировать, затем скопировать данные обратно в файл - тогда будет меньше риск повреждения файла в случае убиения программы.

Читайте сообщения ТС.

Значит так. Такая задача. Наверно я не сформулировал ее достаточно четко 1) Имеется текстовый файл разделенный на строки символом перевода строки - '\n'. 2) Необходимо отсортировать строки в файле в лексикографическом порядке. 3) Нельзя использовать временный файл. 4) Полностью файл загрузить нельзя. 5) Можно использовать буфер размера szbuf.

Сортировка в памяти не проблема.

так как мы не можем предсказать, сколько строк войдет в буффер — и, в частности, войдет ли в него хотя бы одна строка — задача превращается во что-то типа: «отсортировать много строк, лежащих одна за другой, не используя вообще никакой внешней памяти и желательно с минимальным количеством возвратов и перемещений данных».

В лоб это решается при помощи Insertion Sort прямо по файлу, с пробегом внутреннего цикла от начала данных вперед, а не от текущей позиции назад, и с хитрым алгоритмом перестановки блоков, использующим буффер не более чем в szbuf байт.

Сортировка в памяти не проблема.

А как вы себе можете представить сортировку файла без загрузки его в память и без промежуточных файлов? В начало или середину файла невозможно что-то дописать без переписывания всего остального. Самый быстрый способ - скопировать его целиком в память и отсортировать. Медленный - использовать mmap. При использовании промежуточных файлов сортировка будет длиться очень долго (т.к. придется переписывать один и тот же файл огромное количество раз).

>Нет. Это не вариант. А если файл 2 Гб?

1. x86_64

2. use sort. Спрашивающий, очевидно, пишет не замену стандартному sort'у а лабораторную работу.

> Спрашивающий, очевидно, пишет не замену стандартному sort'у а лабораторную работу

Я придумала бредовую идею. Ведь никто не сказал, что нельзя изменять размер файла в процессе работы, верно? Тогда можно просто дописывать в конец оригинального файла (в результате в процессе работы файл вырастет до удвоенного размера), и использовать эту дописанную область вместо временного файла, а в самом конце вернуться в начало файла, сделать seek на ту точку, где заканчивался файл, и устроить ему truncate! Поскольку цель ведь получить отсортированные данные в оригинальном файле, этот оригинал доступен нам по записи, так что никаких технических проблем тут вроде бы не будет :-)