Отсортировать строки в файле размером 3GB

Опубликовано Sep 30, 2011 в Тестовые проекты (2-3 часа) | 27 коммент.

, , ,

Отсортировать строки в файле размером 3GB

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

За хорошую реализацию гарантированный приз – флешка для хранения таких файлов и, возможно, предложение работы в нашей компании.


27 Коммент. : “Отсортировать строки в файле размером 3GB”

  1. Спасибо за вопросы.

    >>А куда отправлять собственно исходник со своим вариантом решения задачи? Или флешки уже давно кончились? Насколько я понял, нужен алгоритм, который выполняет задачу за разумное время, используя значительно меньше памяти, чем 4 гб, так ведь?

    Решение задачи стоит отправлять по адресу team@fulcrumweb.com

    >используя значительно меньше памяти, чем 4 гб, так ведь?

    Абсолютно верно

    По какому признаку сортировать нужно? И чем они разделены? Или нужно сделать что то универсальное?

    Строки сортируются по значению. Файл – текстовый. Длина строк неограниченна (строки могут быть от одного байта до гигабайта – т.е. например файл может состоять только из строк длиной в один символ или 4-х строк длиной по гигабайту или все в вперемешку)
    Все исходные строки должны присутствовать в результирующем файле.
    Если строка повторяется – то она должна повторяться и в результирующем файле.

  2. Trusov Denis says:

    Увы, я предполагал, что строки имеют вменяемую длину, скажем не больше 1 мб, например. Если генерировать/преобразовать файл к такому виду нельзя, то я — пасс. Попытаюсь изложить суть проблемы. Строки нельзя хранить в памяти, поэтому придется подгружать их части из файла по мере необходимости, но любой накопитель уступает ОЗУ по скорости доступа настолько, что скорость выполнения данной задачи зависит от того, насколько часто приходится обращаться к носителю с файлом. Т.е. задача сводится к минимизации непоследовательных обращений к исходному/промежуточному файлу. Во время сортировки требуется неоднократное обращение к строкам и если их не держать в кэше, то падение скорости выполнения будет весьма ощутимым. Для примера, если перечитывать пару строк для сравнения из одного буфера в другой, то это увеличивает время сортировки в среднем в 40 раз! А, в случае, если придется перечитывать строки (или их часть) в буфер из файла, то это время только существенно увеличится. В целом, время выполнения задачи в таком случае будет сильно зависеть от содержимого строк, поскольку существуют такие наборы данных на которых программа будет работать “бесконечно”, т.е. нельзя гарантировать приемлемое максимальное время выполнения для любого набора данных. Ну и кому будет нужна такая программа? Если учесть затраты на электоэнергию и амортизацию в долгосрочной перспективе, то дешевле докупить необходимую память и выполнять эту задачу за минимум времени, поскольку массив строк крайне легко упорядочить, когда он умещается в памяти.
    А вот, если ограничить длину строк, то задачу можно свести к схеме “чтение исходного 4 гб файла и запись промежуточного 4 гб файла, чтение промежуточного 4 гб файла и запись результирующего 4 гб”. Для такого алгоритма можно дать оценку времени — допустим время чтения равно времени записи и равно 5 мин, тогда примерное время выполнения будет 20-30 мин.
    Интересно откуда у этой задачи ноги растут или это просто ещё одна из искусственных задач для проверки навыков программиста? В общем, отослал исходник с вариантом когда длина строк ограничена, хочу увидеть, обещанную в одном из постов, критику проекта.

    • Спасибо, исходники посмотрим.

      Да, задача искусственная и постановка задачи намеренно сделана неполной.
      Было интересно услышать ваши размышления (вопросы и предложения).
      Вы правы что с большими строками работать сложно (да и не просто найти готовый алгоритм на Google:-) ).
      НО – можно ведь не сразу сортировать – а для начала пройтись по файлу, пособирать статистику (сколько строк, какие длины, сколько очень длинных строк (записать их положение) и т.п.).
      Далее можно в зависимости от длины применять разные алгоритмы.
      Сравнивать большие строки можно не целиком (например тот же первый мегабайт строки) Для больших строк, отличающихся в последних байтах, можно сделать отдельный проход для их “до-сортировки”(при этом сколь долго строки совпадают – уже можно писать результат) и т.п.

  3. А задачка еще актуальна?

    • Добрый день. Вполне актуальна. Но проверить раньше конца января не сможем, так как ее автор и вдохновитель в отпуске. Так что можете, если интересно, делать не спеша и красиво.

  4. Liaksiejka says:

    Можно ли использовать промежуточные файлы? Если да то есть ли на них ограничение. Какой примерно размер хранимой памяти будет допустимым, скажем 100 мб допустимый?

    • Хороший вопрос.
      Да, можно использовать промежуточные/временные файлы.
      суммарный размер не более, чем размер исходного файла (желательно минимизировать).
      И не забудьте потом их удалить :)

  5. Опубликовал свой вариант решения предложенной задачи с подробными комментариями:
    http://cpp.in.ua/2012/02/o-sortirovke-bolshix-tekstovyx-fajlov/

    Теперь с нетерпением жду или фирменной флешки, или фирменной эталонной реализации с лучшими результатами и подробным описанием фирменного алгоритма (а лучше и то, и другое сразу). ;)

    • Trusov Denis says:

      Йо-хо-хо… Ещё один кандидат на флеш-премию. :) Исходники не смотрел, но пару слов скажу. Если судить по устному описанию алгоритма — реализована следующая незатейливая схема: получить массив смещений в файле с длинами строк и упорядочить его, а строки считывать во время сравнения буфферизируя по 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 МБ, две трети которых жрёт ось с виртуальным диском и запущеным браузером… Вывод: алгоритм шедевральное говно и не канает, да и понятно становится почему программа после запуска "самоустраняется" и провести "полномасштабное" тестирование проблематично. В общем, вместе флешкой от заказчика должен поставляться нигра, как бонус за отменный алгоритм, с баночкой вазелину — дабы легче флешка прошла…
      А в целом, задачу нужно было начинать делать с вопросов: сколько можно использовать оперативной памяти и других ресурсов, за какое время должна быть решена задача, т.е. время обработки одного файла. Получить образцы характерных файлов для тестирования. Да и если возвели задачу в ранг сверхзадачи, за которую полагается поощрение, нужно хотя было составить табличку с рейтингом программ типа сумма весовых коэффициентов по степени важности помноженные на пиковое использование памяти и время исполнения над тестовым файлом соответственно. Или составлять рейтинговую таблицу не из чего?) Этот был вопрос к организаторам блога компании.
      Покаюсь, я тоже написал подобный алгоритм сначала, думаю я не первый и далеко не последний. Но после того как тест показал его не состоятельность, появилась идея как реализовать достаточно эффективный для строк не превышающих некоторой длины с предсказуемым пиковым потреблением памяти. Но, увы, последующее уточнение развеяло предположения об ограниченности длины строк. А поскольку идея, как эффективно обрабатывать сверхбольшие строки, не посетила сразу, решил отказаться — тут ситуация из разряда: лучше уж ничего не предлагать, если не можешь предложить что-нибудь внятное. А тут заявко: совсем не работает — ну и ладно, и так сойдет, подавайте-ка мою фирменную флешку. Кстати, я ведь не тестировал свою программу на большом файле полностью, только определенные этапы… Технические трудности, так сказать — винт помер давным-давно, писать временный файл некуда. Работает ли корректно (при строках не более 1 МБ)? А то камментов по ней как кот наплакал… ^_^
      Взглянув на задачу вновь, спустя столь долгое время, есть предположение, что можно написать эффективный алгоритм, который вложится в пиковое потребление от 64-90 МБ памяти и промежуточным файлом такой же длины как и исходный (или меньше, это будет зависеть от количества сверхдлинных строк).
      А насчёт того, что эта задача выплывает из СУБД — задачи принципиально разные: в БД запись имеет фиксированную длинну, т.е. достаточно знать адрес одной записи и все остальные легко вычисляемые — ненада никаких "карт". Да и сами данные всегда на одном месте с момента записи, нужен другой порядок — вот вам в зубы индексный файл. Посему эта задача искусственная, а кто пишет такие программы, которые выдают неструктурированные данные с такими характеристиками, и перекладывают дальнешие проблемы на следующего в цепочке, который будет обрабатывать эти данные — их расстреливать сразу надобно, чтоб не осложняли жизнь другим. :)

      • Денис, Вы – писатель, а не читатель – Ваше право. )
        Но…
        Денис, пожалуйста, Ваш вариант в студию, плиз! Зачем так много пустых слов? ;)

        • Trusov Denis says:

          Вот файл с текстом программы, который я отсылал. Если так уж интересно, хотя мой велосипед ничем особо не отличается от описанного в приводимой ссылке на англо-википедию.

          http://files.mail.ru/F0PKZD

        • Trusov Denis says:

          Ссылка на модерации. А словоблудие будет полезно для продвижения сайта в топ выдачи — это ж сколько уникального контента я нагенерил. Пока бегло пробежался по твоему исходнику — алгоритм несколько иной, но болезни будут те же, что я озвучил ранее. Позиционирование проявит себя во всей красе на втором и последующих этапах сортировки. Ну и по памяти в любом случае твоя программа весьма прожорлива. И что в итоге получим? Я так понял массив смещений строк в искомом порядке с хвостиками строк в буфферах — в итоге возвращаемся опять к проблеме позиционирования: строки придется считывать из источника в случайном порядке. Просто замерь сколько эта операция занимает реального времени — сколько строк ты сможешь прочитать за час из большого файла. Вот если увеличить размер буффера до рамера кластера файловой системы, то алгоритм будет хорош для больших строк, но таких строк должно быть немного.

  6. Trusov Denis says:

    Назрел вопрос, а исходный неупорядоченный файл нужен ли после сортировки? Если задуматься, то скорее всего ведь не нужен. Или назовите причину, почему бы от него не избавиться.)

    • Может нужен, а может и нет. Скорее всего решать это стоит не программе по сортировке. Обычно, если файл создан не нами(существовал до момента запуска нашего кода), то, прежде чем решиться его удалить, стоит спросить себя минимум 7 раз – уверены ли мы, что он точно никому не нужен и что 100% никто его искать не будет. А может он кому-то дорог как память:)

      • Trusov Denis says:

        Аргумент засчитан и фича должна быть реализована в виде опции. Просто возникло предположение, что если исходный файл участвует в цепочке “исходные данные — конечный результат”, то скорее всего он является тоже промежуточным. А раз так, то почему бы не сбросить “балласт” сразу как он стал не нужен.

  7. Trusov Denis, Ваши рассуждения, в целом, вполне логичны и заслуживают внимания. Однако, для конкретной задачи должно быть нечто большее, чем одни лишь рассуждения, а именно, – решение.
    Конечно, можно рассуждать в умозрительном поиске идеального варианта, но…
    Представьте, если бы Майкрософт захотел выпустить идеальный Виндоус, знали бы мы о нем хоть что нибудь сейчас? Нет.
    Любое решение прикладной задачи лучше, чем отсутствие такового – ведь оно дает основу для дальнейшей работы, усовершенствования.
    Учтя Ваше (совершенно верное) замечание, что я не тестировал свое решение на действительно длинных строках, я написал программку для обеспечения такого тестирования. Теперь могу с полной ответственностью заявить, что строки длиной до нескольких МБ (тестировал до 3) обрабатываются совершенно корректно.
    Пожалуйста, не стесняйтесь, выкладывайте свой вариант для этой задачи, мы протестируем и сравним. Также, пожалуйста, используйте всё, что сочтете полезным из выложенных мною исходников, в своём варианте решения задачки. Извините, что отчасти повторяюсь, но, для удобства:
    Утилита для тестирования (новое): http://cpp.in.ua/wp-content/uploads/2012/03/TextSortTester.zip
    Исходники решения: http://cpp.in.ua/wp-content/uploads/2012/02/ExtSorting.zip
    Описание всего этого: http://cpp.in.ua/2012/02/o-sortirovke-bolshix-tekstovyx-fajlov/

    Уважаемый Jacob, Вы тоже не стесняйтесь, присоединяйтесь к нашей песочнице! Я уверен, Вы способны предложить оригинальный, интересный и эффективный вариант алгоритма для этой задачки. Не сочтите, что пытаюсь Вас торопить и напрячь заниматься ерундой (я вполне понимаю Ваши цели), но хотя бы через полгодика надеюсь его увидеть, заглянув на этот сайт. ;)

    • Trusov Denis says:

      Кошмар. Ссылку на файл-исходник моей программы не пропустили и похоже не пропустят. Прям теория заговора какая-то. Отправил на мыло.
      Никто и не пытается идеализировать разработку софта. Просто задача не решена, т.е. теоретически предложенный метод будет работать, а на практике — он бесполезен. Примерно, как в случае с определителем матрицы большой размерности — никто не ищет его тем методом, которым он вводится в лин. алгебре, а используют метод Гаусса. Задача считывания большого числа случайных строк из файла размазанного по диску (да хоть и не размазанного) для большинства современных накопителей является непосильной. В этом контексте фраза “Давайте флешку. А будет ещё лучше, если покажете правильное решение, т.е решите за меня.” звучит не очень.
      Задача уже разжёвана до предела: разделить исходный файл на два — в один сбросить “короткие” строки, а в другой — “длинные”. Первый отсортировать можно моей программой (алгоритм аналогичен описанному в англо-вики по приведенной ссылке), второй — вашей с увеличенным буффером (например, до 4 килобайт). А дальше обьединить их методом сортировки слиянием. Тонкости оптимизации (счётчики для очень коротких строк; сбрасывать в отдельный файл “длинные” строки в принципе не нужно) — это уже не очень интересные детали и банальная рутина. И вот “фирменный” алгоритм готов, хотя он, скорее всего, единственный для поставленной задачи.
      Переписывать/дописывать программу не вижу смысла, поскольку комментариев о недостатках по отосланному исходнику было чуть более, чем ноль — вскользь упомянули, что промежуточный файл нужно удалять. Так этот “недостаток” был описан в сопровождающем текстовом файле и оставлен умышленно, чтобы содержимое можно было посмотреть.
      Кстати, если вдруг случайно выяснится, что строки будут в кодировке utf-8, то как много строк придется переписать в вашем алгоритме?

      • Денис, напишите ссылку на Ваш исходники с очевидными очепятками, например хттп://www.mysource.com/test.зип, и её пропустит кто угодно. Если Вы не против, могу добавить Ваш вариант решения в запись на своем сайте вместе с Вашим сопроводительным текстом (шлите на мыло -jet-[мяу]ukr.net).
        А о прикладной ценности этой работы предлагаю не переживать – я с этой задачкой возился исключительно тогда, когда ничего более полезного делать был не в состоянии (например, после очередного отмечания дня рождения коллеги). Конечно, если надоело – нету смысла себя насиловать.
        …А исходники давайте Ваши опубликуем – вдруг кому пригодится (а может быть, и нам самим когда-нибудь)? ;)

        • Trusov Denis says:

          Та делай с ним, что хошь. Хоть впаривай за плату. Надеюсь, роялти отчислить не забудешь, если вдруг бабло попрёт. LMAO

          • Спасибо. Вы выполнили хорошую работу по решению поставленной задачи, я просмотрел Вашу программу. Раз уж местные корифеи не рвутся комментировать, позволю себе выразить своё впечатление.

            У Вас аккуратный, легко читаемый код, из которого следует наличие хорошего опыта работы со стандартной библиотекой, знание ООП, наличие теоретических знаний о проектировании приложений.
            Он далек от идеала с точки зрения (исключительно моей лично) оптимизации по быстродействию (например, в условиях циклов пестрят явно ненужные вызовы методов контейнеров), хотя, сравнение в функторе выполняется с привлечением арифметики указателей (что есть хорошо). Однако, с точки зрения некоторых знакомых мне архитекторов, оптимизация – ничто, а вот следование паттернам и сомнительным требованиям типа “если код метода длиннее 20 строк, значит его нужно разделить”, Ваша программа написана отлично. Впрочем, это уже дело вкуса и целесообразности.

            Итог:
            Вы хорошо реализовали классическую внешнюю сортировку, с лучшей стороны продемонстрировали некоторые свои профессиональные навыки.
            Было бы совсем хорошо, ели бы Вы могли дать значения времени сортировки для файла размером 100 МБ.

            Сочетая выполненную Вами и мною работу, можно получить требуемый универсальный алгоритм. У Вас нет ограничения на размер строки с меньшей стороны, у меня – с большей. Подождем кого-нибудь третьего, кто это сделает, или же какого-нибудь праздника с возлияниями (когда это сделаю я сам). ;)

            Если бы мне было по-душе грести бабло лопатой, я бы взял Вас на испытательный срок, даже несмотря на депрессивность Ваших высказываний. Однако, меня всегда больше интересовали технические вопросы, чем “впаривание” продукта клиентам.

            Если Вас расстраивает недостаток внимания со стороны хозяев сайта – это Вы зря. У них свои цели и свои интересы (подороже_Вас_продать/подешевле_Вас_купить = больше счастья), у нас – свои. Мне вот, к примеру, нравится их тема для Вордпресса, удобно комментарии постить. :)

        • Денис, разместил Ваш исходник и критику моего алгоритма у себя в записи, можете просмотреть, и если что не нравится – сообщите, исправлю. )

          З.Ы. Спасибо владельцам этого сайта за гостеприимство и то, что настолько либерально относитесь к нашему флуду. :)

          • Trrusov Denis says:

            Всё-таки ради интереса протестировал скорость работы на 100 МБ файле, хотя сами по себе тесты в моем случае особого смысла не несут — у меня нет физического накопителя (все на виртуальном диске в ОЗУ). В итоге, было написано пару скриптов для теста (они прилагаются с прочими музейными экспонатами из раздела “как не надо” для историков и любителей покопаться в сортах различного…) и выяснилось, что всё-таки ошибка есть. Я не виноват, это просто изъян в периодической системе символов Интернета имени ASCII, а именно — символ перевода строки находится не в начале таблицы. Мне стало стыдно за чужие ошибки (ANSI, в частности, который её собственно и издал в таком виде) и я добавил на скорую руку костылик, который должен сводить на нет весь изъян. Ссылка прилагается. Результаты моего теста в лог-файле в архиве. Лучше его и выложить на ваш сайт (архивчик).
            хттп://files.mail.ru/9IWBXL
            И, кстати, не серчай на мою критику. Я её писал даже не заглядывая в исходник, а на основе словесного описания. Ввиду того, что словесное описание тонкостей центральной идеи довольно скудно или чрезмерно упрощено, так что предложения из пунктов 3 и 4 не воспринимаются должным образом, для того, кто не смотрел вглубь. И кажется, что реализована классическая сортировка с указателями в памяти на строки в файле… Но попытка сделать хороший алгоритм для “длинных” строк универсальным провалилась с треском винта — чем меньше кеш строк, тем резче падает производительность. А, в принципе, на файле состоящем из одних “длинных” строк он способен завершить выполнение задачи за [~3 полных чтения файла в худшем случае (2 в лучшем) + 1 запись в файл] против моего варианта [2 чтения + 2 записи в любом случае], но для большого числа строк его никак не адаптировать. Дифирамбы, дифирамбы… А ведь вполне очевидно, что код вылизан, ну по крайней мере старался причесать более менее, т.е. показать, что если надо, то всё возможно. :) Хотя рудиментов от предыдущих вариантов моих реализации отбавляй по самое нехочу. И на завершающей ноте — таки, я бы не решил эту задачу в оффисе за 2-3 часа.
            ЗЫ
            Всё-таки контейнер контейнеру рознь, и хоть метод size() не реализован как {retun this->count;}, там всё же не обход списка.

        • Trrusov Denis says:

          Всё-таки, неблагодарное это занятие, упражняться в обходе фильтров. Очередная модерация.

  8. galina says:

    На эту тему идет дискуссия – вставлю и я свои пять копеек.

    Очевидно, что суть задачи в том, что нужно работать со структурой данных, которая не помещается целиком в память. Задача, на самом деле, очень не простая, начиная от весьма неконкретной постановки, и заканчивая очевидными большими временными затратами, необходимых просто для полноценных тестовых запусков.
    Пользуясь привилегией модератора, свое решение я буду постепенно публиковать в виде поста http://www.fulcrumweb.com.ua/?p=2709

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

    Сейчас уже думаем над новыми интересными задачами и новыми призами.

    • Да ладно, мы тут и сами справляемся потихоньку, а еще Галина взяла огонь (по теме) на себя.
      Это ей надо памятную флешку за отвагу, ведь девушка после восьмого марта, в нерабочее время, без принуждения сверху нашла в себе силы и сделала свой вариант решения! )

Оставить комментарий

Ваш адрес email не будет опубликован.


*