Привет,

Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).

Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.

	Задание
	На входе есть большой текстовый файл, где каждая строка имеет вид Number. String Например: 415. Apple 30432. Something something something 1. Apple 32. Cherry is the best 2. Banana is yellow Обе части могут в пределах файла повторяться. Необходимо получить на выходе другой файл, где все строки отсортированы. Критерий сортировки: сначала сравнивается часть String, если она совпадает, тогда Number. Т.е. в примере выше должно получиться 1. Apple 415. Apple 2. Banana is yellow 32. Cherry is the best 30432. Something something something Требуется написать две программы: Утилита для создания тестового файла заданного размера. Результатом работы должен быть текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой частью String. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования будет использоваться размер ~100Gb. При оценке выполненного задания мы будем в первую очередь смотреть на результат (корректность генерации/сортировки и время работы), во вторую на то, как кандидат пишет код. Язык программирования: C#.

Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг Так мне написали.

Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

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

Буду брагодарем за объяснения, как это должно быть сделано правильно.

Решение: https://github.com/ViIvanov/DataSort

	Как это запускать
	Сначала можно запустить GenerateFile.cmd, он создаст подпапку Results и в ней файл DataSort-1G.txt размером 1 гигабайт. Командная строка: @GenerateFile --FilePath "..\..\..\..\Results\DataSort-1G.txt" --RequiredLengthGiB 1 то есть путь к файлу и требуемый размер в гигабайтах. Размер можно указывать дробный, например 0.1 для 100-мегабайтного файла. Какие-то более тонкие настройки есть в AppSettings.json рядом с исполняемым файлом. Потом (при необходимости нужно изменить текущую директорию снова на папку solution) можно запустить SortFile.cmd, он отсортирует файл, результат (единственный файл) будет в папке "Results\<guid>\" Командная срока: @SortFile --FilePath "..\..\..\..\Results\DataSort-1G.txt" --MaxReadLines 200000 Снова путь к файлу и количество строк, на которые можно перед сортировкой можно разбить входной файл. Этим параметром можно регулировать используемую оперативную память. Так же, некоторые более тонкие настройки есть в AppSettings.json рядом с исполняемым файлом.

P.S. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.

Здравствуйте, _FRED_, Вы писали:

_FR>Привет,

_FR>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где

Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.

А должно работать за O(N * log K)

Вероятно, проверяющий запускал тест с большим количество чанков (с меньшей потребляемой памятью).

_FR>В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл. Так мы можем подобрать, сколько памяти программа будет занимать.
_FR>Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано. Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
_FR>Затем открываем все созданные файлыб вычитываем по строке, сортируем, пишем в выходной файл меньшее значение и из этого файла вычитываем следующу строчку.

_FR>Буду брагодарем за объяснения, как это должно быть сделано правильно.

Сам алгоритм норм, но реализация не очень.

Кроме кривой реализации merge еще добавлю:
— смешаны отслеживание прогресса и сам алгоритм, я бы разделил (с помощью хуков, например)
— возможно, не стоит использовать async. Это усложняет реализацию, но, по-моему не дает значимых плюсов. Почти все время работы алгоритмы — работа с диском. Сама сортировка в памяти — единицы процентов
— я использовал генераторы (yield), алгоритм упрощается. см. http://rsdn.org/forum/dotnet/8339349.1

Автор: Буравчик
Дата: 19.08.22

Здравствуйте, Буравчик, Вы писали:

_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
Б>Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Б>Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.
Б>А должно работать за O(N * log K)

Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?

P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.

Здравствуйте, _FRED_, Вы писали:

_FR>Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
_FR>Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Так еще insert есть, в середину

_FR>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?

Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска

P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME

Здравствуйте, _FRED_, Вы писали:

_FR>P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.

Ну, может и не в этом

А профайлер что говорит?

Здравствуйте, Буравчик, Вы писали:

_FR>>Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
_FR>>Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Б>Так еще insert есть, в середину

То есть вот это вот по сути имеет линейную сложность:

var index = list.BinarySearch(item);
list.Insert(index >= 0 ? index : ~index, item);

_FR>>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
Б>Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска
Б>P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME

Мне выдали такие вот:

Как ориентир по времени — 10Гб файл генерируется около 2,5 минут, сортируется — 9 (кстати, это не самое быстрое решение).
Дополнительный ориентир — при сортировке 1Гб используется 2-2,5 Гб памяти.

На моём стареньком лаптопе, хорошем, но совсем не геймерском с ССД ессно генерация файла в 10Г занимает 35 секунд, сортировка 140с (памяти при этом расходуется меньше гига).
Если мне сказали, что моя программа работает 130 секунд на гигабайтном файле и это медленно, значит у них есть программы, которые там же работают значительно быстрее.

Я подозреваю, что дело тут может быть или в работе с диском или в каком-то принципиально другом подходе, потому что иначе не вижу, почему вдруг мой код работает в 10 раз медленнее, чем их.
Вот и интересно, в чём же именно я так промахнулся.

Здравствуйте, Буравчик, Вы писали:

_FR>>P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.
Б>Ну, может и не в этом

Да точно не там. Половина времени (примерно, ±10%) у меня это разбивка большого файла на мелкие, другая половина — сборка обратно большого сортированного файла из этих мелких.

Б>А профайлер что говорит?

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

Здравствуйте, _FRED_, Вы писали:

Решал эту задачу в реальном проекте в 2000-е. Но писал на C, поэтому мог позволить себе все. Да и исходный файл делал сам из других данных, так что мог его портить. Кроме того, надо было получить возможность доступа в порядке отсортированности, а собственно передвижение строк не требовалось.

Решение

Открываем file mapping и view на весь файл.

За линейное время проходим весь файл, заменяем разделитель внутри строки на '\0'. Конец строки тоже заменяем на '\0'. Одновременно строим массив указателей (смещение от начала файла + базовый адрес view) для каждой строки.

Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.

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

Если таки нужен выходной файл — пройти массив указателей линейно, переписывая строки в новый файл.

P.S. В действительности все было немного иначе. Полей в строке было 5-6 штук и надо было отсортировать по каждому полю. Так что массивов указателей было столько же и каждый сортировался.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Решал эту задачу в реальном проекте в 2000-е. Но писал на C, поэтому мог позволить себе все. Да и исходный файл делал сам из других данных, так что мог его портить. Кроме того, надо было получить возможность доступа в порядке отсортированности, а собственно передвижение строк не требовалось.
PD>Решение
PD>Открываем file mapping и view на весь файл.
PD>За линейное время проходим весь файл, заменяем разделитель внутри строки на '\0'. Конец строки тоже заменяем на '\0'. Одновременно строим массив указателей (смещение от начала файла + базовый адрес view) для каждой строки.

Хм. У меня в файле на 10 гиг 19,759,295 строк. Получается, файл на 200 гиг может содержать порядка (x20) 395,185,900 строк. Уже, вроде, гига полтора интов.

PD>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.

Исходный файл:

415. Apple
30432. Something something something
1. Apple
32. Cherry is the best
2. Banana is yellow

после преобразования:

415
Apple
30432
Something something something
1
Apple
32
Cherry is the best
2
Banana is yellow

Если я правильно понял предлагаемый алгоритм, то после сортировки будет:

1
2
30432
32
415
Apple
Apple
Banana is yellow
Cherry is the best
Something something something

И как потом собрать из этого то, что должно получиться в итоге:

1. Apple
415. Apple
2. Banana is yellow
32. Cherry is the best
30432. Something something something

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

Здравствуйте, _FRED_, Вы писали:

_FR>Хм. У меня в файле на 10 гиг 19,759,295 строк. Получается, файл на 200 гиг может содержать порядка (x20) 395,185,900 строк. Уже, вроде, гига полтора интов.

Тогда на них тоже file mapping. Хотя этого я не делал, за скорость не поручусь.

PD>>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.

_FR>Исходный файл:
_FR>

_FR>415. Apple
_FR>30432. Something something something
_FR>1. Apple
_FR>32. Cherry is the best
_FR>2. Banana is yellow
_FR>

После преобразования будет

415\0Apple\0
30432\0Something something something\0
1\0Apple\0
32\0Cherry is the best\0
2\0Banana is yellow\0

(точки я убрал, но они погоды не делают)

А массив указателей — на начала каждой исходной строки : p[0] на 415, p[1] на 30432 и т.д.

И тогда p[i] — указатель на число в строке, а p[i] + strlen(p[i]) — указатель на текстовую часть строки

Ну и все. qsort на этот p. В compare сравниваем как нам надо. Строки не переставляем, только p[i] будут переставлены.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Этот массив и сортируем обычной qsort, используя strcmp в качестве int (*compare), так как строка заканчивается '\0'. Если strcmp возвращает 0 для первого критерия, strcmp по второму критерию.

Такой вариант будет медленнее, чем merge-сорт. Потому что кардинально поменяется работа с диском, вместо sequential read&write будет выполняться random read&write.

Здравствуйте, _FRED_, Вы писали:

_FR>сортировку файлов слиянием

На сакмом деле, здесь лучше bucket sort

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>После преобразования будет
PD>415\0Apple\0
PD>30432\0Something something something\0
PD>1\0Apple\0
PD>32\0Cherry is the best\0
PD>2\0Banana is yellow\0

PD>(точки я убрал, но они погоды не делают)

Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?

PD>А массив указателей — на начала каждой исходной строки : p[0] на 415, p[1] на 30432 и т.д.
PD>И тогда p[i] — указатель на число в строке, а p[i] + strlen(p[i]) — указатель на текстовую часть строки
PD>Ну и все. qsort на этот p. В compare сравниваем как нам надо. Строки не переставляем, только p[i] будут переставлены.

Это часть понял, спасибо. Действительно, не могу представить, что случайные перескакивания по файлу, размер которого значительно больше объёма оперативной памяти, будут быстрее.

Здравствуйте, _FRED_, Вы писали:

_FR>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?

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

Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.

Здравствуйте, Буравчик, Вы писали:

_FR>>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?
Б>Вообще не нужно ничего заменять. Достаточно сохранять индекс начала строки. А еще лучше сохранять индексы начала и длину строки, но потребуется чуть больше памяти.
Б>Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.

Да, в таком разрезе это понятно: при каждом сравнении так сможем распарсить всю строку и сравнить как нужно.

Здравствуйте, _FRED_, Вы писали:


_FR>Тогда не понял: вы ранее писали, что "Конец строки тоже заменяем на '\0'.". Что такое "конец строки"? В винде это два символа \r\n. Каждый из них нужно заменить на \0 или только какой-то один?

Первый, то есть \r. Мне надо, чтобы каждая строка исходного файла превратилась в 2 строки ASCIIZ. Что будет после второй ASCIIZ — не важно, так как использоваться не будет

Исходно

415 Apple

То есть

415 Apple\r\n

После преобразования

415\0Apple\0\n

Имеем 2 строки ASCIIZ и указатель на первую из них. Если к нему прибавить strlen(первой) + 1, получим указатель на вторую, она тоже ASCIIZ. А что там за вторым нулем — мне совсем не важно.

Здравствуйте, Буравчик, Вы писали:

Б>Заменялось на \0, наверное, для того, чтобы использовать библиотечную оптимизированную strcmp. В задаче данного топика это не дает такой выгоды.

Да. Я же писал, там в действительности было 5 или 6 полей. Записал \0 в конец каждого и stricmp

Здравствуйте, _FRED_, Вы писали:

Нашел у себя этот код, и даже замеры времени.

Файл размером примерно в 1 Гбайт. Максимальное количество строк 1 миллион. Время на сортировку в разных случаях от 1-2 минут до 5-10 минут.

Писал я это в 2002 году. Pentium III, 666 Mhz, 256 Мб ОП, винчестер на 80 Гб. Хорошая была машинка, на тот момент одна из лучших в университете

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Нашел у себя этот код, и даже замеры времени.
PD>Файл размером примерно в 1 Гбайт. Максимальное количество строк 1 миллион. Время на сортировку в разных случаях от 1-2 минут до 5-10 минут.
PD>Писал я это в 2002 году. Pentium III, 666 Mhz, 256 Мб ОП, винчестер на 80 Гб. Хорошая была машинка, на тот момент одна из лучших в университете

О, так может удастся запустить сейчас, можно будет и померить?

Здравствуйте, _FRED_, Вы писали:

_FR>О, так может удастся запустить сейчас, можно будет и померить?

Увы, запустить не удастся. Эти csv файлы делаются из других, а тех у меня уже давно нет. Да и не помню я, что и как именно там запускалось — все же 20 лет прошло.