На сайте одной из харьковских фирм, занимающихся аутсорсингом, опубликована задача такого содержания:
Необходимо написать алгоритм, который бы смог отсортировать строки в файле большого размера (от 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. Внешняя сортировка файлов неограниченного размера, содержащих строки ограниченной длины
Осталось скрестить их на досуге, и получить маленького милого сортировочного монстрика, которого можно будет препарировать и эксплуатировать на благо человечества. 🙂