2

Имеется файл, скажем, размеров в 16 Гб, содержащий double через пробелы.

Простое применение внешней сортировки:

  1. Разбить файл на куски, которые помещаются в памяти, отсортировать их и обратно записать;
  2. Применить k-путевое слияние для этих отсортированных кусков и записывать во второй файл.
  3. Удалить первый файл и переименовать второй.

Проблем нет, если у пользователя есть свободное место (в данном случае, 16 Гб).

Как можно модифицировать алгоритм так, чтобы дополнительное место не тратилось?

На ум приходит лишь небольшая оптимизация: создать файл размером в 1 кусок, записывать в него. При его заполнении удалить использованные элементы из исходного файла, ну и повторить алгоритм.

Поиск в Google постоянно выдаёт не то, что нужно. (Возможно я плохо ищу). Не могли бы подсказать алгоритм или хотя бы литературу?

Ildar Akhmetov
  • 372
  • 1
  • 14

1 Answers1

2

Можно попробовать следующий трюк.

Пусть у юзера есть ещё X свободного места. При слиянии двух файлов пишем результат в новый файл на свободное место, пока оно не закончится. Затем обрезаем данные в сливаемых файлах в начале, так, чтобы выкинуть уже слитые данные, у нас освобождается место. Процесс повторяем.

Для того, чтобы эффективно отрезать данные в начале файла, можно, по идее, заводить не 16 файлов по гигабайту, а один файл, и в переменных запоминать каждый раз начало и конец данных того или иного куска. Таким образом обрезка начала файла сведётся лишь к увеличению числа, представляющего собой начало данного логического куска в общем файле. (При этом данные файла превращается в список кусков, что тоже требует некоторого расхода памяти: один номер следующего блока в каждом блоке.)

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

VladD
  • 206,799
  • Перечитайте, пожалуйста, условие. Я не создаю дополнительно 16 файлов, а всего лишь один дополнительный файл и то уже при k-путевом слиянии. Отрезание именно по принципу начала и конца куска идёт. Разница в том, что я написал что размер равен первоначальному файлу или куску, а вы написали Х, где Х - свободное место у юзера. В принципе это самый логичный подход. А возможно ли без дополнительной памяти на диске? - Вот в этом главный вопрос. – Ildar Akhmetov Nov 12 '15 at 21:07
  • @ИльдарАхметов: Ну, я про это пишу тоже. После того, как вы «слили» кусок информации в памяти, у вас освободилось место, и вы можете сбросить память на диск. – VladD Nov 12 '15 at 21:20
  • @ИльдарАхметов: при этом вам не нужна дополнительная дисковая память. – VladD Nov 12 '15 at 21:22
  • Всё, я теперь понял как. Ответ засчитан. – Ildar Akhmetov Nov 12 '15 at 21:24
  • @ИльдарАхметов: не торопитесь, там ещё будут тонкости в имплементации: нужна будет структура данных, чтобы описывать куски. Или можно просто сдвигать данные, чтобы не заморачиваться. – VladD Nov 12 '15 at 21:25
  • Если делать кусками, вам может понадобиться ручная «дефрагментация» информации. Так что наверное проще будет таки сдвигать. – VladD Nov 12 '15 at 21:26
  • Отрезать от файла куски лучше с конца, тогда не придётся переписывать весь файл, а достаточно просто вызвать функцию ftruncate. – sercxjo Nov 14 '15 at 19:55
  • @sercxjo: К сожалению, не получится. Если мы сливаем с начала данных, и отрезать надо от начала. А если мы сливаем с конца, то нам при добавлении данных новых данных в слитый файл придётся дописывать в начало, то есть снова переписывать данные. Таким образом, без многократного переписывания мы, кажется, не обойдёмся. – VladD Nov 14 '15 at 20:05
  • Интересно, но... (@ИльдарАхметов, imho Вам тоже будет любопытно). Мы тут уже когда-то рассматривали похожую задачку , только с сортировкой в ОЗУ. Результаты слияния по возможности тоже "откачивались" поверх уже "слитых" данных. В моих экспериментах под дополнительную память при слиянии (с учетом разумного фрагментирования) уходило порядка 10% массива. Т.е. для 16G понадобится порядка 1.5G оперативки (или этот процесс будет существенно хуже N log N) – avp Nov 14 '15 at 21:03
  • @avp: Если есть дополнительная память, надо, конечно, использовать её насколько возможно. Но по условию её нету :( – VladD Nov 14 '15 at 21:04
  • Вообще без нее ничего не выйдет. – avp Nov 14 '15 at 21:05
  • @avp: Я имел в виду дисковую, внешнюю. // Пошёл поставить плюс обсуждению про Yamsort, и обнаружил, что он там уже стоит. – VladD Nov 14 '15 at 21:07
  • Можно уменьшить размер фрагментов, но и при их размере sqrt(N) скорость несколько хуже N log N (но лучше N (log N)^2 (а вот такая сортировка слиянием (symmsort) дополнительной памяти кроме стека для рекурсии не требует)) – avp Nov 14 '15 at 21:11