Привет друзья.

Как обычно Илья, Сова, Саша, Чингиз и все остальные.

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

Давайте в форуме один раз и навсегда закодим решение и поставим точку в этих трудностях.

Буду краток. Надоело растекаться по дереву.

Вобщем дано:

Input:



Output:


Комментарии к ТЗ:
1) Предполагается любая операционная система Windows/Linux/BSD.
2) DBMS не установлен и не используется.
3) Исходный текстовый файл минимум четырёхкратно превышает доступную физическую память.
4) Результатом является - лексикографически отсортированный текстовый файл
5) Кодировки - опциональны. Тоесть мы на них пока забиваем болт. Символы - однобайтные.

Приветствуется:
1) C/C++/Rust/D
2) Delphi/FPC
3) Ассемблер. Хардкод и всякие там MMX/SSE1,2,3,4,5/AVX.

Что будем обсуждать:
1) Ваши идеи и сорцы.
2) Кардинальность. Структуры данных. Подсчет. Сжатие (возможно?).
3) Дисковая оптимизация. 1,2,3 физических дисковых устройства.

Что мы не будем обсуждать.
1) Чужие сорцы. Здесь я поясню что
в рамках форума Программирование,
лично мне, а также сообществу, интересно говорить с автором
и задавать вопросы по исходникам. Поэтому ссылка на
github "канает" только в одном случае - если вы автор
или участник разработки.
2) Готовые коробочные продукты.

Особо также приглашаю в топик Диму-Т т.к. слыхал что у него есть идеи по поводу сортировок. Ау, чел!

С уважением, ваш покорный слуга,
а также большой ворчун и бухтелка
mayton.

Мой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.




При таком раскладе в фазе 2 merge-sort мы имеем




Возможны варианты с компромиссом. Когда у нас (0001) и (0002) читаются с устройства /mnt/disk1, и пишуться в /mnt/disk2

+Надо еще подумать как быть с третьей фазой. По сути решать пасьянс с файловой нагрузкой.

Dima TmaytonМой поинт в том что при реализации merge-sort мы работаем обычно с 1 дисковым устройством.
Допустим это /tmp. Но для эффективного алгоритма слияния нужны минимум 3 дисковых устройства
которые работают независимо.
Ерунду написал. Нет смысла рассматривать оптимизацию железа для решения данной задачи.

Я уже писал "в реальной жизни оптимизация начинается до получения этого биг-файла"

Если у тебя эта сортировка происходит регулярно и требует оптимизации, то оптимизацию надо начинать в источнике возникновения файла, т.к. их много, так нагрузку проще распределить.
ОК. Поговорим тогда про оптимизаци в источнике.

Кардинальность. В теории (я не уверен стоит уточнить) это количество уникальных записей.

Допустим нам на вход идут данные следующего рода.


Можно сказать что уникальных записей всего две хотя из текстового файла пришло 3 штуки.

Для сортировки и слияния совершенно нет необходимости многократно копировать повторения
если на 1-й фазе мы их слегка преобразуем. Мы учтем повторы в виде специального счетчика.



Счетчик удобно укладывается в алгоритм слияния. Подобно сортировке подсчетом. Его можно тащить аж до последней фазы
где два файла сливаются в один равный по размеру исходным данным. По сути это нечто вроде
RLE (run-length-encoding).

Когда принимать решение о введении счетчика или об отказе от него? Это вопрос.
Но в любом случае решение этой задачи потребует хотя-бы одного full-scan текстового
файла. И уж коли мы решили это делать то лучше собрать на этом шаге максимум
сведений.

Dima TЕрунду написал. Нет смысла рассматривать оптимизацию железа для решения данной задачи.
Еще дам один комментарий. Речь не идет об оптимизации железа. А скорее о сборе сведений
о конфигурации. И если конфигурация позволяет - то почему этим не воспользоваться?
Разумеется я не предлагаю форматировать и монтировать диски. Но разве ты, когда экспериментировал
с акторами не опрашивал систему на имеющиеся на борту количество CPU-s/Hyper-Threads?

Замётано док. Будем форсировать директ. Я уже название придумал.

Roilling-triplet algorithm. Типа крутящийся треугольник. А мои сомнения
по поводу дискового пасьянса - только что развеялись.

Псевдокод.

д0kХЯ себе могу подключить в полигон для тестов
терабайт дискового пространства 50 000 iops и трансфером 2400 МБайт/сек
Да подключай хоть амазон.

По сути здесь топик - про собеседование и рассуждения о том как решить данную задачу.

Но поскольку я - бухтелка и перфекционист, то я ставлю сверх-задачу, а именно оптимизацию merge-sort
при условии что она УЖЕ реализована и корректно работает на 1 локальном дисковом устройстве.

Я думаю что лучше все таки такая форма

Соровка текстового файла размером 4 RAM
за минимальное время.

С эталонными файлами - проблема.

Пожалуй это главный косяк этой задачи на собесе.
Мы о них ничего не знаем. Это может быть текстовый файл.
CSV-экспорт из БД. HTML. И вообще все что угодно.

В некоторых постановках максимальная длина строки
ограничивалась в 255 символов. В некоторых в 2Г.

О кардинальности также нет сведений.

Вобщем вот такие вот условия.

д0kХ,

я не совсем понял, по какому принципу мы будем бить файл на блоки.
(Сорян у меня c блоком - ассоциации c 8K Oracle db_block).

Будет сложно просить пользователя вводить эти цифры. Часть из них лучше получить
из API по аналогии с lscpu, free, df.

Dima TТ.е. если считаем что файл не сортированный, то одно ядро отдаем под слияния, а все остальные под сортировку блоков. Размер блока надо исходя из количества ядер выбирать, думаю чтобы 4-8 блоков на ядро получалось, чтобы слияния как можно раньше начались.
Я не просто так делаю акценты на дисковой подсистеме.

Если в 1-й фазе для тебя важна скорость сортировки блока в оперативке (можно поискать мультипоточный хоар)
То в фазе №2 у нас будет суровое физическое ограничение. Вы хоть в 16 ядер запускайте merge двух блоков (файлов)
но события ожидания у вас выстроятся в очередь на канале вашего жесткого диска.

Фактически фаза 2 представляет из себя сплошное дисковое копирование. И если кто-то из вас часто и много
копировал большие файлы (бэкапы) а я - много копировал, то вы представляете себе масштаб трагедии.

Если у вас не RAID стойка - а обычная рабочая станция то никакого масштабирования не будет.

Есть 1 сканирование. Это факт. Предлагаю его взять на вооружение.