Информация об изменениях

Сообщение Как правильно сортировать содержимое больших файлов? от 21.08.2022 11:11

Изменено 21.08.2022 11:11 _FRED_

Исправил заголовок

Как правильно сортирать содержимое больших файлов?
Привет,

Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в 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

Требуется написать две программы:
  1. Утилита для создания тестового файла заданного размера. Результатом работы должен быть
    текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой
    частью String.
  2. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования
    будет использоваться размер ~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. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.
Как правильно сортировать содержимое больших файлов?
Привет,

Ещё в прошлом году дали в одной компании тестовое задание, которое мне показалось интересным сделать — во-первых, я на программиста не учился и сортировку файлов слиянием делать мне никогда не приходилось, только читал. Во-вторых, показалось, что в такой задаче можно как раз удачно поиграть с последними нововведениями в 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

Требуется написать две программы:
  1. Утилита для создания тестового файла заданного размера. Результатом работы должен быть
    текстовый файл описанного выше вида. Должно быть какое-то количество строк с одинаковой
    частью String.
  2. Собственно сортировщик. Важный момент, файл может быть очень большой. Для тестирования
    будет использоваться размер ~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. Мне показалось, что Алгоритмы более подходящий форум для этого обсуждения, но если нет — то давайте перенесём.