О сортировке больших текстовых файлов

На сайте одной из харьковских фирм, занимающихся аутсорсингом, опубликована задача такого содержания:

Необходимо написать алгоритм, который бы смог отсортировать строки в файле большого размера (от 2-х до 4-х Gigabytes). Результатом выполнения должен быть другой файл.

Большинству из нас, скорее всего, никогда не понадобится её решать в своей деятельности, но определенный практический интерес она представляет. Поскольку задача поставлена крайне неопределенно (не дай вам бог иметь начальника, формулирующего технические задания в таком стиле), некоторые детали проясняются только из обсуждения (http://www.fulcrumweb.com.ua/archives/1020). Например, упоминается, что в файле могут быть строки огромного размера — даже порядка размера всего файла. Именно это условие и вызвало мой интерес к задаче — как отсортировать строки, которые невозможно сравнивать целиком?

В этой заметке изложены  подробности по возможному подходу к решению этой задачи (придуманному мною, хотя на авторство в первой инстанции не претендую — всё достаточно элементарно), с иллюстрациями исходным кодом, и практическим тестированием получившейся реализации.

Откуда (и куда) ноги растут

Сортировка больших файлов (т.е. таких, что их размер значительно превышает доступную оперативную память), не является редкой задачей. Например, любая СУБД с ней справляется, и алгоритмы внешней сортировки известны и успешно применяются. Но, есть одно «но»: в виденных мною реализациях алгоритмов внешней сортировки предполагается известным (и сравнительно небольшим) максимальный размер сортируемых объектов, что в нашем случае совсем не так.

И что же делать?

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

Чтобы воплотить нашу простую идею, мы будем сортировать все строки сразу, но сравнивая их не целиком, а небольшими частями —  по нескольку символов за раз. Сортировка будет закончена, когда мы доберемся до концов самых длинных строк. Вкратце, последовательность действий такая:

1. Исследовать исходный файл, составляя его «карту»: найти смещения начала каждой строки и её длину. В итоге мы получим последовательность объектов в оперативной памяти, содержащих эти сведения и расположенных в том же порядке, что и строки в исходном файле. Это очень важно, поскольку при дальнейших обращениях к файлу мы сможем обеспечить последовательное чтение данных с диска (т.е. сэкономим время и ресурс накопителя).
Также создаем «список сортировки», в котором храним только указатели на объекты «карты файла». Сортировать будем именно этот список, не изменяя порядок объектов в «карте».

2. Считать для каждой строки по нескольку символов. Кладем их в буферы сравнения ранее созданных объектов с информацией о строках. Чем больше символов сможем обработать за раз, тем меньше придется выполнить циклов сортировки, но тем больше расход памяти. Т.е. оптимальный размер буфера сравнения выбираем как компромисс с учетом этих факторов.

3.  Сортируем указатели в списке сортировки, используя для сравнения части строк, полученные в п.2. Запоминаем результат сравнения в специальном поле наших объектов, поскольку в дальнейшем мы должны сравнивать лишь те строки, начальные фрагменты которых оказались одинаковыми.

4. До тех пор, пока остаются строки, еще не считанные до конца, повторяем пункты 2-3-4.

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

А поконкретнее… 

Как известно, на словах можно много чего умного и хорошего «сделать» (живущие на Украине не-аполитичные дамы и господа меня должны понять), а на практике — ничего. Собственно говоря, авторы задачи (по устному признанию одного из сотрудников фирмы), не удосужились её решить самостоятельно, и, к сожалению, пока сравнивать не с чем. Справедливости ради, тамошние ведущие специалисты несомненно обладают профессиональным опытом гораздо больше моего (общаться с ними — одно удовольствие),  это дает надежду, что кто-нибудь из них выделит 2-3 часа, чтобы сделать референсную реализацию.

Если Вы придумаете собственную реализацию (и/или алгоритм) для этой задачки, не сочтите за труд поставить меня в известность — интересно полюбоваться (пишите на мыло -jet-[at]ukr.net) .

Для привязки к реальности: всё далее представленное выполнялось на ноуте с двухъядерным Интелом в 5870 попугайчиков (однако, двухъядерность его нигде не использована) и двумя гигами оперативы, под управлением Виндоус 7 х64, среда разработки — MS Visual Studio 2008.

Для проверки состоятельности изложенных выше идей, было «состряпано» тестовое приложение. Для хранения карты файла и списка сортировки в нем использованы контейнеры STL vector и list. Сортировка выполняется методом list::sort(). Однако, накладные расходы «на содержание» контейнера list слишком велики (особенно в 64-разрядной версии, где каждый указатель требует по 8 байт памяти для хранения), поэтому следующим шагом стала минимальная оптимизация, связанная с отказом от контейнеров СТЛ. Вы можете скачать, изучить и оптимизировать по собственному усмотрению обе версии:
ExtSortingSTL и
ExtSorting (no STL).

Тесты и результаты 

При попытке обработать файл размером 3 ГБ х32 СТЛ версия самоустранилась, поскольку съела всю доступную память из кучи (около 2 ГБ), а версия без СТЛ х64 успешно отработала первый цикл сортировки, занимая в памяти примерно 1,5 ГБ. На этом мне стало жалко жесткий диск любимого ноутбука, и я решил, что полномасштабное тестирование можно оставить на усмотрение тех, кому оно действительно понадобится. Кстати, рекомендую на досуге прочесть довольно интересную статью об экспериментах с выделением больших объемов памяти в Виндоус.

Все далее представленные тесты выполнены на одном и том же исходном файле размером около 100 МБ (107 953 781 байт). Файл сгенерирован из повторяющихся в случайном порядке строк, имеющих различные числовые окончания, с помощью самой тестовой программы. В тестовом файле оказалось 1 620 275 строк, таким образом средняя длина строки составила 66,6 символа (не так уж и много, учитывая, что наш алгоритм может работать со строками длиной в миллионы раз больше), то есть на входе  имеем файл с вполне типичными для реальной жизни строками. Длина буфера сортировки равна 16 символам.

Сравним результаты по 4 вариантам программы: с применением контейнеров STL и без них (с qsort и проверенным в многочисленных боях за байты и мегагерцы менеджером памяти собственного приготовления) в 32- и 64-разрядном исполнении. Сборка проектов выполнялась с оптимизацией «Релиз», предоставляемой профилем VS по умолчанию.

Ниже представлена сводная таблица с основными результатами.

STL list::sort() x32 STL list::sort()  x64 qsort x32 qsort x64
Память, кБ

85  284

97  484

53  356

60  800

Время, мс

120  136

96  705

114  240

86  986

Из практически полезных выводов, видим, что 64-разрядные версии выполняются заметно быстрее (на 24% для list::sort() и 31%  для qsort()), потребляя немногим больше памяти (на 14% ). Для любой из тестовых конфигураций объем используемой памяти не превысил объем исходного файла (хотя STL версия вплотную подобралась к этому пределу).

Очевидно, для решения реальных задач по сортировке огромных массивов данных следует использовать только 64-разрядные ОС и 64-разрядные приложения: помимо заметной разницы в быстродействии, в них нету ограничения на 2 ГБ адресного пространства для х86 приложения.

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

Тестирование. Дополнение (от 3 марта 2012) 

Поскольку тестирование «на глаз» правильности сортировки больших строк весьма сомнительно, для автоматизации этого процесса написал специальную утилиту (Embarcadero RS / C++).
Скачать вместе с исходниками можно по этой ссылке.

Она позволяет создавать неотсортированные тестовые файлы — со строками любой длины (длина по равномерному распределению в заданных пределах от минимальной до максимальной) и любого размера. Исходные наборы строк можете изменять по собственному усмотрению — достаточно изменить содержимое файла Strings.txt в папке с программой.

Также с её помощью можно проверить корректность сортировки по следующим признакам:

1. Размеры исходного файла и файла-результата должны совпадать;
2. Порядок строк в отсортированном файле должен быть правильным. Выясняется построчным сравнением. Каждая следующая строка должна быть больше или равна предыдущей;
3. Контрольная сумма всех символов  в исходном файле должна быть равна контрольной сумме в отсортированном файле — это значит, что всё содержимое исходного файла находится в отсортированном.

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

Критика. Реализация классического алгоритма внешней сортировки. Дополнение (от 13 марта 2012)

Дабы обеспечить дополнительную ясность и полноту изложения, приведу цитату из обсуждения, содержащую критику предложенного мною алгоритма. Человек, её высказавший, имеет полное право критиковать (хотя в части последовательного чтения он не врубился), поскольку сам реализовал алгоритм внешней сортировки (и с позволения автора можно скачать исходник). Стиль, содержание и чувство юмора автора данного критического опуса оставлены без изменений. 🙂

 Trusov Denis says:
March 2, 2012 в 03:48

Йо-хо-хо… Ещё один кандидат на флеш-премию. Исходники не смотрел, но пару слов скажу. Если судить по устному описанию алгоритма — реализована следующая незатейливая схема: получить массив смещений в файле с длинами строк и упорядочить его, а строки считывать во время сравнения буфферизируя по N байт (в данном случае по 16, запомним это число). Этот алгоритм — первое, что приходит в голову, когда понимаешь, что в лоб задачу не решить. А задача крайне проста — упорядочить массив строк, но массив не простой, а очень большой… Увы, печалько, данный алгоритм нежизнеспособен и непригоден для использования, причина проста — время позиционирования не равно нулю, т.е. узкое место с большими задержками по времени, примерно 3,6-11,5 мс на каждый вызов seek-функции, а счет идет на сотни миллионов таких вызовов для поставленной задачи. Нетрудно оценить время — от недели до месяца реального времени. Хочется более точных цифирь? Берем и пишем программу, которая вычисляет среднее время позиционирования: есть файл 4 ГБ, из него считываем случайные блоки, продолжительность — минут десять, делим это время на число прочитанных блоков за этот период. Далее генерируем массив случайных величин размером равным числу строк файла для сортировки (у меня тестовый файл содержал ~15 млн.) и считаем число сравнений, потребовавшихся для его сортировки, умножаем на удвоенное среднее время и получаем более адекватную и удручающую оценку. А если файл лежит на двд-диске… Кто-то хочет еще провести полномасштабное тестирование этого алгоритма?.. ^^ Ладно, вернёмся к загадочному числу 16, взятому явно с потолка у инженера-программиста — они ведь любят степени двойки и на них зациклены. Ещё на заре развития накопителей, минимальной адресуемой единицей был блок 512 байт (ходят сплетни, что сейчас у современных уже 4 КБ). В нашей задаче придется, как минимум, один раз прочитать каждый блок и если делать это по 16 байт, то получается, что файл будет прочитан 32 раза (256 раз в современном варианте ^^, новые технологии определённо радуют при отсутствии соответствующего обеспечения, хотя это и не заметно при растущем быстродействии). Забавно, но при сортировке не факт, что нам потребуется больше 1-4 байт в среднем от каждой строки на реальной задаче, хотя всякое бывает, а читается за раз 512 байт минимум… К чему это я всё клоню-то?) Да вот к чему — кажется, что увеличив буффер чтения, минимизируется число обращений к накопителю, но это справедливо только в случае последовательного доступа, когда мы знаем, что прочитанный байт потребуется в следующей итерации, а в этом алгоритме — доступ асинхронный, количество байт, которые нужно прочитать, зависит от самих строк в файле, т.е. величина эта случайная и совсем не предсказуемая — может быть будет эффективно буферизовать всю строку, а может и нет — хватает одного байта для сравнения. В общем, вместо минимизации реального чтения идет минимизация >потенциальных< вызовов read-функции, что не есть одно и то же. И здесь издержки… Проедемся дальше и бросимся в очередную крайность. ^^ Есть у нас файл, в котором 0,8 млрд. 5-байтовых строк, и будем мы его сортировать по предложенному алгоритму. Смотрим «карту»: 4 байта на смещение и 4 байта на длину для каждой строки, т.е. мы не знаем что в файле короткие строки, а по условию задачи они могут быть до 1 ГБ. (4+4)*0,8=6,4 ГБ. А не жирно ли для сортировки файла в 4 ГБ, да ещё с подкачкой строк с накопителя? ^^ А там еще какой-то список указателей на обьекты «карты» — смело умножаем на 1,5-2 (в зависимости от типа контейнера-списка, подробностей не знаю и что-то не очень хочется) и получаем сказочные 9,6-12,8 ГБ с подкачкой фрагментов строк в буффера сравнения. Я нервно хихикаю в сторонке со своими 756 МБ, две трети которых жрёт ось с виртуальным диском и запущеным браузером… Вывод: алгоритм шедевральное говно и не канает, да и понятно становится почему программа после запуска «самоустраняется» и провести «полномасштабное» тестирование проблематично. В общем, вместе флешкой от заказчика должен поставляться нигра, как бонус за отменный алгоритм, с баночкой вазелину — дабы легче флешка прошла…

 

ToDo

Совместными усилиями у нас есть две хорошие реализации алгоритмов сортировки:

1. Сортировка строк неограниченного (сверху) размера
2. Внешняя сортировка файлов неограниченного размера, содержащих строки ограниченной длины

Осталось скрестить их на досуге, и получить маленького милого сортировочного монстрика, которого можно будет препарировать и эксплуатировать на благо человечества.  🙂

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*