Сообщение Как правильно сортировать содержимое больших файлов? от 21.08.2022 11:11
Изменено 21.08.2022 11:11 _FRED_
Исправил заголовок
Как правильно сортирать содержимое больших файлов?
Привет,
Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).
Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.
Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг
Так мне написали.
Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл. Так мы можем подобрать, сколько памяти программа будет занимать.
Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано. Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
Затем открываем все созданные файлыб вычитываем по строке, сортируем, пишем в выходной файл меньшее значение и из этого файла вычитываем следующу строчку.
Буду брагодарем за объяснения, как это должно быть сделано правильно.
Решение: https://github.com/ViIvanov/DataSort
P.S. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.
Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).
Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.
| Задание | |
| На входе есть большой текстовый файл, где каждая строка имеет вид Number. String Например: Обе части могут в пределах файла повторяться. Необходимо получить на выходе другой файл, где все строки отсортированы. Критерий сортировки: сначала сравнивается часть String, если она совпадает, тогда Number. Т.е. в примере выше должно получиться Требуется написать две программы:
текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой частью String. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования будет использоваться размер ~100Gb. При оценке выполненного задания мы будем в первую очередь смотреть на результат (корректность генерации/сортировки и время работы), во вторую на то, как кандидат пишет код. | |
Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 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. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.
Как правильно сортировать содержимое больших файлов?
Привет,
Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).
Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.
Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 1Г сортируется за 13 с небольшим секунд, а у ревьюеров получилось 130c на файл 1 гиг Так мне написали.
Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
В целом как сделано: на вход программе сортировки подаётся путь к файлу и количество строк, на которые можно перед сортировкой разбить входной файл. Так мы можем подобрать, сколько памяти программа будет занимать.
Схематично, алгоритм такой: входной файл вычитывается PipeReader-ом: столько строк, сколько задано. Пока эти строки сохраняются в файл, начимаем вычитывать следующий буфер, дабы избежать простоя.
Затем открываем все созданные файлыб вычитываем по строке, сортируем, пишем в выходной файл меньшее значение и из этого файла вычитываем следующу строчку.
Буду брагодарем за объяснения, как это должно быть сделано правильно.
Решение: https://github.com/ViIvanov/DataSort
P.S. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.
Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в C# и dotnet и покапаться в спанах (может, в этом и была моя ошибка, подскажите).
Но так в открытую задание шарить не хотелось (чтобы не подводить компанию), а подготовить для общественного порицания своюь реализацию в более простом виде всё времени небыло, тормозил с этим
А раз уж аж видео-обзор этого задания вышел: Тестовое задание Senior .Net — критикуйте, то, думаю. не страшно, если я прям так. Если что, звиняйте.
| Задание | |
| На входе есть большой текстовый файл, где каждая строка имеет вид Number. String Например: Обе части могут в пределах файла повторяться. Необходимо получить на выходе другой файл, где все строки отсортированы. Критерий сортировки: сначала сравнивается часть String, если она совпадает, тогда Number. Т.е. в примере выше должно получиться Требуется написать две программы:
текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой частью String. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования будет использоваться размер ~100Gb. При оценке выполненного задания мы будем в первую очередь смотреть на результат (корректность генерации/сортировки и время работы), во вторую на то, как кандидат пишет код. | |
Решение моё интервьюеров не удовлетворило, говорят, что очень медленно работает: как обычно, у меня на лаптопе как раз всё летает, файл в 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. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.